Interactive Complexity 2018
2018-10-15..2018-10-18
Berkeley, United States
who it's for
theoretical computer scientists, complexity theorists, data structure researchers, streaming algorithms researchers, distributed systems researchers, cryptographers and security researchers, quantum algorithms researchers
topics
explicit hardest halfspace approximation; weak regularity for elimination; triangular discrimination round elimination; quantum query composition with shared inputs; bounded independence plus noise; network coding in undirected graphs; linear sketching over finite fields; strong direct sum randomized queries; composition lower bounds for query complexity; oblivious RAM bandwidth lower bounds; time-space tradeoffs for memory game; sparse MDS matrices and GM-MDS conjecture
| title | author | length |
|---|---|---|
| The Hardest Halfspace | Alexander Sherstov | 01h 05m |
Constructs an explicit hardest halfspace on {0,1}^{2n} whose degree-D polynomial (and rational) pointwise approximation error stays 1 − 2^{-Ω(n/D)}, matching… | ||
| Lower Bounds for Elimination via Weak Regularity | Michal Koucky | 33m |
Proves a quantitative lower bound for elimination: any distributional deterministic protocol for k independent copies must use at least… | ||
| Round Elimination using Triangular Discrimination | Amir Yehudayoff | 34m |
Shows that replacing round elimination with an analysis of distributions using triangular discrimination (Delta) yields stronger, practical lower bounds on… | ||
| Quantum Algorithms for Composed Functions With Shared Inputs | Justin Thaler | 29m |
Shows that composing any outer Boolean F with shared-input OR gates has quantum query complexity ~O(polylog(n) sqrt(n Q(F))) so the bound is the geometric… | ||
| Bounded Independence Plus Noise, and the Communication Complexity of Decoding | Emanuele Viola | 34m |
Proves that bounded-independence plus small-noise fools products of K functions once T is about the row length L, giving error exponentially small in T… | ||
| Network Coding in Undirected Graphs Is Either Very Helpful or Not Helpful at All | Sumegha Garg | 25m |
Main claim: either undirected networks never benefit from coding, or there exist undirected graphs where coding beats flow by a gap that grows to roughly a… | ||
| Advances in Linear Sketching over Finite Fields | Grigory Yaroslavtsev | 56m |
Shows that when there are at least 10·m sequential players and each message is at most C bits one can convert the protocol into a randomized F2 linear sketch… | ||
| Strong Direct Sum for Randomized Query Complexity | Joshua Brody | 33m |
Proves a strong direct sum for randomized query complexity with aborts: computing k independent copies with overall error epsilon requires Θ(k) times the… | ||
| On a Composition Theorem for Randomized Query Complexity | Troy Lee | 36m |
Proves a composition lower bound showing randomized query complexity can drop to R(F)·√R(G) and gives a matching example: an outer relation with R(F)=Θ(√n) and… | ||
| Distributed Interactive Proofs | Rotem Oshman | 33m |
Shows that MAM protocol verifies graph symmetry in O(log n) bits per node by having the prover commit a permutation and a rooted spanning tree, then nodes… | ||
| Yes, There is an Oblivious RAM Lower Bound! | Kasper Green Larsen | 33m |
Shows a concrete lower bound: any online oblivious RAM that hides access patterns against a polynomial-time adversary must incur Ω(log n / m) bandwidth… | ||
| Time-Space Tradeoffs for the Memory Game | Amit Chakrabarti | 31m |
Deterministic algorithms that only compare cards for equality achieve a pass-based tradeoff with a simple upper bound s·T = n^2, and a matching lower bound (up… | ||
| Static Data Structure Lower Bounds Imply Rigidity | Omri Weinstein | 01h 05m |
A formal connection proves that hard linear static data-structure problems correspond to rigid matrices by relating outer dimension (data-structure complexity)… | ||
| Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers | Siva Natarajan Ramamoorthy | 27m |
Proves new non‑adaptive lower bounds in the cell‑probe model using the sunflower lemma: treat each element’s accessed cell set, find a sunflower with P ≈… | ||
| Simulation beats Richness: New Data-Structure Lower Bounds | Arkadev Chattopadhyay | 38m |
Proves average-case lower bounds for Boolean matrix–vector problems by reducing data-structure probes to an asymmetric communication game and a lifting… | ||
| Why Extension-Based Proofs Fail | Faith Ellen | 35m |
Claim: no extension-based proof can establish the impossibility of k‑set agreement for more than k processes. Proof works in the non-uniform iterated immediate… | ||
| Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication | Diptarka Chakraborty | 27m |
Proves a concrete tradeoff in the succinct cell‑probe model: using an information‑theoretic encoding of a hard distribution (one 1 per block) and careful probe… | ||
| Sparse MDS Matrices: Proof of the GM-MDS Conjecture | Shachar Lovett | 01h 06m |
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… | ||
| On the Deterministic Complexity of Counting Events in a Stream | T.S. Jayram | 36m |
Deterministic algorithms that give a constant (2x) multiplicative approximation for counting ones in an insertion-only stream require sublinear but polynomial… | ||
| Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation | Huacheng Yu | 30m |
Fully dynamic streaming and simultaneous-distributed spanning forest problems get tight space and communication lower bounds: randomized linear AGM sketch… | ||
| The Sketching Complexity of Graph and Hypergraph Counting | Michael Kapralov | 34m |
Counts subgraphs in bounded-degree graphs using linear sketches and a colored vertex-sampling estimator, proving space Theta(m / T^{1/μ}) where μ is the… | ||
| Distributed Statistical Estimation of Matrix Products with Applications | Qin Zhang | 30m |
Estimates ℓp norms of C = A·B for binary and integer inputs with explicit communication and round counts: gives a two‑round protocol achieving 1+ε for ℓp (p≥0)… | ||
| Fully Understanding The Hashing Trick | Lior Kamma | 31m |
Gives a tight characterization of when feature hashing preserves L2 norms: if M is at or below the Johnson–Lindenstrauss dimension it fails, if M is much… | ||
| nothing matches | ||