Gillat Kol
where else to find them
no profile links on file
what they talk about
all 4 in the filters
where they keep going back
- ITCS2 editions2021–2023
on a stage with
all 4 in the filters
who talks about the same things
- Dmitry Paramonov3 talks
- Klim Efremenko5 talks
- Raghuvansh R. Saxena4 talks
- Yuval Filmus9 talks
- Michael Kapralov7 talks
- Ran Raz6 talks
| title | conference | date |
|---|---|---|
| Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds | ITCS 2023 | 2023-01-10 |
Proves that noisy-CAS vs CAS can incur the worst-case slowdown Θ(log n): any adaptive protocol that uses √n rounds on CAS yields an equivalent beeping (OR)… | ||
| Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly | ITCS 2023 | 2023-01-10 |
Claim: p pass streaming algorithms need space Theta(n^{deg(f)}) to compute Max‑CSPf exactly where deg(f) is f's multilinear polynomial degree and p is… | ||
| Computation Over the Noisy Broadcast Channel with Malicious Parties | ITCS 2021 | 2021-01-06 |
Shows a protocol that computes bit‑exchange over a noisy broadcast channel tolerating up to half malicious parties while cutting per‑player communication from… | ||
| Exponential Separation of Information and Communication | Information Theory in Complexity Theory and Combinatorics 2015 | 2015-04-24 |
Claim: there is an explicit search problem and distribution mu for which the information cost O(k) vs communication ≥ 2^k gap holds, so transcripts cannot… | ||
| Lucky Talk: Exponential Separation of Information and Communication | Information Theory in Complexity Theory and Combinatorics 2015 | 2015-04-24 |
Constructs a boolean function on inputs that label every vertex of a complete binary tree with 2^{4^k} multilayers, grouping every 100k levels into a… | ||
| nothing matches | ||