Information Theory in Complexity Theory and Combinatorics 2015
2015-04-24..2015-04-27
Berkeley, United States
| title | author | length |
|---|---|---|
| Tutorial on Coding for Interactive Communication: Introduction and Overview | Anup Rao | 01h 17m |
Tutorial explains a concrete simulation: reduce arbitrary interactive protocols to the pointer-jumping hard case, protect each step with a tree code and prove… | ||
| Exponential Separation of Information and Communication | Gillat Kol | 36m |
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… | ||
| Small Value Parallel Repetition for General Games | Ankit Garg | 27m |
Proves a general parallel-repetition bound showing that when a game has initial value 1 − ε the value after n independent repetitions falls exponentially in n… | ||
| Answering FAQs in CSPs, PGMs, Databases, Logic and Matrix Operations | Atri Rudra | 31m |
Presents a single algorithmic framework that expresses sum‑product queries (FAQs) over hypergraphs and specializes to joins, exact inference in PGMs, FFT and… | ||
| Streaming Lower Bounds for Approximating MAX-CUT | Michael Kapralov | 30m |
Proves any single-pass streaming algorithm that beats a trivial 2-approximation for MAX-CUT (achieving 2−ε) requires Ω(√n) space, even when edges arrive in a… | ||
| Extended Formulations and Information Complexity | Ankur Moitra | 29m |
Defines non-negative rank of the slack matrix and uses an entropy sampling reduction to show any factorization with R terms would let one sample a size-3^n… | ||
| Welfare Maximization with Limited Interaction: Information and Communication in Economics | Omri Weinstein | 33m |
Proves a round-vs-communication lower bound for multi-party matching: with B bits per player per round and R fixed rounds any protocol only achieves an… | ||
| A New Look at Gallager's Bounds | Nati Linial | 30m |
Random LDPC codes are constructed from a parity-check matrix with J ones/column and K ones/row built by J random permutations of block identity matrices, J ≥… | ||
| Tutorial on Efficient Coding for Interactive Communication via List Decoding | Bernhard Haeupler | 01h 19m |
Claims an adaptive interactive protocol tolerates up to 2/7 error rate (tight) while non‑adaptive protocols hit a 1/4 barrier, and achieves this by combining… | ||
| Relative Discrepancy Does Not Separate Information and Communication Complexity | Sophie Laplante | 36m |
Linear-program comparisons produce a concrete collapse: a change-of-variables maps relative discrepancy solutions to feasible points for the relaxed partition… | ||
| Internal Compression of Protocols to Entropy | Shay Moran | 25m |
Claims an interactive compression method that matches external entropy up to a constant (empirically about 1.82), and an internal compression that replaces the… | ||
| Lucky Talk: Exponential Separation of Information and Communication | Gillat Kol | 33m |
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… | ||
| Information Complexity for Multi-Party NIH Communication | Rotem Oshman | 27m |
Proves that k‑party number‑in‑hand disjointness on n coordinates has an Ω(n log k) communication lower bound under shared blackboard by first applying a… | ||
| Upper Bound on List-decoding Radius of Binary Codes | Yury Polyanskiy | 31m |
Proves a new upper bound on the list‑decoding radius for odd list sizes L≥3 and beats Blinovsky’s 1986 bound on a nontrivial rate interval, while leaving other… | ||
| On the Communication Complexity of Sparse Set Disjointness | Gábor Tardos | 34m |
Establishes tight trade-offs for k-sparse set disjointness: a simple bias-tweak of the Håstad–Wigderson-style protocol yields O(k) communication and log k… | ||
| Some Novel Computational Models to Think About | D Sivakumar | 31m |
Surveys practical computation models and gives concrete payoffs: algorithms for frequency moments reach surprising low-space single-pass bounds while matching… | ||
| Tutorial on Capacity in Coding for Interactive Communication (Part 1 of 2) | Ran Raz | 43m |
Ran Raz, Weizmann Institute and Institute for Advanced Study
Information Theory in Complexity Theory and… | ||
| Tutorial on Capacity in Coding for Interactive Communication (Part 2 of 2) | Bernhard Haeupler | 40m |
Provides an explicit coding scheme that attains overhead 1+Θ(√ε) by grouping communication into blocks of length block length b ≈ 1/√ε, hashing complete… | ||
| An Information Theoretic View of Hypercontractivity | Ehud Friedgut | 38m |
Provides an entropy-based proof of Beckner’s hypercontractive inequality (primal) and revisits a 2001 entropy proof of the dual that yields a 28^(1/4) base… | ||
| Equality, Revisited | Hartmut Klauck | 29m |
Gives a simpler proof via killing correlations that reproduces the Θ(√n) private-coin SMP lower bound for Equality by showing encoded messages become… | ||
| Lucky Talk: Upper Bound on List-decoding Radius of Binary Codes | Yury Polyanskiy | 31m |
Claim: an upper bound on the list-decoding radius τ_L is given by an explicit function G1 of ψ0 (ψ0 = 1/2 − √(β(1−β)) from the LP1 Plotkin point), derived by… | ||
| Non-Signalling Parallel Repetition Using de Finetti Reductions | Thomas Vidick | 31m |
Proves parallel repetition bounds for no-signalling strategies by applying finite de Finetti reductions to permutation‑invariant strategy distributions, then… | ||
| Limits to Efficient Preprocessing | Andrew Drucker | 32m |
Shows that OR-SAT and AND-SAT do not admit polynomial kernels unless NP ⊆ coNP/poly, and extends the impossibility to randomized and a defined quantum… | ||
| Parallel Repetition for Entangled Games via Fast Quantum Search | Henry Yuen | 29m |
Proves for free (product-input) games a stronger parallel-repetition upper bound: the entangled value falls like entangled value ≤ (1−ε^{3/2})^{Θ(n/s)} where ε… | ||
| Do Read Errors Matter for DNA Assembly? | Thomas Courtade | 35m |
Assumes a dense read model (a read starting at every base, cyclic) and adversarial erasures (≤ D erasures per read and ≤ D erasures per base, i.e. erasure rate… | ||
| Tutorial on List Decodable Coding Schemes and Interactive Communication in Networks (Part 1 of 2) | Klim Efremenko | 38m |
Shows a protocol that uses list decoding/list recovery to solve pointer‑jumping: given Alice and Bob’s layered edge sets the protocol outputs a small list of… | ||
| Tutorial on List Decodable Coding Schemes and Interactive Communication in Networks (Part 2 of 2) | Ran Gelles | 44m |
Survey of multiparty interactive coding gives concrete conversions and limits: a randomized-BSC synchronous compiler yields a resilient protocol that uses O(t… | ||
| Information Theory and Polyhedral Combinatorics | Sebastian Pokutta | 33m |
Describes a concrete pipeline that lowers bounds on LP sizes by turning an optimization problem into its slack matrix, interpreting that matrix as a… | ||
| Information Theory and Additive Combinatorics | Mokshay Madiman | 31m |
Shows two concrete claims: on Z and R there exist IID finite-entropy variables for which H(X−X′) − H(X+X′) is arbitrarily large gap, yet after subtracting H(X)… | ||
| Lucky Talk: An Information Theoretic View of Hypercontractivity | Ehud Friedgut | 32m |
Proves a fractional Shearer inequality for the t=2 case by partitioning the ground set, encoding weighted Fourier coefficients as integer multiplicities, and… | ||
| On Parallelizing Streaming Algorithms | Makrand Sinha | 25m |
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… | ||
| Streaming Interactive Proofs and Arthur-Merlin Communication | Amit Chakrabarti | 32m |
Claims a verifier with only polylog space can answer point membership and nearest-neighbor queries by turning the stream into a multilinear polynomial, storing… | ||
| A Communication Game Approach to the Sensitivity Conjecture | Mike Saks | 34m |
Defines a streaming communication game where one player writes bits into positions revealed by a random permutation and the last position is forced to be a… | ||
| Deterministic Communication vs. Partition Number | Toniann Pitassi | 32m |
Proves a superlinear gap: deterministic communication complexity grows like (log partition number)^{1.5} (up to polylogs) and for the one-rectangle measure… | ||
| Interactive and Amortized Communication – An Information Theoretic Perspective | Alon Orlitsky | 36m |
Examines concrete gaps: the indexing (league) example shows one-way needs ~log n bits while a two-message protocol sends one index plus a single bit so… | ||
| Lucky Talk: A Communication Game Approach to the Sensitivity Conjecture | Mike Saks | 37m |
Defines a streaming game where an input permutation σ arrives and bits are irrevocably written to positions; Bob sees the final vector and must output a set… | ||
| Counting Distinct Elements in the Message Passing Model | David P. Woodruff | 26m |
Proves an Omega communication lower bound: the randomized distributional sum‑disjointness task in the k‑party point‑to‑point model requires omega(n k) bits by… | ||
| Superlinear Lower Bounds for Multipass Graph Processing | Krzysztof Onak | 35m |
Shows that for P passes several basic graph tasks — testing whether two fixed vertices are within distance 2P+1, deciding perfect matching, and s–t… | ||
| Tribes is Hard in the Message Passing Model | Arkadev Chattopadhyay | 34m |
Shows that Tribes in the coordinator (star) message‑passing model has randomized communication Theta(nk) for the typical setting m = l = √n, so the naive… | ||
| Combinatorial Proofs of Concentration Bounds | Thomas Holenstein | 32m |
Gives a direct combinatorial proof that for n independent fair bits the chance of ≥ (1+ε)n/2 ones is ≤ exp(-ε^2 n/10) by choosing a random subset M of size m ≈… | ||
| How to Compress Asymmetric Communication | Sivaramakrishnan Natarajan Ramamoorthy | 27m |
Provides two concrete compression schemes and one explicit bound that helps when information is lopsided: converts any protocol into a bounded‑round “guess K… | ||
| On Geometric Measures for Information Complexity | T.S. Jayram | 29m |
Defines a transcript wave function by taking square roots of transcript probabilities and uses the induced Hellinger (L2) distance, then proves negative‑type… | ||
| Information Complexity is Computable | Mark Braverman | 29m |
Proves zero‑error information complexity is algorithmically approximable: given f on n×m and distribution μ produce a δ‑approximation by restricting to… | ||
| nothing matches | ||