Boaz Barak
where else to find them
mastodon:@boazbaraktcs@sigmoid.social
mastodon:@boazbaraktcs@mastodon.online
what they talk about
where they keep going back
- ITCS2 editions2021–2022
on a stage with
- Chi-Ning Chouonce
- Kunal Marwahaonce
- Xun Gaoonce
who talks about the same things
- Kunal Marwaha3 talks
- Chi-Ning Chou2 talks
- François Le Gall4 talks
- Yuval Filmus9 talks
- Avishay Tal4 talks
- Keren Censor-Hillel2 talks
| title | conference | date |
|---|---|---|
| Classical algorithms and quantum limitations for maximum cut on high-girth graphs | ITCS 2022 | 2022-01-31 |
Shows a concrete limitation: for graphs of girth ≥6 any one-local algorithm (classical or quantum) can only achieve cut fraction 1/2 + C/√D with C ≤ 1/√2 ≈… | ||
| Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits | ITCS 2021 | 2021-01-06 |
Claims a classical algorithm that uses light-cone marginals to sample from shallow random circuits, computes each marginal in poly(n)·2^L time where L is the… | ||
| Circularity Based IO, Part 2 | Simons Institute Workshop: New Developments in Obfuscation | 2020-12-10 |
Claims a construction of indistinguishability obfuscation from LWE plus a strong circular SRL (Shielded Randomness Leakage) heuristic, proving GSW is… | ||
| iO via Functional Encryption: Techniques and Challenges from LWE | Simons Institute Workshop: New Developments in Obfuscation | 2020-12-10 |
Attempts to get functional encryption from LWE alone produce concrete partial results and clear roadblocks: constructions use homomorphic LWE encodings and… | ||
| On the Existence of Optimal Algorithms | Connections Between Algorithm Design and Complexity Theory | 2015-09-28 |
Proposes sum of squares as a candidate “universal” algorithmic template: optimize over degree-d pseudo-distributions (convex, solvable in n^d time) that… | ||
| nothing matches | ||