By Josh Baxt
Shachar Lovett, an associate professor in UC San Diego’s Department of Computer Science and Engineering, has received a Simons Foundation Investigator award, which supports outstanding theoretical scientists in math, physics, astrophysics and computer science. Lovett will receive $100,000 per year over the next five years.
“This Simons award gives me the opportunity to pursue high-risk basic research,” said Lovett. “The beauty is we have the freedom to explore completely new techniques. Many of these are going to fail, but every once in a while, we can develop something that is incredibly useful.”
Structure and Randomness
Lovett wants to understand how specific structures, or the lack of structure, can influence algorithm design
“I investigate the types of structures that are important to understanding various computational problems,” said Lovett. “By understanding the properties of these structures, we can build faster algorithms, analyze when existing algorithms work or show that a problem is highly difficult and that no efficient algorithm can solve it.”
On the other hand, some problems have (or seem like they have) no structure at all. At the extreme, such problems might look completely random. Structure and randomness are complimentary, and Lovett investigates the interplay between them.
“There’s a theory of pseudo-randomness, which says things are not random, but they look random in various ways, and we can utilize pseudo-randomness to complement structure,” said Lovett. “We could use it to design algorithms that are easier to implement or that run faster.”
The Sunflower Conjecture
The Simons award gives Lovett consistent funding to study problems that have stymied mathematicians and computer scientists for years or even decades. He points to the Sunflower Conjecture as a good example.
A sunflower is a collection of sets with a useful property: some elements belong to all the sets (these are called the kernel), and others belong to just one set (these are called petals). But no element belongs to some but not all the sets. For example, the three sets 1,2,3,4; 2,3,5,6 and 2,3,7,8 are a sunflower with kernel 2,3 and petals 1,4; 5,6; and 7,8.
In the 1960s mathematicians discovered that every large collection of sets, no matter how complicated it is, must contain a sunflower. This observation turned out to be extremely useful for many computer science and mathematics problems.
However, the precise size of the collection of sets from which this phenomena stems remained a mystery. The Sunflower Conjecture speculates that there is such a boundary, but for over 60 years, the proof seemed out of reach.
In 2019, Lovett and colleagues from different institutions finally made progress on, getting closer to the conjectured boundary. (As Lovett told Quanta Magazine, “If you have a large enough mathematical object of some nature, there has to be some hidden structure inside it.”)
“We identified techniques developed in the CS theory community to attack this problem, even though it originally comes from pure mathematics,” said Lovett. “We tried different approaches, and they kept failing, but eventually we were able to get these to work. Since then, people have been able to take our techniques and simplify and strengthen them to prove even more results.”
This exemplifies what Lovett wants to achieve: identify problems that defy solution and find creative ways to address them, often by bridging different areas of research within computer science and mathematics.
“The Simons award will give us the resources to address some incredibly challenging problems, helping to invent new techniques and find ways to overcome long-standing problems,” said Lovett.