Russell Impagliazzo
where else to find them
no profile links on file
what they talk about
all 6 in the filters
where they keep going back
- ITCS2 editions2021–2023
all 7 in the filters
on a stage with
- Adam R. Klivansonce
- Fanny Yangonce
- Florent Krzakalaonce
all 9 in the filters
who talks about the same things
- Noah Fleming6 talks
- Toniann Pitassi5 talks
- Daniel Mitropolsky2 talks
- Yuval Filmus9 talks
- Robert Robere5 talks
- Takeshi Tsukada16 talks
| title | conference | date |
|---|---|---|
| Panel on the future of scientific research and education | Unknown Futures of Generalization 2024 | 2024-12-02 |
A live panel debates which research skills survive widespread LLM use and gives concrete examples: a student-run “Resurrected Scientists” ChatGPT experiment… | ||
| Cryptographic Hardness of Correlated Sampling | Minimal Complexity Assumptions for Cryptography 2023 | 2023-05-01 |
Shows that converting perfect generalization (or stability) into replicability hinges on correlated sampling and cryptography: a white box correlated sampling… | ||
| Lower Bounds Against PC With Extension Variables | Proof Complexity and Meta-Mathematics 2023 | 2023-03-20 |
Proves a concrete size lower bound for Polynomial Calculus over F_p (PCR): for every prime p, n and κ = O(log n) there is an explicit unsatisfiable polynomial… | ||
| TFNP Characterizations of Proof Systems and Monotone Circuits | ITCS 2023 | 2023-01-10 |
Paper proves necessary and sufficient conditions for when TFNP classes correspond to proof systems and to monotone-circuit models, and constructs a formal… | ||
| Hypotheses about Satisfiability and their Consequences | 50 Years of Satisfiability: The Centrality of SAT in the Theory of Computing | 2021-02-11 |
Proposes the Exponential Time Hypothesis (3‑SAT needs 2^{c n} time for some c>0) and the Strong ETH (limiting exponent →1), proves a sparsification lemma that… | ||
| Comparing computational entropies below majority (or: When is the dense model theorem false?) | ITCS 2021 | 2021-01-06 |
Shows explicit separations proving the dense model theorem false below majority: constructions of delta-dense distributions that are pseudorandom for small… | ||
| Algorithmic Dense Model Theorems and Weak Regularity | Structure vs. Randomness 2017 | 2017-04-10 |
Claims a tight equivalence between hardcore lemmas, dense model theorems, and weak regularity, and gives algorithmic dense model theorem and weak regularity… | ||
| Boolean Hardness to Randomization | Fine-Grained Complexity and Algorithm Design Boot Camp 2015 | 2015-08-31 |
Shows a blueprint that converts a worst‑case hard Boolean function into a pseudorandom generator g so that any small circuit that distinguishes g’s outputs… | ||
| Derandomization to Boolean Circuit Lower Bounds | Fine-Grained Complexity and Algorithm Design Boot Camp 2015 | 2015-08-31 |
Main claim: any general derandomization of probabilistic algorithms forces nontrivial nonuniform lower bounds, and conversely strong circuit lower bounds yield… | ||
| The Easy Witness Lemma | Fine-Grained Complexity and Algorithm Design Boot Camp 2015 | 2015-08-31 |
Shows that a weakening of Natural Proofs — a quasi‑natural property (constructive, nonempty but only occasionally large) — is essentially equivalent to circuit… | ||
| Connections Between Hardness and Randomness in the Algebraic Setting | Fine-Grained Complexity and Algorithm Design Boot Camp 2015 | 2015-08-31 |
Shows that derandomizing low-formal-degree PIT is essentially equivalent to proving algebraic circuit lower bounds: a polynomial-size, low-degree algebraic… | ||
| nothing matches | ||