ﻻ يوجد ملخص باللغة العربية
For every constant c > 0, we show that there is a family {P_{N, c}} of polynomials whose degree and algebraic circuit complexity are polynomially bounded in the number of variables, that satisfies the following properties: * For every family {f_n} of polynomials in VP, where f_n is an n variate polynomial of degree at most n^c with bounded integer coefficients and for N = binom{n^c + n}{n}, P_{N,c} emph{vanishes} on the coefficient vector of f_n. * There exists a family {h_n} of polynomials where h_n is an n variate polynomial of degree at most n^c with bounded integer coefficients such that for N = binom{n^c + n}{n}, P_{N,c} emph{does not vanish} on the coefficient vector of h_n. In other words, there are efficiently computable equations for polynomials in VP that have small integer coefficients. In fact, we also prove an analogous statement for the seemingly larger class VNP. Thus, in this setting of polynomials with small integer coefficients, this provides evidence emph{against} a natural proof like barrier for proving algebraic circuit lower bounds, a framework for which was proposed in the works of Forbes, Shpilka and Volk (2018), and Grochow, Kumar, Saks and Saraf (2017). Our proofs are elementary and rely on the existence of (non-explicit) hitting sets for VP (and VNP) to show that there are efficiently constructible, low degree equations for these classes. Our proofs also extend to finite fields of small size.
We observe that a certain kind of algebraic proof - which covers essentially all known algebraic circuit lower bounds to date - cannot be used to prove lower bounds against VP if and only if what we call succinct hitting sets exist for VP. This is an
This article describes a formal strategy of geometric complexity theory (GCT) to resolve the {em self referential paradox} in the $P$ vs. $NP$ and related problems. The strategy, called the {em flip}, is to go for {em explicit proofs} of these proble
Geometric complexity theory (GCT) is an approach to the P vs. NP and related problems. This article gives its complexity theoretic overview without assuming any background in algebraic geometry or representation theory.
We study the computational complexity of approximating the 2->q norm of linear operators (defined as ||A||_{2->q} = sup_v ||Av||_q/||v||_2), as well as connections between this question and issues arising in quantum information theory and the study o
This note is purely expository and is in Russian. We show how to prove interesting combinatorial results using the local Lovasz lemma. The note is accessible for students having basic knowledge of combinatorics; the notion of independence is defined