Aleksandr Golovnev
Georgetown University, DC·Computer Science·Early-career
Some problems seem to require huge amounts of computation, but proving that no clever shortcut exists is one of the hardest tasks in computer science. Circuit complexity tackles this by modeling computation as circuits of simple logic gates and asking which functions cannot be computed by small circuits.
- Fields
Computer Science
Mathematics & Statistics
- Topics
circuit complexity
circuit lower bounds
computational complexity
- Grants
- 1 known grant, through Feb 2029
What they work on
- 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.
- Develop a new approach to proving lower bounds against constant-depth circuits with counting gates.
- Use circuit-complexity techniques to construct a weak version of a one-way function, a function easy to compute but hard to invert that underlies cryptography.
More about the research
Such 'lower bounds' matter for cryptography, algorithms, discrete mathematics and software verification. Full answers remain out of reach, so researchers prove limits for restricted circuit models. This project aims to prove strong new results of this kind, improving on several decades of work.
Why it matters
This is basic theoretical research on the limits of efficient computation. Stronger circuit lower bounds and weak one-way functions could firm up the mathematical foundations of cryptography, the basis of secure communication. Past results of this kind have found uses across computer science, and new ones could eventually inform algorithms and software verification.
Known grants
From NIH and NSF research grants. Labs often have other funding we can't see.
Closest labs
Shachar Lovett
University of California-San Diego, CA·Computer Science
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.
Vinodchandran Variyam
University of Nebraska-Lincoln, NE·Computer Science
Initiate the study of a "right to forget" data stream model, in which items can be required to be deleted, motivated by privacy concerns and the growth of data generation.
Bhargav Narayanan
Rutgers University-New Brunswick, NJ·Mathematics & Statistics·Early-career
Study up-sets and down-sets in the Boolean hypercube from a probabilistic viewpoint, where they encode events of interest in probabilistic combinatorics and statistical physics.
The school
Georgetown University: 14 labs on PI Pages, $377M a year on research, 206 research doctorates a year.
Reach out
A start for your email. Fill in the brackets.