Makrand Sinha
where else to find them
no profile links on file
what they talk about
where they keep going back
- ITCS2 editions2021–2022
all 4 in the filters
on a stage with
- Daniel Dadushonce
- Haotian Jiangonce
- Neil Olveronce
all 7 in the filters
who talks about the same things
- Raghu Meka5 talks
- Anindya De3 talks
- Gillat Kol5 talks
- Mark Braverman5 talks
- Dor Minzer8 talks
- Yuval Filmus9 talks
| title | conference | date |
|---|---|---|
| Separating Quantum from Classical with k-fold Forrelation and Friends | Beyond the Boolean Cube 2023 | 2023-06-26 |
k-fold Forrelation is easy for quantum machines (about k/2 queries, BQP-complete) but hard for simple classical models: any decision tree or parity decision… | ||
| Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing | ITCS 2022 | 2022-01-31 |
Shows that in a smoothed model (noise whose covariance has nontrivial projection in every direction) the Banaszczyk bound improves to sqrt(log d)+sqrt(log log… | ||
| Query, Communication and Discrepancy | Meet the Fellows Welcome Event | 2021-09-08 |
Shows a concrete k-fold correlation problem that yields a constant vs almost linear separation between quantum and randomized query complexity (previous best… | ||
| Majorizing Measures for the Optimizer | ITCS 2021 | 2021-01-06 |
Proves a constructive version of the majorizing measures duality: a convex program for the Gaussian chaining functional and a simplified dual are within a… | ||
| On Parallelizing Streaming Algorithms | Information Theory in Complexity Theory and Combinatorics 2015 | 2015-04-24 |
Shows a direct-sum lower bound for parallel streaming: for IID streams computing k independent copies requires about k times the average memory under a… | ||
| nothing matches | ||