ترغب بنشر مسار تعليمي؟ اضغط هنا

On the Existence of Algebraically Natural Proofs

163   0   0.0 ( 0 )
 نشر من قبل Anamay Tengse
 تاريخ النشر 2020
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

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 alogous to the Razborov-Rudich natural proofs barrier in Boolean circuit complexity, in that we rule out a large class of lower bound techniques under a derandomization assumption. We also discuss connections between this algebraic natural proofs barrier, geometric complexity theory, and (algebraic) proof complexity.
93 - Ketan Mulmuley 2010
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 ms. By an explicit proof we mean a proof that constructs proof certificates of hardness that are easy to verify, construct and decode. The main result in this paper says that (1) any proof of the arithmetic implication of the $P$ vs. $NP$ conjecture is close to an explicit proof in the sense that it can be transformed into an explicit proof by proving in addition that arithmetic circuit identity testing can be derandomized in a blackbox fashion, and (2) stronger forms of these arithmetic hardness and derandomization conjectures together imply a polynomial time algorithm for a formidable explicit construction problem in algebraic geometry. This may explain why these conjectures, which look so elementary at the surface, have turned out to be so hard.
116 - Ketan D. Mulmuley 2009
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 f Khots Unique Games Conjecture (UGC). We show the following: 1. For any constant even integer q>=4, a graph $G$ is a small-set expander if and only if the projector into the span of the top eigenvectors of Gs adjacency matrix has bounded 2->q norm. As a corollary, a good approximation to the 2->q norm will refute the Small-Set Expansion Conjecture--a close variant of the UGC. We also show that such a good approximation can be obtained in exp(n^(2/q)) time, thus obtaining a different proof of the known subexponential algorithm for Small Set Expansion. 2. Constant rounds of the Sum of Squares semidefinite programing hierarchy certify an upper bound on the 2->4 norm of the projector to low-degree polynomials over the Boolean cube, as well certify the unsatisfiability of the noisy cube and short code based instances of Unique Games considered by prior works. This improves on the previous upper bound of exp(poly log n) rounds (for the short code), as well as separates the Sum of Squares/Lasserre hierarchy from weaker hierarchies that were known to require omega(1) rounds. 3. We show reductions between computing the 2->4 norm and computing the injective tensor norm of a tensor, a problem with connections to quantum information theory. Three corollaries are: (i) the 2->4 norm is NP-hard to approximate to precision inverse-polynomial in the dimension, (ii) the 2->4 norm does not have a good approximation (in the sense above) unless 3-SAT can be solved in time exp(sqrt(n) polylog(n)), and (iii) known algorithms for the quantum separability problem imply a non-trivial additive approximation for the 2->4 norm.
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 and the Lovasz lemma is stated and proved. Our exposition follows `Probabilistic methods of N. Alon and J. Spencer. The main difference is that we show how the proof could have been invented. The material is presented as a sequence of problems, which is peculiar not only to Zen monasteries but also to advanced mathematical education; most problems are presented with hints or solutions.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا