Neo-Classical Methods in Discrete Analysis 2013
2013-12-02..2013-12-06
Berkeley, United States
as the organisers put it
This workshop will focus on future directions in discrete analysis. These include non-commutative Fourier analysis, representation theory techniques, and techniques from additive combinatorics. The workshop topics include basic theoretical questions, as well as applications to extremal combinatorics, theoretical computer science and social choice. The workshop will include some “visionary” talks focusing on unexplored directions. Enquiries may be sent to the organizers at this address.
who it's for
discrete analysts, theoretical computer scientists, additive combinatorics researchers, harmonic analysts, representation theorists, graph theorists, coding theorists, computational complexity researchers
topics
non-commutative Fourier analysis; representation theory of S_n; quantitative idempotent theorems; Boolean Fourier spectrum structure; Gowers regularity lower bounds; algorithmic polynomial regularity; Green-Tao relative Szemeredi theorem; ultraproducts in combinatorics; undecidability of graph homomorphism inequalities; non-commutative algebraic complexity; small lifts of expander graphs; Gowers-norm Reed-Muller decoding
| title | author | length |
|---|---|---|
| Threshold, Influence, Noise, and Discrete Harmonic Analysis | Gil Kalai | 44m |
Asks when near-equality in Harper’s edge-expansion bound actually forces structure: for muP(f) = T and P·I_P(f) within constant of the T·log_P(T) optimum… | ||
| Structure of the Fourier Spectrum of Boolean Functions and Complexity | Ben Lee Volk | 39m |
Claim: Boolean f with small spectral norm (L1 ≤ M) decomposes as a ± sum of indicators of affine subspaces (Green–Sanders), with number of terms bounded by a… | ||
| Quantitative Aspects of the Idempotent Theorem | Tom Sanders | 57m |
Proves a quantitative idempotent theorem: an integer‑valued (or ±1) function with small Fourier algebra norm m decomposes as a signed sum of few subgroup coset… | ||
| Families of Permutations with Forbidden Intersection-sizes | David Ellis | 57m |
Conjecture: for fixed t and n sufficiently large, the largest t-intersecting family of permutations has size (n−t)! and equality is achieved by t-cosets… | ||
| Friedgut-Kalai-Naor for Boolean Functions on S_n | Yuval Filmus | 53m |
Extension of the FKN theorem to permutations: a Boolean f on S_n whose projection onto the span of 1-cosets is small-distance from f must be close to a single… | ||
| A Short Proof of Gowers' Lower Bound for the Regularity Lemma | Asaf Shapira | 49m |
Constructs a weighted complete graph with edge weights in [0,1], builds a sequence of partitions X0,X1,... whose cluster counts grow as a tower, then runs 1/√ε… | ||
| Carries and Cocycles | Persi Diaconis | 52m |
Adds digits produce carries with probability 1/2 − 1/(2b) (45% when b = 10); choosing balanced coset representatives cuts forced carries to (b^2 − 1)/4 (≈… | ||
| The Green-Tao Theorem and a Relative Szemeredi Theorem | Yufei Zhao | 48m |
Proves a relative Szemerédi result that removes the correlation condition from Green–Tao and replaces Gowers uniformity by a cut norm dense model, so fewer… | ||
| Algorithmic Regularity for Polynomials and Applications | Arnab Bhattacharyya | 50m |
Randomized polynomial-time algorithms find an explicit degree-(D−1) polynomial factor that exactly generates any biased degree-D polynomial over… | ||
| Ultraproducts as a Bridge Between Discrete and Continuous Analysis | Terry Tao | 01h 05m |
Ultraproducts convert sequences of finite/discrete objects into a single canonical continuous limit by choosing a non-principal ultrafilter and forming… | ||
| Undecidability of Linear Inequalities Between Graph Homomorphism Densities | Hamed Hatami | 49m |
Proves that deciding whether a linear inequality between graph homomorphism densities holds for all graphs is undecidable. Proof reduces… | ||
| Non-commutative Computation | Avi Wigderson | 55m |
Survey of concrete results and open problems in non-commutative algebraic complexity: proves exponential formula lower bounds (Nisan-style) for some explicit… | ||
| Small Lifts of Expander Graphs are Expanding | Alexandra Kolla | 46m |
Claim: random two-lifts (and more generally k‑shift lifts) preserve expansion: new eigenvalues of the lift have spectral radius bounded by about O(Lambda)… | ||
| Building Monotone Expanders | Amir Yehudayoff | 53m |
Constructs explicit constant-degree monotone expanders by first building a continuous monotone expander on [0,1] from a finite set of SL(2,R) Möbius maps (take… | ||
| The Structure of Low Rank Matrices | Shachar Lovett | 52m |
Problem: characterize N×N matrices with rank r and a constant fraction of zeros and find how large a zero rectangle must exist. Concrete conjecture: every such… | ||
| Counting Sumsets and Applications | Ben Green | 49m |
Count of A ⊂ [N] with |A| = k and |A+A| ≤ Kk is log‑asymptotically given by the product (Kk/2 choose k) · N^K, with the progression construction dominating… | ||
| Incidence Geometry and Applications to Theoretical Computer Science | Shubhangi Saraf | 47m |
Shows quantitative Sylvester–Galai bounds: δ-configurations have dimension O(1/δ) (tight), derived from rank bounds for design matrices over characteristic… | ||
| Laplacian Eigenvalues, Metric Uniformization, and Incidence Geometry | James Lee | 51m |
Proves the graph analogue of uniformization statements by constructing a vertex-weight metric (shortest-path lengths equal vertex-weight sums) whose dual is a… | ||
| Hardness Amplification and the Approximate Degree of Constant-Depth Circuits | Justin Thaler | 47m |
Shows a lossless linear-program dual view using dual LP / dual polynomials to prove approximate-degree lower bounds, with an explicit combining trick (feed… | ||
| Vertical Versus Horizontal Poincare Inequalities | Assaf Naor | 54m |
Proves a concrete vertical vs horizontal inequality on the discrete Heisenberg group that yields sharp lower bounds: any embedding of the ball of radius n… | ||
| Partial Difference Equations Over Compact Abelian Groups | Tim Austin | 51m |
Studies measurable circle-valued functions on compact abelian groups that satisfy K-fold partial difference equations and proves the quotient by “degenerate”… | ||
| Some Pseudorandom Phenomena in Finite Fields | Swastik Kopparty | 44m |
Proves two concrete independence results: multiplicative characters like the cubic residue character have negligible correlation with Boolean polynomials of… | ||
| Discrete Tori and Bounds for Linear Codes | Alex Samorodnitsky | 42m |
Recasts linear-code bounds by treating F2^n / C⊥ as a discrete torus and comparing metric balls there to Hamming balls; proves the torus second Laplacian… | ||
| nothing matches | ||