Spencer's theorem in nearly input-sparsity time

Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

Type: Book-Chapter

Publication Date: 2023-01-01

Citations: 0

DOI: https://doi.org/10.1137/1.9781611977554.ch152

Abstract

A celebrated theorem of Spencer states that for every set system S1,…, Sm ⊆ [n], there is a coloring of the ground set with {±1} with discrepancy . We provide an algorithm to find such a coloring in near input-sparsity time Õ(n + Σi=1m|Si|)

Locations

arXiv (Cornell University) - View - PDF
Society for Industrial and Applied Mathematics eBooks - View

Similar Works

Action	Title	Year	Authors
+	Spencer's theorem in nearly input-sparsity time	2022	Vishesh Jain Ashwin Sah Mehtaab Sawhney
+	Fast Discrepancy Minimization with Hereditary Guarantees	2023	Kasper Green Larsen
+	Fast Discrepancy Minimization with Hereditary Guarantees	2022	Kasper Green Larsen
+	Linear-Sized Sparsifiers via Near-Linear Time Discrepancy Theory	2023	Arun Jambulapati Victor Reis Kevin Tian
+	A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension	2013	Esther Ezra
+	Tight Hardness Results for Minimizing Discrepancy	2011	Moses Charikar Alantha Newman Aleksandar Nikolov
+ PDF Chat	A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension	2016	Esther Ezra
+ PDF Chat	Linear-Sized Sparsifiers via Near-Linear Time Discrepancy Theory	2024	Arun Jambulapati Victor Reis Kevin Tian
+	Colorings with Low Discrepancy	2011	Bernd Gärtner Jiřı́ Matoušek
+	The Berman-Hartmanis Conjecture and Sparse Sets	1998	Uwe Schöning Randall Pruim
+	A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension	2013	Esther Ezra
+	Deterministic Discrepancy Minimization	2011	Nikhil Bansal Joel Spencer
+	Constructive Discrepancy Minimization with Hereditary L2 Guarantees	2017	Kasper Green Larsen
+ PDF Chat	An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound	2019	Nikhil Bansal Daniel Dadush Shashwat Garg
+	Discrepancy Without Partial Colorings	2014	Nicholas J. A. Harvey Roy Schwartz Mohit Singh
+ PDF Chat	An SDP-based algorithm for linear-sized spectral sparsification	2017	Yin Tat Lee He Sun
+	Constructive Algorithms for Discrepancy Minimization	2010	Nikhil Bansal
+	Constructive Algorithms for Discrepancy Minimization	2010	Nikhil Bansal
+	A Stress-Free Sum-of-Squares Lower Bound for Coloring	2021	Pravesh K. Kothari Peter Manohar
+	Discrepancy and Sparsity	2021	Mario Grobler Yiting Jiang Patrice Ossona de Mendez Sebastian Siebertz Alexandre Vigny

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (17)

Action	Title	Year	Authors
+	Efficient Algorithms for Discrepancy Minimization in Convex Sets	2014	Ronen Eldan Mohit Singh
+	Roth’s estimate of the discrepancy of integer sequences is nearly sharp	1981	József Beck
+ PDF Chat	Constructive Discrepancy Minimization by Walking on the Edges	2015	Shachar Lovett Raghu Meka
+	EXTREMAL PROPERTIES OF ORTHOGONAL PARALLELEPIPEDS AND THEIR APPLICATIONS TO THE GEOMETRY OF BANACH SPACES	1989	E. D. Gluskin
+	“Integer-making” theorems	1981	József Beck Tibor Fiala
+ PDF Chat	Constructive Algorithms for Discrepancy Minimization	2010	Nikhil Bansal
+ PDF Chat	Constructive Discrepancy Minimization for Convex Sets	2017	Thomas Rothvoß
+ PDF Chat	Nearly linear-time packing and covering LP solvers	2018	Zeyuan Allen-Zhu Lorenzo Orecchia
+	Balancing vectors and Gaussian measures of n-dimensional convex bodies	1998	BanaszczykWojciech
+ PDF Chat	Coordinate Methods for Matrix Games	2020	Yair Carmon Yujia Jin Aaron Sidford Kevin Tian