25 Aug 2026 13:30 : Information-Theoretic Limits on Computational Resource Tradeoffs in Machine Learning and Data Structures

PhD Defense
Tuesday, August 25, 2026, 01:30pm - 03:00pm

Speaker: Songhua He

Bio

Location : CoRE 301

Committee: 

Assistant Professor Sumegha Garg (chair)

Professor Jie Gao

Associate Professor Periklis A. Papakonstantinou

Assistant Professor Vatsal Sharan (external)

Professor David P. Woodruff (external)

Event Type: PhD Defense

Abstract: Algorithms can often reduce their use of one computational resource by spending more of another. Complexity theory has long studied the limits of such tradeoffs, especially between time and space. This thesis establishes new information-theoretic lower bounds for problems in machine learning and data structures and develops new tools for studying resource tradeoffs. Most of these results concern models with query access to the input.On the machine-learning side, we use correlation clustering, a fundamental problem in unsupervised learning, to study the tradeoff between queries and memory. In the random-query model introduced and studied in [Raz-Zhan2020, Dinur2024], we prove the first nontrivial query-space tradeoff for an estimation problem. Earlier techniques for this model rely on Boolean functions with high sensitivity or total influence, whereas estimation problems such as correlation clustering need not have influential input coordinates. Instead, our proof adapts the Fourier-analytic framework used for the streaming lower bound in [Kapralov-Khanna-Sudan2014] to handle noisy instances and repeated queries. We complement this result by proving query lower bounds for correlation clustering in the adjacency-matrix and general-graph models, as well as a strong nonadaptive property-testing lower bound. In separate work, we study the tradeoff between weight precision and network size for ReLU networks computing Boolean functions: allowing unrestricted real weights can exponentially reduce the number of neurons required, while some Boolean functions still require exponentially many neurons even with such weights.On the data-structure side, we study how redundancy—the amount of extra information stored about the input during preprocessing—trades off against the number of probes needed to answer a query in succinct and systematic data structures. The difficulty is that the redundancy can be an arbitrary function of the input. Our general framework handles this through a reduction to a new query-with-sketch model and a min-entropy tool that we develop for that model. As its main application, we prove strong lower bounds for the approximate matrix powering problem. These bounds provide new unconditional evidence for a conjecture of Pătraşcu and Roditty on the space required to answer set-disjointness queries in constant time [Patrascu-Roditty2010]. We also revisit Yao’s implicit membership problem [Yao1981], which asks how universe size, table size, and probe complexity trade off in a restricted full-table model. In this work, I prompted a large language model to generate the proofs in full. We then verified each proof and polished its exposition. The resulting bound substantially improves Yao’s 45-year-old lower bound and is the first quantitative improvement since the problem was introduced.

Organization: 

Contact  Assistant Professor Sumegha Garg

Zoom Link:
https://rutgers.zoom.us/j/5528725019?pwd=SWk2R0h3S1haTW83M0lWRFFIZzl2dz09