More Like this

1. Fast Regression for Structured Inputs

   Meyer, Raphael ; Musco, Cameron ; Musco, Christopher ; Woodruff, David P. ; Zhou, Samson ( April 2022 , International Conference on Learning Representations (ICLR))

   We study the $\ell_p$ regression problem, which requires finding $\mathbf{x}\in\mathbb R^{d}$ that minimizes $\|\mathbf{A}\mathbf{x}-\mathbf{b}\|_p$ for a matrix $\mathbf{A}\in\mathbb R^{n \times d}$ and response vector $\mathbf{b}\in\mathbb R^{n}$. There has been recent interest in developing subsampling methods for this problem that can outperform standard techniques when $n$ is very large. However, all known subsampling approaches have run time that depends exponentially on $p$, typically, $d^{\mathcal{O}(p)}$, which can be prohibitively expensive. We improve on this work by showing that for a large class of common \emph{structured matrices}, such as combinations of low-rank matrices, sparse matrices, and Vandermonde matrices, there are subsampling based methods for $\ell_p$ regression that depend polynomially on $p$. For example, we give an algorithm for $\ell_p$ regression on Vandermonde matrices that runs in time $\mathcal{O}(n\log^3 n+(dp^2)^{0.5+\omega}\cdot\text{polylog}\,n)$, where $\omega$ is the exponent of matrix multiplication. The polynomial dependence on $p$ crucially allows our algorithms to extend naturally to efficient algorithms for $\ell_\infty$ regression, via approximation of $\ell_\infty$ by $\ell_{\mathcal{O}(\log n)}$. Of practical interest, we also develop a new subsampling algorithm for $\ell_p$ regression for arbitrary matrices, which is simpler than previous approaches for $p \ge 4$. 

   more » « less
2. A New Family of Algebraically Defined Graphs with Small Automorphism Group

   https://doi.org/10.37236/10707  

   Lazebnik, Felix ; Taranchuk, Vladislav ( January 2022 , The Electronic Journal of Combinatorics)

   Let $p$ be an odd  prime, $q=p^e$, $e \geq 1$, and $\mathbb{F} = \mathbb{F}_q$ denote the finite field of $q$ elements.  Let $f: \mathbb{F}^2\to \mathbb{F}$ and  $g: \mathbb{F}^3\to \mathbb{F}$  be functions, and  let $P$ and $L$ be two copies of the 3-dimensional vector space $\mathbb{F}^3$. Consider a bipartite graph $\Gamma_\mathbb{F} (f, g)$ with vertex partitions $P$ and $L$ and with edges defined as follows: for every $(p)=(p_1,p_2,p_3)\in P$ and every $[l]= [l_1,l_2,l_3]\in L$, $\{(p), [l]\} = (p)[l]$ is an edge in $\Gamma_\mathbb{F} (f, g)$ if $$p_2+l_2 =f(p_1,l_1) \;\;\;\text{and}\;\;\; p_3 + l_3 = g(p_1,p_2,l_1).$$The following question  appeared in Nassau: Given $\Gamma_\mathbb{F} (f, g)$,  is it always possible to find a function $h:\mathbb{F}^2\to \mathbb{F}$ such that the graph $\Gamma_\mathbb{F} (f, h)$  with the same vertex set as $\Gamma_\mathbb{F} (f, g)$ and with edges $(p)[l]$  defined in a similar way  by the system $$p_2+l_2 =f(p_1,l_1) \;\;\;\text{and}\;\;\; p_3 + l_3 = h(p_1,l_1),$$ is isomorphic to $\Gamma_\mathbb{F} (f, g)$ for infinitely many $q$?  In this paper we show that the  answer to the question is negative and the graphs $\Gamma_{\mathbb{F}_p}(p_1\ell_1, p_1\ell_1p_2(p_1 + p_2 + p_1p_2))$ provide such an example for $p \equiv 1 \pmod{3}$. Our argument is based on proving that the automorphism group of these graphs has order $p$, which is the smallest possible order of the automorphism group of graphs of the form $\Gamma_{\mathbb{F}}(f, g)$. 

   more » « less
3. Character bounds for regular semisimple elements and asymptotic results on Thompson’s conjecture

   https://doi.org/10.1007/s00209-022-03193-3  

   Larsen, Michael ; Taylor, Jay ; Tiep, Pham Huu ( February 2023 , Mathematische Zeitschrift)

   Abstract For every integer k there exists a bound $$B=B(k)$$ B = B ( k ) such that if the characteristic polynomial of $$g\in \textrm{SL}_n(q)$$ g ∈ SL n ( q ) is the product of $$\le k$$ ≤ k pairwise distinct monic irreducible polynomials over $$\mathbb {F}_q$$ F q , then every element x of $$\textrm{SL}_n(q)$$ SL n ( q ) of support at least B is the product of two conjugates of g . We prove this and analogous results for the other classical groups over finite fields; in the orthogonal and symplectic cases, the result is slightly weaker. With finitely many exceptions ( p ,  q ), in the special case that $$n=p$$ n = p is prime, if g has order $$\frac{q^p-1}{q-1}$$ q p - 1 q - 1 , then every non-scalar element $$x \in \textrm{SL}_p(q)$$ x ∈ SL p ( q ) is the product of two conjugates of g . The proofs use the Frobenius formula together with upper bounds for values of unipotent and quadratic unipotent characters in finite classical groups. 

   more » « less
4. Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms

   https://doi.org/10.1007/s00224-022-10106-8  

   Vyas, Nikhil ; Williams, R. Ryan ( November 2022 , Theory of Computing Systems)

   We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in$\mathsf {Quasi}\text {-}\mathsf {NP} = \mathsf {NTIME}[n^{(\log n)^{O(1)}}]$$\mathrm{Quasi}-\mathrm{NP}=\mathrm{NTIME}\left[n^{{\left(\log n\right)}^{O\left(1\right)}}\right]$and other complexity classes do not have small circuits (in the worst case and/or on average) from various circuit classes$\mathcal { C}$$C$, by showing that$\mathcal { C}$$C$admits non-trivial satisfiability and/or#SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of having a non-trivial#SAT algorithm for a circuit class${\mathcal C}$$C$. Say that a symmetric Boolean functionf(x₁,…,x_n) issparseif it outputs 1 onO(1) values of${\sum }_{i} x_{i}$${\sum }_i{x}_i$. We show that for every sparsef, and for all “typical”$\mathcal { C}$$C$, faster#SAT algorithms for$\mathcal { C}$$C$circuits imply lower bounds against the circuit class$f \circ \mathcal { C}$$f\circ C$, which may bestrongerthan$\mathcal { C}$$C$itself. In particular:

   #SAT algorithms forn^k-size$\mathcal { C}$$C$-circuits running in 2ⁿ/n^ktime (for allk) implyNEXPdoes not have$(f \circ \mathcal { C})$$(f\circ C)$-circuits of polynomial size.

   #SAT algorithms for$2^{n^{{\varepsilon }}}$$2^{n^{\epsilon }}$-size$\mathcal { C}$$C$-circuits running in$2^{n-n^{{\varepsilon }}}$$2^{n-n^{\epsilon }}$time (for someε> 0) implyQuasi-NPdoes not have$(f \circ \mathcal { C})$$(f\circ C)$-circuits of polynomial size.

   Applying#SAT algorithms from the literature, one immediate corollary of our results is thatQuasi-NPdoes not haveEMAJ∘ACC⁰∘THRcircuits of polynomial size, whereEMAJis the “exact majority” function, improving previous lower bounds againstACC⁰[Williams JACM’14] andACC⁰∘THR[Williams STOC’14], [Murray-Williams STOC’18]. This is the first nontrivial lower bound against such a circuit class.

    

   more » « less
5. Finding solutions with distinct variables to systems of linear equations over $$\mathbb {F}_p$$

   https://doi.org/10.1007/s00208-022-02391-y  

   Sauermann, Lisa ( April 2022 , Mathematische Annalen)

   Let us fix a primepand a homogeneous system ofmlinear equations$$a_{j,1}x_1+\dots +a_{j,k}x_k=0$$$a_{j,1}{x}_1+\cdots +a_{j,k}{x}_k=0$for$$j=1,\dots ,m$$$j=1,\cdots ,m$with coefficients$$a_{j,i}\in \mathbb {F}_p$$$a_{j,i}\in F_p$. Suppose that$$k\ge 3m$$$k\ge 3m$, that$$a_{j,1}+\dots +a_{j,k}=0$$$a_{j,1}+\cdots +a_{j,k}=0$for$$j=1,\dots ,m$$$j=1,\cdots ,m$and that every$$m\times m$$$m\times m$minor of the$$m\times k$$$m\times k$matrix$$(a_{j,i})_{j,i}$$${\left(a_{j,i}\right)}_{j,i}$is non-singular. Then we prove that for any (large)n, any subset$$A\subseteq \mathbb {F}_p^n$$$A\subseteq F_p^n$of size$$|A|> C\cdot \Gamma ^n$$$\left|A\right|>C·{\Gamma }^n$contains a solution$$(x_1,\dots ,x_k)\in A^k$$$(x_1,\cdots ,x_k)\in A^k$to the given system of equations such that the vectors$$x_1,\dots ,x_k\in A$$$x_1,\cdots ,x_k\in A$are all distinct. Here,Cand$$\Gamma $$$\Gamma$are constants only depending onp,mandksuch that$$\Gamma $\Gamma <p$. The crucial point here is the condition for the vectors$$x_1,\dots ,x_k$$$x_1,\cdots ,x_k$in the solution$$(x_1,\dots ,x_k)\in A^k$$$(x_1,\cdots ,x_k)\in A^k$to be distinct. If we relax this condition and only demand that$$x_1,\dots ,x_k$$$x_1,\cdots ,x_k$are not all equal, then the statement would follow easily from Tao’s slice rank polynomial method. However, handling the distinctness condition is much harder, and requires a new approach. While all previous combinatorial applications of the slice rank polynomial method have relied on the slice rank of diagonal tensors, we use a slice rank argument for a non-diagonal tensor in combination with combinatorial and probabilistic arguments.

    

   more » « less