ﻻ يوجد ملخص باللغة العربية
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.
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
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$ su
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)
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 d
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 Lo