Research

It is known that any Boolean function that depends on all its n inputs, when represented as a real-valued multivariate polynomial, must have degree at least log n - O(1). Similar statements are also known for other Boolean function complexity measures such as sensitivity, quantum query complexity, and approximate degree. In this work, we address this question for probabilistic degree.

The probabilistic degree of a Boolean function is defined to be the smallest degree of a random polynomial that agrees with the function with high probability, at each input. Our understanding of this complexity is significantly weaker than above: for instance, we do not even know the probabilistic degree of the OR function. Here, we give a near-optimal understanding of the minimum possible probabilistic degree of an n-variate Boolean function, modulo our lack of understanding of the probabilistic degree of OR.

(Accepted in the APPROX-RANDOM 2021 Special Issue of the Theory of Computing.) 

Alon and Füredi (1993) proved that any family of hyperplanes that covers every point of the n-dimensional Boolean cube, except one, must contain at least n hyperplanes. We obtain two extensions of this result, in characteristic zero, for hyperplane covers of symmetric sets of the Boolean cube (subsets that are closed under permutations of coordinates).

As a main tool for solving our problems, we give a combinatorial characterization of the finite-degree Zariski closures of symmetric sets of the Boolean cube. 

The probabilistic degree of a Boolean function is defined to be the smallest degree of a random polynomial that agrees with the function with high probability, at each input. Introduced by Razborov (1987), upper and lower bounds on probabilistic degrees of Boolean functions -- specifically symmetric Boolean functions -- have been used to prove explicit lower bounds, design pseudorandom generators, and devise algorithms for combinatorial problems.

In this work, we characterize the probabilistic degrees of all symmetric Boolean functions up to polylogarithmic factors in the input size, over all fields of fixed characteristic (positive or zero).

In this work, we prove the first Fixed-Depth Size-Hierarchy Theorem for uniform AC^0[MOD_2]. In particular, we show that for any fixed d, the class C_{d,k} of functions that have uniform AC^0[MOD_2] formulas of depth d and size n^k, form an infinite hierarchy. We show this by exhibiting the first class of explicit functions where we have nearly (up to polylogarithmic factors) matching upper and lower bounds for the class of AC^0[MOD_2] formulas.

The explicit functions are derived from the Delta-Coin Problem, which is the computational problem of distinguishing between coins that are heads with probability (1+ Delta)/2 or (1 - Delta)/2, where Delta is a parameter going to 0. We study the complexity of this problem and make progress on both upper and lower bound fronts. 

Kim and Kopparty (2017) gave a deterministic algorithm for the unique decoding problem for polynomials of bounded total degree over a general finite grid. We show that their algorithm can be adapted to solve the unique decoding problem for the general family of downset codes. Here, a downset code is specified by a family D of monomials closed under taking factors; the corresponding code is the space of evaluations of all polynomials that can be written as linear combinations of monomials from D. 

Polynomial ideal (PI) codes are linear codes where the encoding is defined by the residues of a polynomial (the message) with respect to a set of pairwise coprime ideals.  Specific instances of PI codes are well-studied, and the general class of PI codes was considered (Bhandari, Kumar, Harsha, and Sudan, 2021) in the context of efficient list-decoding.

Recent breakthroughs (Brakensiek, Gopi, and Makam, 2023; Guo and Zhang, 2023) show that randomly punctured Reed-Solomon codes achieve list-decoding capacity with optimal list size.  We build upon these results, and show that a large subclass of PI codes achieves list-decoding capacity with optimal list size, and some of these codes, in fact, can be list-decoded efficiently.

Alon and Füredi (European J. Combin. 1993) gave a tight bound for the following hyperplane covering problem: find the minimum number of hyperplanes required to cover all points of the n-dimensional hypercube {0,1}^n except the origin. Their proof, in fact, gives a lower bound for a weaker polynomial covering problem, and it turns out that this bound is tight for the stronger hyperplane covering problem. In a similar vein, solutions to some other hyperplane covering problems were obtained, via solutions of corresponding weaker polynomial covering problems, have been observed recently.

In this work, we build on these and solve a hyperplane covering problem for general symmetric sets of the hypercube, where we consider hyperplane covers with higher multiplicities. We see that even in this generality, it is enough to solve the corresponding polynomial covering problem.  Further, we gather evidence that this seems to be the limit of this approach as far as covering symmetry preserving subsets of the hypercube is concerned.

The affine Hilbert function is a classical algebraic object that has been central, among other tools, to the development of the polynomial method in combinatorics. Owing to its concrete connections with Gröbner basis theory, as well as its applicability in several areas like computational complexity, combinatorial geometry, and coding theory, an important line of enquiry is to understand the affine Hilbert function of structured sets of points in the affine space.

In this work, we determine the affine Hilbert function (over the reals) of arbitrary unions of layers of points in a uniform grid (a finite grid with the component sets having equispaced points), where each layer of points is determined by a fixed sum of components for all the points. This extends a result of Bernasconi and Egidi (1999) from the Boolean cube setting to the uniform grid setting. 

The finite-degree Zariski (Z-) closure is a classical algebraic object, that has found a key place in several applications of the polynomial method in combinatorics. In this work, we characterize the finite-degree Z-closures of a subclass of symmetric sets (subsets that are invariant under permutations of coordinates) of the Boolean cube, in positive characteristic.

Our results subsume multiple statements on finite-degree Z-closures that have found applications in extremal combinatorial problems, for instance, pertaining to set systems (Hegedűs, 2010; Hegedűs, 2021), and Boolean circuits (Hrǔbes et al., 2019). Our characterization also establishes that for the subclasses of symmetric sets that we consider, the finite-degree Z-closures have low computational complexity.