Structural Results 2023
2023-07-20..2023-07-27
Berkeley, United States
who it's for
combinatorics researchers, theoretical computer scientists, complexity theorists, additive combinatorics researchers, random graph and probabilistic method researchers, communication complexity researchers
topics
unate k-SAT functions; hypergraph container method; flag algebras sum-of-squares; depth-four parity lower bounds; regularity with VC2-dimension; high-dimensional random geometric graphs; spectral expansion of geometric complexes; Bogolyubov-type results in SL_n(F_q); Heilbronn triangle area bounds; tight space coin problem; sign-rank versus margin separations; Fourier growth of XOR-fibers
| title | author | length |
|---|---|---|
| Nearly all k-SAT Functions are Unate | Yufei Zhao | 01h 05m |
Proves that for every fixed k a 1-o(1) fraction of k-SAT Boolean functions on n variables are unate, resolving the Bollobás–Brightwell–Leader conjecture. The… | ||
| P-smallness of Increasing Families | Jinyoung Park | 58m |
Defines p-smallness as an explicit certificate: an increasing family F is p-small when a cover G satisfies Σ p^{|B|} ≤ 1/2. Presents a theorem giving a… | ||
| Top-Down Lower Bounds for Depth-Four Circuits | Mika Göös | 01h 01m |
New top-down proof shows parity needs size exp(Θ(n^{1/3})) for depth‑4 circuits by combining two concrete tools: a block unpredictability lemma that picks… | ||
| Larger Corner-free Sets in High Dimensions | Lianna Hambardzumyan | 35m |
Presents a concrete improvement over Rankin’s 1961 construction: for k>2 the new protocol yields strictly larger corner-free subsets of [N]^k by shaving… | ||
| An Improved Bound for Regular Partitions of Hypergraph of Bounded VC_2 Dimension | Caroline Terry | 51m |
Shows that a 3‑uniform hypergraph with VC_2-dimension ≤ k admits a Frankl–Rödl style regular decomposition whose number of edge‑colors ℓ is polynomial in 1/ε… | ||
| Testing Thresholds for High-dimensional Sparse Random Geometric Graphs | Siqi Liu | 56m |
Main result: when p = c/n the random geometric graph Geo_d(n,p) becomes statistically indistinguishable from G(n,p) once d ≥ poly(log n), with total variation… | ||
| Higher-dimensional Expansion of Random Geometric Complexes | Tselil Schramm | 01h 04m |
Shows that triangles in a random geometric graph on the D-sphere produce a sparse 2D spectral expander: pick C log n dimensions and edge probability p =… | ||
| A Polynomial Bogolyubov type Result for the Special Linear Group | Guy Kindler | 01h 04m |
Result: for A ⊂ SLn(Fq) of density as small as q^{-c n^2}, the product A A^{-1} A A^{-1} contains a subgroup whose relative density is polynomial in the… | ||
| A New Upper Bound for the Heilbronn Triangle Problem | Cosmin Pohoata | 01h 03m |
Proves that for sufficiently large n every n-point set in the unit square contains a triangle of area < n^{-8/7-1/2000} by combining an incidence-based… | ||
| Tight Space Complexity of the Coin Problem | Sumegha Garg | 52m |
Proves a sharp threshold at c=1/3: read-once branching programs with effective width 1 and recursive AND–OR/majority gadgets achieve O(log n) width to detect… | ||
| Sign-rank vs Margin | Kaave Hosseini | 58m |
Two strong negative answers: small sign-rank does not force small margin because an explicit inner‑product construction (rows/columns are integer vectors)… | ||
| Fourier Growth of XOR-Fibers of Communication Protocols | Uma Girish | 53m |
Proves a tight O(sqrt{d}) bound for level‑1 Fourier growth of XOR‑fibers and an improved O(d^{3/2}) bound for level‑2, conjecturing an optimal O(d · polylog n)… | ||
| Randomized versus Deterministic Decision Tree Size | Nikhil S. Mande | 01h 04m |
Proves that, up to polylog(n) factors, log of deterministic decision tree size is at most the fourth power of the log of bounded‑error randomized size (log^4… | ||
| Structures in Random Graphs: New Connections | Huy Tuan Pham | 01h 03m |
Proves an upper bound on clique and independence numbers in uniformly random Cayley graphs of any finite group of order N at order log N · log log N, tight for… | ||
| Correspondence Colouring of Random Graphs | Liana Yepremyan, Zdenek Dvorak | 01h 00m |
Erdős–Rényi G(n,p) with constant p has correspondence chromatic number O(n/√log n), proved by giving a sufficient condition (a numbers of independent sets… | ||
| Structure Of Boolean Almost Low Degree Functions On The Biased Cube | Yuval Filmus | 57m |
Claims precise structural descriptions: on the p‑biased cube any degree‑d real polynomial f that is ε‑close in L2 to Boolean has (after possibly negating) an… | ||
| nothing matches | ||