Yuval Filmus
where else to find them
what they talk about
where they keep going back
- ITCS2 editions2021–2022
all 4 in the filters
on a stage with
- Akshayaram Srinivasanonce
- Andrej Bogdanovonce
- Avi Kaplanonce
all 17 in the filters
who talks about the same things
- Avishay Tal4 talks
- Shay Moran6 talks
- Yuval Ishai8 talks
- Dor Minzer8 talks
- Toniann Pitassi5 talks
- Oded Goldreich4 talks
| title | conference | date |
|---|---|---|
| Structure Of Boolean Almost Low Degree Functions On The Biased Cube | Structural Results 2023 | 2023-07-20 |
Claims precise structural descriptions: on the p‑biased cube any degree‑d real polynomial f that is ε‑close in L2 to Boolean has (after possibly negating) an… | ||
| The Hitting Proof System | Proof Complexity and Meta-Mathematics 2023 | 2023-03-20 |
A hitting refutation is a partition of 0/1^n into subcubes where each subcube’s assignments all falsify a single clause; disjointness is certified by variable… | ||
| Bounded indistinguishability for simple sources | ITCS 2022 | 2022-01-31 |
Shows both positive and negative Braverman-style claims: for constant-degree/local sources constant k suffices to fool simple distinguishers, and depth‑one… | ||
| The entropy of lies: playing twenty questions with a liar | ITCS 2021 | 2021-01-06 |
Distributional 20 Questions with up to K lies requires on average H(mu) + K·H2(mu) yes/no queries, where H(mu) + K·H2(mu) is tight (matching lower bound up to… | ||
| Complexity measures on symmetric group and beyond | ITCS 2021 | 2021-01-06 |
Defines an abstract simplicial complex framework that extends degree, decision tree complexity and sensitivity from the hypercube to domains like the symmetric… | ||
| Explicit SoS lower bounds from high-dimensional expanders | ITCS 2021 | 2021-01-06 |
Constructs deterministic, polynomial-time Max-3-XOR instances from Ramanujan complexes whose true optimum is at most 1 − μ (μ a fixed constant, e.g. ~0.1) yet… | ||
| Shrinkage under random projections, and cubic formula lower bounds in AC^0 | ITCS 2021 | 2021-01-06 |
Proves an n^3 lower bound on De Morgan formula size for an explicit AC^0 function built by composing a small hard gadget F0 with a surjectivity block, using… | ||
| Friedgut-Kalai-Naor for Boolean Functions on S_n | Neo-Classical Methods in Discrete Analysis 2013 | 2013-12-02 |
Extension of the FKN theorem to permutations: a Boolean f on S_n whose projection onto the span of 1-cosets is small-distance from f must be close to a single… | ||
| nothing matches | ||