More Like this

1. Searching for Regularity in Bounded Functions

   Iyer, Siddharth; Whitmeyer, Michael (July 2023, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023))

   Given a function f on (F_2_^n, we study the following problem. What is the largest affine subspace U such that when restricted to U, all the non-trivial Fourier coefficients of f are very small? For the natural class of bounded Fourier degree d functions f : (F_2)^n → [−1, 1], we show that there exists an affine subspace of dimension at least ˜Ω (n^(1/d!) k^(−2)), wherein all of f ’s nontrivial Fourier coefficients become smaller than 2^(−k) . To complement this result, we show the existence of degree d functions with coefficients larger than 2^(−d log n) when restricted to any affine subspace of dimension larger than Ω(dn^(1/(d−1))). In addition, we give explicit examples of functions with analogous but weaker properties. Along the way, we provide multiple characterizations of the Fourier coefficients of functions restricted to subspaces of (F_2)^n that may be useful in other contexts. Finally, we highlight applications and connections of our results to parity kill number and affine dispersers. 

   more » « less
2. Linear Sketching over F_2

   https://doi.org/10.4230/LIPIcs.CCC.2018.8  

   Kannan, Sampath; Mossel, Elchanan; Sanyal, Swagato; Yaroslavtsev, Grigory (August 2018, Leibniz international proceedings in informatics)

   We initiate a systematic study of linear sketching over F_2. For a given Boolean function treated as f : F_2^n -> F_2 a randomized F_2-sketch is a distribution M over d x n matrices with elements over F_2 such that Mx suffices for computing f(x) with high probability. Such sketches for d << n can be used to design small-space distributed and streaming algorithms. Motivated by these applications we study a connection between F_2-sketching and a two-player one-way communication game for the corresponding XOR-function. We conjecture that F_2-sketching is optimal for this communication game. Our results confirm this conjecture for multiple important classes of functions: 1) low-degree F_2-polynomials, 2) functions with sparse Fourier spectrum, 3) most symmetric functions, 4) recursive majority function. These results rely on a new structural theorem that shows that F_2-sketching is optimal (up to constant factors) for uniformly distributed inputs. Furthermore, we show that (non-uniform) streaming algorithms that have to process random updates over F_2 can be constructed as F_2-sketches for the uniform distribution. In contrast with the previous work of Li, Nguyen and Woodruff (STOC'14) who show an analogous result for linear sketches over integers in the adversarial setting our result does not require the stream length to be triply exponential in n and holds for streams of length O(n) constructed through uniformly random updates. 

   more » « less
3. A dimension-free discrete Remez-type inequality on the polytorus

   Slote, Joseph; Volberg, Alexander; Zhang, Haonan (January 2026, Discrete analysis)

   Consider f : Ωn K →C a function from the n-fold product of multiplicative cyclic groups of order K. Any such f may be extended via its Fourier expansion to an analytic polynomial on the polytorus Tn, and the set of such polynomials coincides with the set of all analytic polynomials on Tn of individual degree at most K−1. In this setting it is natural to ask how the supremum norms of f over Tn and over Ωn K compare. We prove the following discretization of the uniform norm for low-degree polynomials: if f has degree at most d as an analytic polynomial, then ∥ f ∥Tn ≤C(d,K)∥ f ∥Ωn K with C(d,K) independent of dimension n. As a consequence we also obtain a new proof of the Bohnenblust–Hille inequality for functions on products of cyclic groups. Key to our argument is a special class of Fourier multipliers on Ωn K which are L∞ →L∞ bounded independent of dimension when restricted to low-degree polynomials. This class includes projections onto the k-homogeneous parts of low-degree polynomials as well as projections of much finer granularity. 

   more » « less
4. Affine Stresses, Inverse Systems, and Reconstruction Problems

   https://doi.org/10.1093/imrn/rnad294  

   Murai, Satoshi; Novik, Isabella; Zheng, Hailun (December 2023, International Mathematics Research Notices)

   Abstract A conjecture of Kalai asserts that for $$d\geq 4$$, the affine type of a prime simplicial $$d$$-polytope $$P$$ can be reconstructed from the space of affine $$2$$-stresses of $$P$$. We prove this conjecture for all $$d\geq 5$$. We also prove the following generalization: for all pairs $(i,d)$ with $$2\leq i\leq \lceil \frac d 2\rceil -1$$, the affine type of a simplicial $$d$$-polytope $$P$$ that has no missing faces of dimension $$\geq d-i+1$$ can be reconstructed from the space of affine $$i$$-stresses of $$P$$. A consequence of our proofs is a strengthening of the Generalized Lower Bound Theorem: it was proved by Nagel that for any simplicial $(d-1)$-sphere $$\Delta $$ and $$1\leq k\leq \lceil \frac {d}{2}\rceil -1$$, $$g_{k}(\Delta )$$ is at least as large as the number of missing $(d-k)$-faces of $$\Delta $$; here we show that, for $$1\leq k\leq \lfloor \frac {d}{2}\rfloor -1$$, equality holds if and only if $$\Delta $$ is $$k$$-stacked. Finally, we show that for $$d\geq 4$$, any simplicial $$d$$-polytope $$P$$ that has no missing faces of dimension $$\geq d-1$$ is redundantly rigid, that is, for each edge $$e$$ of $$P$$, there exists an affine $$2$$-stress on $$P$$ with a non-zero value on $$e$$. 

   more » « less
5. Approximate Degree, Secret Sharing, and Concentration Phenomena

   https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.71  

   Bogdanov, Andrej; Mande, Nikhil S.; Thaler, Justin; Williamson, Christopher (September 2019, Leibniz international proceedings in informatics)

   The epsilon-approximate degree, deg_epsilon(f), of a Boolean function f is the least degree of a real-valued polynomial that approximates f pointwise to within epsilon. A sound and complete certificate for approximate degree being at least k is a pair of probability distributions, also known as a dual polynomial, that are perfectly k-wise indistinguishable, but are distinguishable by f with advantage 1 - epsilon. Our contributions are: - We give a simple, explicit new construction of a dual polynomial for the AND function on n bits, certifying that its epsilon-approximate degree is Omega (sqrt{n log 1/epsilon}). This construction is the first to extend to the notion of weighted degree, and yields the first explicit certificate that the 1/3-approximate degree of any (possibly unbalanced) read-once DNF is Omega(sqrt{n}). It draws a novel connection between the approximate degree of AND and anti-concentration of the Binomial distribution. - We show that any pair of symmetric distributions on n-bit strings that are perfectly k-wise indistinguishable are also statistically K-wise indistinguishable with at most K^{3/2} * exp (-Omega (k^2/K)) error for all k < K <= n/64. This bound is essentially tight, and implies that any symmetric function f is a reconstruction function with constant advantage for a ramp secret sharing scheme that is secure against size-K coalitions with statistical error K^{3/2} * exp (-Omega (deg_{1/3}(f)^2/K)) for all values of K up to n/64 simultaneously. Previous secret sharing schemes required that K be determined in advance, and only worked for f=AND. Our analysis draws another new connection between approximate degree and concentration phenomena. As a corollary of this result, we show that for any d <= n/64, any degree d polynomial approximating a symmetric function f to error 1/3 must have coefficients of l_1-norm at least K^{-3/2} * exp ({Omega (deg_{1/3}(f)^2/d)}). We also show this bound is essentially tight for any d > deg_{1/3}(f). These upper and lower bounds were also previously only known in the case f=AND. 

   more » « less