Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBreaking the quadratic barrier for 3-LCCs over the Reals
223
0
0.0
(
0
)
Added by
Zeev Dvir
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We prove that 3-query linear locally correctable codes over the Reals of dimension $d$ require block length $n>d^{2+lambda}$ for some fixed, positive $lambda >0$. Geometrically, this means that if $n$ vectors in $R^d$ are such that each vector is spanned by a linear number of disjoint triples of others, then it must be that $n > d^{2+lambda}$. This improves the known quadratic lower bounds (e.g. {KdW04, Wood07}). While a modest improvement, we expect that the new techniques introduced in this work will be useful for further progress on lower bounds of locally correctable and decodable codes with more than 2 queries, possibly over other fields as well. Our proof introduces several new ideas to existing lower bound techniques, several of which work over every field. At a high level, our proof has two parts, {it clustering} and {it random restriction}. The clustering step uses a powerful theorem of Barthe from convex geometry. It can be used (after preprocessing our LCC to be {it balanced}), to apply a basis change (and rescaling) of the vectors, so that the resulting unit vectors become {it nearly isotropic}. This together with the fact that any LCC must have many `correlated pairs of points, lets us deduce that the vectors must have a surprisingly strong geometric clustering, and hence also combinatorial clustering with respect to the spanning triples. In the restriction step, we devise a new variant of the dimension reduction technique used in previous lower bounds, which is able to take advantage of the combinatorial clustering structure above. The analysis of our random projection method reduces to a simple (weakly) random graph process, and works over any field.
rate research
Read More
We introduce a simple logical inference structure we call a $textsf{spanoid}$ (generalizing the notion of a matroid), which captures well-studied problems in several areas. These include combinatorial geometry, algebra (arrangements of hypersurfaces and ideals), statistical physics (bootstrap percolation) and coding theory. We initiate a thorough investigation of spanoids, from computational and structural viewpoints, focusing on parameters relevant to the applications areas above and, in particular, to questions regarding Locally Correctable Codes (LCCs). One central parameter we study is the $textsf{rank}$ of a spanoid, extending the rank of a matroid and related to the dimension of codes. This leads to one main application of our work, establishing the first known barrier to improving the nearly 20-year old bound of Katz-Trevisan (KT) on the dimension of LCCs. On the one hand, we prove that the KT bound (and its more recent refinements) holds for the much more general setting of spanoid rank. On the other hand we show that there exist (random) spanoids whose rank matches these bounds. Thus, to significantly improve the known bounds one must step out of the spanoid framework. Another parameter we explore is the $textsf{functional rank}$ of a spanoid, which captures the possibility of turning a given spanoid into an actual code. The question of the relationship between rank and functional rank is one of the main questions we raise as it may reveal new avenues for constructing new LCCs (perhaps even matching the KT bound). As a first step, we develop an entropy relaxation of functional rank to create a small constant gap and amplify it by tensoring to construct a spanoid whose functional rank is smaller than rank by a polynomial factor. This is evidence that the entropy method we develop can prove polynomially better bounds than KT-type methods on the dimension of LCCs.
We study the probabilistic degree over reals of the OR function on $n$ variables. For an error parameter $epsilon$ in (0,1/3), the $epsilon$-error probabilistic degree of any Boolean function $f$ over reals is the smallest non-negative integer $d$ such that the following holds: there exists a distribution $D$ of polynomials entirely supported on polynomials of degree at most $d$ such that for all $z in {0,1}^n$, we have $Pr_{P sim D} [P(z) = f(z) ] geq 1- epsilon$. It is known from the works of Tarui ({Theoret. Comput. Sci.} 1993) and Beigel, Reingold, and Spielman ({ Proc. 6th CCC} 1991), that the $epsilon$-error probabilistic degree of the OR function is at most $O(log n.log 1/epsilon)$. Our first observation is that this can be improved to $O{log {{n}choose{leq log 1/epsilon}}}$, which is better for small values of $epsilon$. In all known constructions of probabilistic polynomials for the OR function (including the above improvement), the polynomials $P$ in the support of the distribution $D$ have the following special structure:$P = 1 - (1-L_1).(1-L_2)...(1-L_t)$, where each $L_i(x_1,..., x_n)$ is a linear form in the variables $x_1,...,x_n$, i.e., the polynomial $1-P(x_1,...,x_n)$ is a product of affine forms. We show that the $epsilon$-error probabilistic degree of OR when restricted to polynomials of the above form is $Omega ( log a/log^2 a )$ where $a = log {{n}choose{leq log 1/epsilon}}$. Thus matching the above upper bound (up to poly-logarithmic factors).
The matroid intersection problem is a fundamental problem that has been extensively studied for half a century. In the classic version of this problem, we are given two matroids $mathcal{M}_1 = (V, mathcal{I}_1)$ and $mathcal{M}_2 = (V, mathcal{I}_2)$ on a comment ground set $V$ of $n$ elements, and then we have to find the largest common independent set $S in mathcal{I}_1 cap mathcal{I}_2$ by making independence oracle queries of the form Is $S in mathcal{I}_1$? or Is $S in mathcal{I}_2$? for $S subseteq V$. The goal is to minimize the number of queries. Beating the existing $tilde O(n^2)$ bound, known as the quadratic barrier, is an open problem that captures the limits of techniques from two lines of work. The first one is the classic Cunninghams algorithm [SICOMP 1986], whose $tilde O(n^2)$-query implementations were shown by CLS+ [FOCS 2019] and Nguyen [2019]. The other one is the general cutting plane method of Lee, Sidford, and Wong [FOCS 2015]. The only progress towards breaking the quadratic barrier requires either approximation algorithms or a more powerful rank oracle query [CLS+ FOCS 2019]. No exact algorithm with $o(n^2)$ independence queries was known. In this work, we break the quadratic barrier with a randomized algorithm guaranteeing $tilde O(n^{9/5})$ independence queries with high probability, and a deterministic algorithm guaranteeing $tilde O(n^{11/6})$ independence queries. Our key insight is simple and fast algorithms to solve a graph reachability problem that arose in the standard augmenting path framework [Edmonds 1968]. Combining this with previous exact and approximation algorithms leads to our results.
N. Hindman, I. Leader and D. Strauss proved that it is consistent that there is a finite colouring of $mathbb R$ so that no infinite sumset $X+X={x+y:x,yin X}$ is monochromatic. Our aim in this paper is to prove a consistency result in the opposite direction: we show that, under certain set-theoretic assumptions, for any $c:mathbb Rto r$ with $r$ finite there is an infinite $Xsubseteq mathbb R$ so that $c$ is constant on $X+X$.
Consider the problem of determining whether there exists a spanning hypertree in a given k-uniform hypergraph. This problem is trivially in P for k=2, and is NP-complete for k>= 4, whereas for k=3, there exists a polynomial-time algorithm based on Lovasz theory of polymatroid matching. Here we give a completely different, randomized polynomial-time algorithm in the case k=3. The main ingredients are a Pfaffian formula by Vaintrob and one of the authors (G.M.) for a polynomial that enumerates spanning hypertrees with some signs, and a lemma on the number of roots of polynomials over a finite field.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
