Consider the following problem: Given an$n$×$n$multiplication table, decide whether it is a Cayley multiplication table of a group. Among deterministic algorithms for this problem, the best known algorithm is implied by F. W. Light's associativity test (1949) and has running time of${O}(n^{2}\log n)$. Allowing randomization. the best known algorithm has running time of$O(n^{2}\log(1/\delta))$, where$\delta > 0$is the error probability of the algorithm (Rajagopalan and Schulman, FOCS 1996, SICOMP 2000). In this work, we improve upon both of the above known algorithms. Specifically, we present a deterministic algorithm for the above problem whose running time is$O(n^{2})$. This performance is optimal up to constants. A central tool we develop is an efficient algorithm for finding a subset$A$of a group$G$satisfying$A^{2}=G$while$\vert A\vert=O(\sqrt{\vert G\vert })$.

Recent efforts in Analysis of Boolean Functions aim to extend core results to new spaces, including to the slice $\binom{[n]}{k}$, the hypergrid $[K]^n$, and noncommutative spaces (matrix algebras). We present here a new way to relate functions on the hypergrid (or products of cyclic groups) to their harmonic extensions over the polytorus. We show the supremum of a function $f$ over products of the cyclic group $\{\exp(2πi k/K)\}_{k=1}^K$ controls the supremum of $f$ over the entire polytorus $(\{z\in\mathbf{C}:|z|=1\}^n)$, with multiplicative constant $C$ depending on $K$ and $\text{deg}(f)$ only. This Remez-type inequality appears to be the first such estimate that is dimension-free (i.e., $C$ does not depend on $n$). This dimension-free Remez-type inequality removes the main technical barrier to giving $\mathcal{O}(\log n)$ sample complexity, polytime algorithms for learning low-degree polynomials on the hypergrid and low-degree observables on level-$K$ qudit systems. In particular, our dimension-free Remez inequality implies new Bohnenblust--Hille-type estimates which are central to the learning algorithms and appear unobtainable via standard techniques. Thus we extend to new spaces a recent line of work \cite{EI22, CHP, VZ22} that gave similarly efficient methods for learning low-degree polynomials on the hypercube and observables on qubits. An additional product of these efforts is a new class of distributions over which arbitrary quantum observables are well-approximated by their low-degree truncations -- a phenomenon that greatly extends the reach of low-degree learning in quantum science \cite{CHP}.

An average-case variant of the k -SUM conjecture asserts that finding k numbers that sum to 0 in a list of r random numbers, each of the order r k , cannot be done in much less than \(r^{\lceil k/2 \rceil }\) time. However, in the dense regime of parameters, where the list contains more numbers and many solutions exist, the complexity of finding one of them can be significantly improved by Wagner’s k -tree algorithm. Such algorithms for k -SUM in the dense regime have many applications, notably in cryptanalysis. In this article, assuming the average-case k -SUM conjecture, we prove that known algorithms are essentially optimal for k = 3,4,5. For k > 5, we prove the optimality of the k -tree algorithm for a limited range of parameters. We also prove similar results for k -XOR, where the sum is replaced with exclusive or. Our results are obtained by a self-reduction that, given an instance of k -SUM that has a few solutions, produces from it many instances in the dense regime. We solve each of these instances using the dense k -SUM oracle and hope that a solution to a dense instance also solves the original problem. We deal with potentially malicious oracles (that repeatedly output correlated useless solutions) by an obfuscation process that adds noise to the dense instances. Using discrete Fourier analysis, we show that the obfuscation eliminates correlations among the oracle’s solutions, even though its inputs are highly correlated.

Consider the n-cube graph with vertices $\{-1,1\}^{n}$ and edges connecting vertices with Hamming distance 1. How many hyperplanes in $\mathbb{R}^{n}$ are needed in order to dissect all edges? We show that at least $\widetilde{\Omega}(n^{2/3})$ are needed, which improves the previous bound of $\Omega(n^{0.51})$ by Yehuda and Yehudayoff.

Let $a_1, \ldots, a_n \in \mathbb{R}$ satisfy $\sum_i a_i^2 = 1$, and let $\varepsilon_1, \ldots, \varepsilon_n$ be uniformly random $\pm 1$ signs and $X = \sum_{i=1}^{n} a_i \varepsilon_i$. It is conjectured that $X = \sum_{i=1}^{n} a_i \varepsilon_i$ has $\Pr[X \geq 1] \geq 7/64$. The best lower bound so far is $1/20$, due to Oleszkiewicz. In this paper we improve this to $\Pr[X \geq 1] \geq 6/64$.

We prove Tomaszewski’s conjecture (1986): Let f:{−1,1}n → ℝ be of the form f(x)= ∑i=1n ai xi. Then Pr[|f(x)| ≤ √Var[f]] ≥ 1/2. Our main novel tools are local concentration inequalities and an improved Berry-Esseen inequality for first-degree functions on the discrete cube. These tools are of independent interest, and may be useful in the study of linear threshold functions and of low degree Boolean functions.