On a special case of rigidity
On a special case of rigidity
复制标题
关于刚性的特殊情况
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Emanuele Viola
中科院分区：
文献类型：
--
作者：
R. Servedio;Emanuele Viola
我们强调了Valiant的刚性问题的特殊情况，其中低级矩阵是稀疏的多项式的真实表，我们表明，在这种特殊情况下的进度表明，内部产品不可能由一层奇偶校验的小型交流电路计算然后，我们证明，在2N变量中，任何-1/1多项式的符号≤s单次，在≥Ω（1/s）的内部产物中不同意输入的一部分，这是一种结果Valiant的刚度问题[Val77]要求建立与低级数矩阵的锤距距离远的显式矩阵。 1）n，那么相应的线性转换x 7→MX需要超级质量深度或超线性大小的电路。长期以来的挑战。 。矩阵具有秩R，并且仅当它是r级别1矩阵的总和，即矩阵uiv t i，其中ui，vi是n-Entry列向量。矩阵是变量x1的真实性。单一c∏i∈S xii∈Tyi，其中s，t⊆{1，。 ∏i∈Tbi。该矩阵可以写为uv t，其中u的A-thentrix是c ∏i∈Sai，而v的b-the则是∏i∈Tbi。问题无直接参考，如下所示。 ：{-1，1}×{-1，1}→{-1，1}，使得对于任何具有≤r单元的真实多项式P，我们都有pr x，y∈{-1,1} n [f（x ，y）6 = p（x，y）]≥， *由nsf授予CCF-1115703：rocco@cs.columbia.edu†NSF授予CCF-0845003对于尽可能大。界限。强度的界限会产生新的电路，让AC-rever表示，AC电路的类别以均衡范围（在输入位之前）增强知识，尚不清楚内部产品功能IP是否可以通过多种大小的AC-c循环进行计算：挑战0.2。深度4的电路，但众所周知，对于深度3的AC-r电路，即多大小的DNF-⊕电路。这种电路可计算的任何功能在变量的某个子集上具有1/poly相关性，但众所周知，IP在任何一个子集中均与奇偶校验指数相关。实际上，对AC的理解为奇偶校验。 IP是一个自然的候选人，我们将两个挑战率定向。 2LGC n单元，使PR X，Y [P（X，Y）6 = IP（X，Y）]≤2LGB。输入位x1。 。输入变量Zi（So C'是n输入位Z1，...，Zn的电路）。并设置zi = x上i-th Parity门的值（d的绘制是字符串z∈{0，1}）。 n））2d，用于从D的所有输入的A（1-）分数计算C'（z）。由于P具有度（O（lg n）），它必须具有≤nn n））2D单元。 x1，xn，y1。在p中替换Zi的Zi（单元）不超过P。连接下限，我们需要等级r =ω（n），而对于稀疏性，班级级别r = poly lgn患者，我们需要超越误差1/r。
We highlight the special case of Valiant’s rigidity problem in which the low-rank matrices are truth-tables of sparse polynomials. We show that progress on this special case entails that Inner Product is not computable by small AC circuits with one layer of parity gates close to the inputs. We then prove that the sign of any −1/1 polynomial with ≤ s monomials in 2n variables disagrees with Inner Product in ≥ Ω(1/s) fraction of inputs, a type of result that seems unknown in the rigidity setting. Valiant’s rigidity problem [Val77] asks to build explicit matrixes that are far in Hamming distance from low-rank matrixes. Valiant proved that if an N ×N matrix M has hamming distance ≥ N from any matrix of rank R = (1−Ω(1))N , then the corresponding linear transformation x 7→ Mx requires circuits of superlogarithmic depth or superlinear size. Exhibiting an explicit such matrix remains a long-standing challenge. Despite significant efforts, the best lower bounds are of the form (N/R) lg(N/R) against matrixes of rank R. The matrix corresponding to the inner product function IP has been conjectured to satisfy better better bounds. We refer the reader to Lokam’s survey [Lok09] for more on rigidity. In this note we highlight a special case of the rigidity problem, and we suggest that attacks should be directed towards it. Recall that an N ×N matrix has rank R if and only if it is the sum of R rank-1 matrixes, i.e., matrixes uiv T i , where ui, vi are N -entry column vectors. We consider the special case of this problem where the rank-1 matrixes are the truthtables of monomials over the variables x1, . . . , xn, y1, . . . , yn, where N = 2 n and the variables range over {−1, 1}. For example, the truth-table of a monomial c ∏ i∈S xi ∏ i∈T yi, where S, T ⊆ {1, . . . , n}, is the N ×N matrix whose entry indexed by (a, b) ∈ {−1, 1}×{−1, 1} is c ∏ i∈S ai ∏ i∈T bi. This matrix can be written as uv T where the a-th entry of u is c ∏ i∈S ai and the b-th entry of v is ∏ i∈T bi. This special case of the rigidity problem is stated without direct reference to rank as follows. Challenge 0.1 (Sparsity). Exhibit an explicit function f : {−1, 1} × {−1, 1} → {−1, 1} such that for any real polynomial p with ≤ R monomials we have Pr x,y∈{−1,1}n [f(x, y) 6= p(x, y)] ≥ , ∗Supported by NSF grant CCF-1115703. Email: rocco@cs.columbia.edu †Supported by NSF grant CCF-0845003. Email: viola@ccs.neu.edu for as large as possible. Again, = Ω(lg(2/R)/R) follows from the rigidity bounds. The concurrent work [RV12] raises a similar challenge for low-degree (as opposed to sparse) polynomials. Motivation: AC with parity gates. Besides hopefully paving the way for the original rigidity question, a motivation for making progress on Challenge 0.1 is that stronger bounds would yield new circuit lower bounds. Let AC-⊕ denote the class of AC circuits augmented with a bottom level (right before the input bits) of parity gates. To our knowledge, it is not known whether the Inner Product function IP is computable by poly-size AC-⊕ circuits: Challenge 0.2. Show that IP cannot be computed by poly-size AC-⊕ circuits. Challenge 0.2 seems open even for AC-⊕ circuits of depth 4, but it is known to be true for AC-⊕ circuits of depth 3, i.e. poly-size DNF-⊕ circuits. Indeed, it follows from Fact 8 in [Jac97] that any function computable by such circuits has 1/poly correlation with parity on some subset of the variables, but it is well-known that IP has exponentially small correlation with parity on any subset of the variables. Solving Challenge 0.2 is a step towards a more thorough understanding of AC with parity gates. For example, no strong correlation bound is known for this class, see e.g. [SV10]. In fact, this is not even known for AC-⊕, and IP is a natural candidate. Next we formally connect the two challenges. Claim 0.3. Suppose that IP on 2n variables has AC-⊕ circuits of polynomial size. Then for any b there exists c and a polynomial p(x, y) with ≤ 2lgc n monomials such that Pr x,y [p(x, y) 6= IP(x, y)] ≤ 2lgb . Proof. Let C be a depth-(d+1) AC-⊕ circuit that computes IP over 2n input bits x1, . . . , xn, y1, . . . , yn. Let N = poly(n) denote the number of parity gates at the leaves. Let C ′ be the depth-d AC circuit obtained by replacing the i-th parity gate by a fresh input variable zi (so C ′ is a circuit over N input bits z1, ..., zN). Let D be the distribution over {−1, 1} induced by drawing a uniform random input x from {−1, 1} and setting zi = the value of the i-th parity gate on x (the draw from D is the string z ∈ {0, 1}). Let := 1/2lgc . Lemma 5.1 and Corollary 5.2 of [ABFR94] tell us that there is a polynomial p(z1, . . . , zN) of degree (O(lg(n)) 2d that computes C ′(z) for a (1 − ) fraction of all inputs drawn from D. Since p has degree (O(lg n)) it must have ≤ n n))2d monomials. Now let q(x1, ..., xn, y1, . . . , yn) be the polynomial obtained by substituting in the i-th parity (monomial) for zi in p. q has no more monomials than p, and q computes IP on (1− ) fraction of all inputs drawn from {−1, 1}. We note that for Valiant’s connection to lower bounds, we need rank R = Ω(N), whereas for sparsity much smaller rank R = poly lgN suffices. In both cases we need to go beyond error 1/R.