Shachar Lovett
University of California-San Diego, CA·Computer Science
Mathematicians and computer scientists often face objects that are too complicated to analyze directly. A powerful response is the "structure versus randomness" paradigm: either find hidden structure in an object that makes it tractable and lets you design fast algorithms for it, or show that the object behaves enough like a random one that random-like properties can be used in place of true randomness.
- Fields
Computer Science
Mathematics & Statistics
- Topics
structure versus randomness
spreadness
mixing
- Grants
- 1 known grant, through Dec 2027
What they work on
- Develop the theory of spreadness, a measure that no structured subset contains too many elements, into a general framework connecting existing structure-versus-randomness arguments.
- Formalize mixing, a measure of how two objects behave jointly under a shared operation, and combine it with spreadness to obtain improved quantitative bounds.
- Apply the new framework to problems in additive combinatorics, which studies additive structure in sets of numbers, and in graph theory.
- Use the spreadness and mixing approach to attack problems in communication complexity, the study of how many bits parties must exchange, and to design fast combinatorial algorithms.
More about the research
In the cleanest situations the two ideas are complements, with randomness appearing exactly where structure is absent. This project develops a new route through that paradigm, aimed at much better quantitative bounds than are currently known.
Why it matters
Sharper quantitative tools for separating structure from randomness could improve bounds on long-standing problems in combinatorics and complexity and speed up widely used combinatorial algorithms. The work also strengthens the bridge between mathematics and theoretical computer science, letting techniques developed in one field be applied in the other.
Known grants
From NIH and NSF research grants. Labs often have other funding we can't see.
Closest labs
Aleksandr Golovnev
Georgetown University, DC·Computer Science·Early-career
Find explicit constructions of rigid matrices, which must have many entries changed to lower their rank, to better understand the power and limits of logarithmic-depth circuits.
Jacob Fox
Stanford University, CA·Mathematics & Statistics
Determine how the number of colors and the structure of hypergraphs, networks whose edges can join more than two points, govern the off-diagonal growth of hypergraph Ramsey numbers.
Thomas Kelly
Georgia Institute of Technology, GA·Mathematics & Statistics
Use randomness and the probabilistic method to prove new results on embedding structures such as Hamilton cycles in graphs and hypergraphs, networks where an edge can join several points.
The school
University of California-San Diego: 84 labs on PI Pages, $1.9B a year on research, 637 research doctorates a year.
Reach out
A start for your email. Fill in the brackets.