On the Symmetries of and Equivalence Test for Design Polynomials.

DOI10.4230/LIPICS.MFCS.2019.53OpenAlexW2971181757MaRDI QIDQ5092415FDOQ5092415

Authors: N. Gupta, Chandan Saha 

Publication date: 21 July 2022

Full work available at URL: https://dblp.uni-trier.de/db/conf/mfcs/mfcs2019.html#GuptaS19

Recommendations

• On the complexity of symmetric polynomials
• Affine projections of symmetric polynomials.
• Deterministic polynomial identity testing in non-commutative models
• Testing polynomial equivalence by scaling matrices
• Diagonal Circuit Identity Testing and Lower Bounds

zbMATH Keywords

Lie algebraequivalence testgroup of symmetriesflip theoremcharacterization by symmetriescircuit testabilityNisan-Wigderson design polynomial

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Hardness vs randomness
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Title not available (Why is that?)
• The monotone circuit complexity of Boolean functions
• Title not available (Why is that?)
• Geometric aspects of iterated matrix multiplication
• Title not available (Why is that?)
• An almost cubic lower bound for depth three arithmetic circuits
• Lower bounds on arithmetic circuits via partial derivatives
• Geometric complexity theory. I: An approach to the P vs. NP and related problems
• An exponential lower bound for homogeneous depth four arithmetic formulas
• Lower bounds for depth-three arithmetic circuits with small bottom fanin
• The boundary of the orbit of the 3-by-3 determinant polynomial
• Title not available (Why is that?)
• Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits
• A super-polynomial lower bound for regular arithmetic formulas
• Sums of products of polynomials in few variables: lower bounds and polynomial identity testing
• Affine projections of polynomials (extended abstract)
• Approaching the chasm at depth four
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• Natural proofs
• Lower bounds and separations for constant depth multilinear circuits
• On P vs. NP and geometric complexity theory: dedicated to Sri Ramakrishna
• On vanishing of Kronecker coefficients
• Partial derivatives in arithmetic complexity and beyond
• The Permanent Function
• Barriers for rank methods in arithmetic complexity
• Proving SAT does not have small circuits with an application to the two queries problem
• Lie Groups, Lie Algebras, and Representations
• Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
• Lower Bounds in a Parallel Model without Bit Operations
• Title not available (Why is that?)
• Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity
• On the power of homogeneous depth 4 arithmetic circuits
• Arithmetic circuits with locally low algebraic rank
• On the size of homogeneous and of depth four formulas with low individual degree
• Succinct hitting sets and barriers to proving algebraic circuits lower bounds
• Generalized matrix completion and algebraic natural proofs
• Title not available (Why is that?)
• Reconstruction of full rank algebraic branching programs
• Lower bounds for depth-4 formulas computing iterated matrix multiplication
• Depth-4 lower bounds, determinantal complexity: a unified approach
• Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications.

This page was built for publication: On the Symmetries of and Equivalence Test for Design Polynomials.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5092415)