Information Theory Boot Camp 2015
2015-01-13..2015-01-16
Berkeley, United States
| title | author | length |
|---|---|---|
| Information Theory in Computational Complexity I | Jaikumar Radhakrishnan | 01h 04m |
Defines protocols as binary trees and proves for the equality function that deterministic complexity = N by showing every 1 on the N×N matrix needs its own… | ||
| Coding for Modern Distributed Storage Systems I | Parikshit Gopalan | 01h 01m |
Introduces a formal data locality R and proves any linear code with that locality needs length at least K + ceil(K/R) + D − 2, so locality forces a roughly… | ||
| Distribution Estimation and Applications I | Alon Orlitsky | 01h 10m |
Establishes concrete minimax rates and practical reductions: empirical frequencies give L1 risk Θ(√(K/N)) and KL risk ≈ (K−1)/(2N), so naive IID learning needs… | ||
| Information Theory in Combinatorics I | Shachar Lovett | 01h 14m |
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 | Shachar Lovett | 01h 06m |
Shachar Lovett, UC San Diego
Information Theory Boot Camp
http://simons.berkeley.edu/talks/shachar-lovett-2015-01-14 | ||
| Coding for Modern Distributed Storage Systems II | Parikshit Gopalan | 01h 04m |
Continues the LRC story with explicit constructions and a concrete failure model: a Reed–Solomon variant picks a degree set skipping every (R+1)th monomial to… | ||
| Polar Codes I | Erdal Arikan | 01h 09m |
Transforms X^n by the Kronecker power matrix F (Un = Xn F^{⊗m}) over GF(2) and proves the conditional entropies of U_i polarize to 0 or 1: for any fixed δ the… | ||
| Information Theory in Computational Complexity II | Jaikumar Radhakrishnan | 01h 11m |
Proves that the randomized communication complexity of Disjointness is Ω(N) by reducing the N-bit problem to a single-bit AND and lower-bounding the… | ||
| Information Theory in Computational Complexity III | Shachar Lovett | 01h 03m |
Shachar Lovett, UC San Diego
Information Theory Boot Camp
http://simons.berkeley.edu/talks/shachar-lovett-2015-01-15 | ||
| Coding for Modern Distributed Storage Systems III | Alex Dimakis | 01h 03m |
Shows a concrete 4,2 MDS construction that repairs a single lost symbol by transferring 1.5 symbols using sub-packetization and interference alignment, and… | ||
| Distribution Estimation and Applications II | Alon Orlitsky | 01h 18m |
Estimators for combined probabilities (s0, s1, …) use Poissonization and show Good–Turing is unbiased: its expected g_mu equals E[s_mu], fixing empirical… | ||
| Polar Codes II | Erdal Arikan | 01h 01m |
Shows how N independent copies of a binary DMC are combined by a one‑to‑one transform and split via the chain rule into synthetic bit‑channels whose capacities… | ||
| Information Theory in Computational Complexity IV | Jaikumar Radhakrishnan | 01h 09m |
Shows the exact equivalence between formula depth and communication cost via the Karchmer–Wigderson game and uses that to prove a concrete lower bound: the… | ||
| Coding for Modern Distributed Storage Systems IV | Alex Dimakis | 49m |
Covers regenerating codes, then formalizes locality R (a symbol reconstructible from R others) and proves the distance tradeoff that generalizes the Singleton… | ||
| Distribution Estimation and Applications III | Alon Orlitsky | 01h 05m |
Establishes concrete limits and algorithms: empirical frequency yields L1 error roughly sqrt(k/n) so sample complexity grows quadratically in k; worst-case… | ||
| Polar Codes III | Erdal Arikan | 01h 14m |
Construction uses repeated Kronecker powers of the 2×2 binary matrix F to build length-N polar transforms; encoding and decoding run in N log N… | ||
| nothing matches | ||