Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPoint-hyperplane incidence geometry and the log-rank conjecture
137
0
0.0
(
0
)
Added by
Noah Singer
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study the log-rank conjecture from the perspective of point-hyperplane incidence geometry. We formulate the following conjecture: Given a point set in $mathbb{R}^d$ that is covered by constant-sized sets of parallel hyperplanes, there exists an affine subspace that accounts for a large (i.e., $2^{-{operatorname{polylog}(d)}}$) fraction of the incidences. Alternatively, our conjecture may be interpreted linear-algebraically as follows: Any rank-$d$ matrix containing at most $O(1)$ distinct entries in each column contains a submatrix of fractional size $2^{-{operatorname{polylog}(d)}}$, in which each column contains one distinct entry. We prove that our conjecture is equivalent to the log-rank conjecture. Motivated by the connections above, we revisit well-studied questions in point-hyperplane incidence geometry without structural assumptions (i.e., the existence of partitions). We give an elementary argument for the existence of complete bipartite subgraphs of density $Omega(epsilon^{2d}/d)$ in any $d$-dimensional configuration with incidence density $epsilon$. We also improve an upper-bound construction of Apfelbaum and Sharir (SIAM J. Discrete Math. 07), yielding a configuration whose complete bipartite subgraphs are exponentially small and whose incidence density is $Omega(1/sqrt d)$. Finally, we discuss various constructions (due to others) which yield configurations with incidence density $Omega(1)$ and bipartite subgraph density $2^{-Omega(sqrt d)}$. Our framework and results may help shed light on the difficulty of improving Lovetts $tilde{O}(sqrt{operatorname{rank}(f)})$ bound (J. ACM 16) for the log-rank conjecture; in particular, any improvement on this bound would imply the first bipartite subgraph size bounds for parallel $3$-partitioned configurations which beat our generic bounds for unstructured configurations.
rate research
Read More
There is a trinity relationship between hyperplane arrangements, matroids and convex polytopes. We expand it as resolving the complexity issue expected by Mnevs universality theorem and conduct combinatorializing so the theory over fields becomes realization of our combinatorial theory. A main theorem is that for n less than or equal to 9 a specific and general enough kind of matroid tilings in the hypersimplex Delta(3,n) extend to matroid subdivisions of Delta(3,n) with the bound n=9 sharp. As a straightforward application to realizable cases, we solve an open problem in algebraic geometry proposed in 2008.
A (q,k,t)-design matrix is an m x n matrix whose pattern of zeros/non-zeros satisfies the following design-like condition: each row has at most q non-zeros, each column has at least k non-zeros and the supports of every two columns intersect in at most t rows. We prove that the rank of any (q,k,t)-design matrix over a field of characteristic zero (or sufficiently large finite characteristic) is at least n - (qtn/2k)^2 . Using this result we derive the following applications: (1) Impossibility results for 2-query LCCs over the complex numbers: A 2-query locally correctable code (LCC) is an error correcting code in which every codeword coordinate can be recovered, probabilistically, by reading at most two other code positions. Such codes have numerous applications and constructions (with exponential encoding length) are known over finite fields of small characteristic. We show that infinite families of such linear 2-query LCCs do not exist over the complex numbers. (2) Generalization of results in combinatorial geometry: We prove a quantitative analog of the Sylvester-Gallai theorem: Let $v_1,...,v_m$ be a set of points in $C^d$ such that for every $i in [m]$ there exists at least $delta m$ values of $j in [m]$ such that the line through $v_i,v_j$ contains a third point in the set. We show that the dimension of ${v_1,...,v_m }$ is at most $O(1/delta^2)$. Our results generalize to the high dimensional case (replacing lines with planes, etc.) and to the case where the points are colored (as in the Motzkin-Rabin Theorem).
For every $epsilon>0$, we give an $exp(tilde{O}(sqrt{n}/epsilon^2))$-time algorithm for the $1$ vs $1-epsilon$ emph{Best Separable State (BSS)} problem of distinguishing, given an $n^2times n^2$ matrix $mathcal{M}$ corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state $rho$ that $mathcal{M}$ accepts with probability $1$, and the case that every separable state is accepted with probability at most $1-epsilon$. Equivalently, our algorithm takes the description of a subspace $mathcal{W} subseteq mathbb{F}^{n^2}$ (where $mathbb{F}$ can be either the real or complex field) and distinguishes between the case that $mathcal{W}$ contains a rank one matrix, and the case that every rank one matrix is at least $epsilon$ far (in $ell_2$ distance) from $mathcal{W}$. To the best of our knowledge, this is the first improvement over the brute-force $exp(n)$-time algorithm for this problem. Our algorithm is based on the emph{sum-of-squares} hierarchy and its analysis is inspired by Lovetts proof (STOC 14, JACM 16) that the communication complexity of every rank-$n$ Boolean matrix is bounded by $tilde{O}(sqrt{n})$.
We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on $n$ input bits, each of which has approximate Fourier sparsity at most $O(n^3)$ and randomized parity decision tree complexity $Theta(n)$. This improves upon the recent work of Chattopadhyay, Mande and Sherif (JACM 20) both qualitatively (in terms of designing a large number of examples) and quantitatively (improving the gap from quartic to cubic). We leave open the problem of proving a randomized communication complexity lower bound for XOR compositions of our examples. A linear lower bound would lead to new and improved refutations of the log-approximate-rank conjecture. Moreover, if any of these compositions had even a sub-linear cost randomized communication protocol, it would demonstrate that randomized parity decision tree complexity does not lift to randomized communication complexity in general (with the XOR gadget).
An $ntimes n$ matrix $M$ is called a textit{fooling-set matrix of size $n$} if its diagonal entries are nonzero and $M_{k,ell} M_{ell,k} = 0$ for every $k e ell$. Dietzfelbinger, Hromkovi{v{c}}, and Schnitger (1996) showed that $n le (mbox{rk} M)^2$, regardless of over which field the rank is computed, and asked whether the exponent on $mbox{rk} M$ can be improved. We settle this question. In characteristic zero, we construct an infinite family of rational fooling-set matrices with size $n = binom{mbox{rk} M+1}{2}$. In nonzero characteristic, we construct an infinite family of matrices with $n= (1+o(1))(mbox{rk} M)^2$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
