Emanuele Viola
where else to find them
no profile links on file
what they talk about
where they keep going back
no series more than once — all 6 in the filters
on a stage with
- Ronen Shaltielonce
- W. T. Gowersonce
who talks about the same things
- Ronen Shaltiel2 talks
- Prahladh Harsha4 talks
- Amey Bhangale3 talks
- Uma Girish4 talks
- Ran Raz6 talks
- Edward Pyne2 talks
| title | conference | date |
|---|---|---|
| Average-case Complexity for Polynomials, and All That | Lower Bounds, Learning, and Average-Case Complexity | 2023-02-13 |
Survey of concrete advances and limits: proves an explicit counterexample to the CHLLZ conjecture by showing TRIBES DNF retains large local correlation after… | ||
| Mixing in non-quasirandom groups | ITCS 2022 | 2022-01-31 |
Paper proves concrete communication bounds for the three-party product=1 problem in three non-quasirandom, non-almost-abelian families: affine groups get… | ||
| On Hardness Assumptions Needed for ``Extreme High-End'' PRGs and Fast Derandomization | ITCS 2022 | 2022-01-31 |
Asks whether scaling the Impagliazzo–Wigderson assumption yields an extreme high-end PRG (seed R = (1+o(1))·L, output M ≈ 2^{1−o(1)·L}, total compute ≈… | ||
| Bounded Independence Plus Noise, and the Communication Complexity of Decoding | Interactive Complexity 2018 | 2018-10-15 |
Proves that bounded-independence plus small-noise fools products of K functions once T is about the row length L, giving error exponentially small in T… | ||
| The Complexity of Distributions | Boolean Devices 2018 | 2018-09-10 |
Characterization: any AC0 sampler whose output has min-entropy k > ~sqrt(n) is a convex combination of bit-block sources, so samplable distributions reduce to… | ||
| 3SUM, 3XOR, Triangles | Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015) | 2015-12-08 |
Shows a two-way quantitative reduction: if 3SUM runs in n^{1+ε} then triangle listing on m-edge graphs runs in about m^{4/3 - Θ(ε)}, and conversely Patrascu’s… | ||
| Local Reductions | Connections Between Algorithm Design and Complexity Theory | 2015-09-28 |
Proves a concrete reduction from a time-t computation to 3SAT formulas of quasi-linear size whose clause for index i is computable by a function depending on… | ||
| nothing matches | ||