Understanding Discrepancy Minimization in Combinatorial Concepts
Explore the intriguing world of Discrepancy Minimization through concepts like walking on the edges, subsets coloring, arithmetic progressions, and more. Delve into fundamental combinatorial concepts and complexity theory to understand the significance of Discrepancy theory in various fields. Discover the implications of Spencers' Six Sigma Theorem and the ongoing research and conjectures in the field of Discrepancy theory.
- Discrepancy Minimization
- Combinatorial Concepts
- Complexity Theory
- Spencers Six Sigma Theorem
- Computation Geometry
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Discrepancy Minimization by Walking on the Edges Raghu Meka (IAS & DIMACS) Shachar Lovett (IAS)
Discrepancy Subsets ?1,?2, ,?? [?] Color with 1 or -1 to minimize imbalance 1 2 3 4 5 1 * 1 1 * 1 1 * 1 1 2 3 4 5 1 * 1 * 1 1 1 1 1 1 1 1 1 * 1 * 1 1 1 * 1 3 1 1 * 1 1 * * * * 1 1 1 * * 1 1 1 * * * 1 1 0 1
Discrepancy Examples Fundamental combinatorial concept Arithmetic Progressions Roth 64: (?1/4) Matousek, Spencer 96: (?1/4)
Discrepancy Examples Fundamental combinatorial concept Halfspaces Alexander 90: Matousek 95:
Discrepancy Examples Fundamental combinatorial concept Axis-aligned boxes Beck 81: Srinivasan 97:
Why Discrepancy? Complexity theory Communication Complexity Computational Geometry Pseudorandomness Many more!
Spencers Six Sigma Theorem Six standard deviations suffice Spencer 85: System with n sets has discrepancy at most . Central result in discrepancy theory. Beats random: Tight: Hadamard.
A Conjecture and a Disproof Spencer 85: System with n sets has discrepancy at most . Non-constructive pigeon-hole proof Conjecture (Alon, Spencer): No efficient algorithm can find one. . Bansal 10: Can efficiently get discrepancy
This Work New elemantary constructive proof of Spencer s result Main: Can efficiently find a coloring with discrepancy ? ? . Truly constructive Algorithmic partial coloring lemma Extends to other settings EDGE-WALK: New algorithmic tool
Beck-Fiala Setting Each element occurs in at most ? sets 1 2 3 4 5 1 * 1 * 1 1 * 1 * Beck-Fiala 80: 2? Srinivasan 97: ?( ?(log n)) (non-algorithmic) * * 1 * 1 * Banszczyk 98: ?( ? log ?) (non-algorithmic) * 1 * * * * 1 * * 1
Beck-Fiala Setting Each element occurs in at most ? sets Thm: Can efficiently find a coloring with discrepancy ?( ? (log?)). Matches Bansal 10
Outline 1. Partial coloring Method 2. EDGE-WALK: Geometric picture 3. Analysis of algorithm
Partial Coloring Method Beck 80: find partial assignment with < ?/2 zeros 1 -1 1 1 -1 1 * 1 * 1 1 1 1 1 1 1 1 1 1 1 1 -1 0 0 0 1 * 1 * 1 1 * 1 1 1 1 0 -1 1 * 1 * 1 1 1 1 1 * 1 1 * * * * * * 1 1 1 * 1 1 1 1 1 1 * 1 1 * * * * * * 1 1 1 1 1 1 1 1 1 1 * 1 * * * * * * 1 1 * * * * 1 1 1 * * * * 1 1 * 1 1 1 1 1 1 * * 1 1 * 1 1 1 * * 1 1 1 1 * 1 1 * 1 1 1 1 1 1
Partial Coloring Method Input: Output: Focus on m = n case. Lemma: Can do this in randomized time.
Outline 1. Partial coloring Method 2. EDGE-WALK: Geometric picture 3. Analysis of algorithm
Discrepancy: Geometric View Subsets ?1,?2, ,?? [?] Color with 1 or -1 to minimize imbalance 1 2 3 4 5 3 1 1 0 1 1 * 1 * 1 * 1 1 * * 1 1 1 * 1 1 * 1 1 * * 1 1 1 1 3 1 1 0 1 1 -1 1 1 -1
Discrepancy: Geometric View Vectors ?1,?2, ,?? 0,1?. Want 1 2 3 4 5 3 1 1 0 1 1 * 1 * 1 * 1 1 * * 1 1 1 * 1 1 * 1 1 * * 1 1 1 1 1 -1 1 1 -1
Discrepancy: Geometric View Vectors ?1,?2, ,?? 0,1?. Want Polytope view used earlier by Gluskin 88. Goal: Find non-zero lattice point inside
Edge-Walk Claim: Will find good partial coloring. Goal: Find non-zero lattice point in Start at origin Gaussian walk until you hit a face Gaussian walk within the face
Edge-Walk: Algorithm Gaussian random walk in subspaces Subspace V, rate ? Gaussian walk in V Standard normal in V: Orthonormal basis change
Edge-Walk Algorithm Discretization issues: hitting faces Might not hit face Slack: face hit if close to it.
Edge-Walk: Algorithm Input: Vectors ?1,?2, ,??. Parameters: ?, , ? ? , ? = 1/?2 1. ?0= 0. For ? = 1, ,?. 2. ????= Cube faces nearly hit by ??. ?????= Disc. faces nearly hit by ??. ??= Subspace orthogonal to ????,?????
Edge-Walk: Intuition Discrepancy faces much farther than cube s Pr ???? ??? ? ????.???? Pr[ ???? ??? ? ???? ?] exp 1002. Pr ???? ??? ? ????.???? Pr ???? ??? ? ???? ???? exp 1 . Hit cube more often! 1
Outline 1. Partial coloring Method 2. EDGE-WALK: Geometric picture 3. Analysis of algorithm
Edge-Walk: Analysis Lem: For with prob 0.1 and
Edge-Walk Analysis Claim 1: Never cross polytope. Claim 2: Number of disc. faces hit ?. Win-Win: Hit many cube faces or grow
Edge-Walk Analysis Claim 1: Never cross polytope Must make a big jump Unlikely: ? ? ?
Edge-Walk Analysis Claim 2: Number of disc. faces hit ?. Small progress each step Martingale tail bound: ? < ?,? = 1/?^2. Linearity of expectation
Edge-Walk Analysis Claim 3: Hit many cube faces - ( 2 norm)2 grows dimension of subspace Final dimension small:
Main Partial Coloring Lemma Th: Given ?1, ,??, thresholds ?1,?2, ??, Can find ? 1,1?with 1. 2. Algorithmic partial coloring lemma
Summary 1. Edge-Walk: Algorithmic partial coloring lemma Spencer s Theorem 2. Recurse on unfixed variables Beck-Fiala setting similar
Open Problems Q: Beck-Fiala Conjecture 81: Discrepancy ?( ?) for degree t. Some promise: our PCL stronger than Beck s Q: Other applications? General IP s, Minkowski s theorem? Constructive version of Banszczyk s bound?
