Shachar Lovett
where else to find them
what they talk about
where they keep going back
- ITCS2 editions2022–2023
all 6 in the filters
on a stage with
- Jiapeng Zhang3×
- Ian Mertzonce
- Qian Lionce
all 6 in the filters
who talks about the same things
- Jiapeng Zhang3 talks
- Toniann Pitassi5 talks
- Raghu Meka5 talks
- Tushant Mittal2 talks
- Madhur Tulsiani4 talks
- Dor Minzer8 talks
| title | conference | date |
|---|---|---|
| Streaming Lower Bounds for the Needle Problems | Sketching and Algorithm Design 2023 | 2023-10-09 |
Shows a near-tight lower bound: any streaming algorithm with space s needs about t ≈ 1/(s p^2) samples (multipass adds an l factor) to distinguish uniform vs… | ||
| Fractional certificates for bounded functions | ITCS 2023 | 2023-01-10 |
Defines epsilon-fractional certificate complexity and proves that any bounded function f with polynomial degree D satisfies Fc_eps(f) = O(D^8 log^16 n / eps^4)… | ||
| Lifting With Sunflowers | ITCS 2022 | 2022-01-31 |
Proves that many lifting theorems (tree‑like, DAG‑like, depth‑dependent) follow from a single sunflower‑based lemma, replacing lengthy casework with a short… | ||
| Sparse MDS Matrices: Proof of the GM-MDS Conjecture | Interactive Complexity 2018 | 2018-10-15 |
States and proves the GM‑MDS conjecture: any K×N zero pattern that satisfies the combinatorial MDS condition can be completed to an MDS matrix over any field… | ||
| Labeling the Complete Bipartite Graph with No Zero Cycles | Structure vs. Randomness 2017 | 2017-04-10 |
Shachar Lovett, UC San Diego
https://simons.berkeley.edu/talks/shachar-lovett-2017-4-13
Structure vs. Randomness | ||
| Information Theory in Combinatorics I | Information Theory Boot Camp 2015 | 2015-01-13 |
Entropy methods give concrete counting bounds via Shearer's Lemma: if each variable appears in at least k subsets then k·H(all) ≤ sum H(on subsets)… | ||
| Information Theory in Combinatorics II | Information Theory Boot Camp 2015 | 2015-01-13 |
Shachar Lovett, UC San Diego
Information Theory Boot Camp
http://simons.berkeley.edu/talks/shachar-lovett-2015-01-14 | ||
| Information Theory in Computational Complexity III | Information Theory Boot Camp 2015 | 2015-01-13 |
Shachar Lovett, UC San Diego
Information Theory Boot Camp
http://simons.berkeley.edu/talks/shachar-lovett-2015-01-15 | ||
| The Structure of Low Rank Matrices | Neo-Classical Methods in Discrete Analysis 2013 | 2013-12-02 |
Problem: characterize N×N matrices with rank r and a constant fraction of zeros and find how large a zero rectangle must exist. Concrete conjecture: every such… | ||
| nothing matches | ||