On the Symmetries of and Equivalence Test for Design Polynomials.

DOI10.4230/LIPIcs.MFCS.2019.53OpenAlexW2971181757MaRDI QIDQ5092415

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Geometric aspects of iterated matrix multiplication
• Lower bounds for depth-three arithmetic circuits with small bottom fanin
• The boundary of the orbit of the 3-by-3 determinant polynomial
• Lower bounds and separations for constant depth multilinear circuits
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• The monotone circuit complexity of Boolean functions
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Hardness vs randomness
• Lower bounds on arithmetic circuits via partial derivatives
• On vanishing of Kronecker coefficients
• Proving SAT does not have small circuits with an application to the two queries problem
• Geometric Complexity Theory I: An Approach to thePvs.NPand Related Problems
• Partial Derivatives in Arithmetic Complexity and Beyond
• Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication
• Depth-4 Lower Bounds, Determinantal Complexity : A Unified Approach
• An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
• On the Power of Homogeneous Depth 4 Arithmetic Circuits
• On P vs. NP and geometric complexity theory
• The Permanent Function
• Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications.
• Lower Bounds in a Parallel Model without Bit Operations
• Succinct hitting sets and barriers to proving algebraic circuits lower bounds
• Barriers for Rank Methods in Arithmetic Complexity
• Reconstruction of Full Rank Algebraic Branching Programs
• Superpolynomial Lower Bounds for General Homogeneous Depth 4 Arithmetic Circuits
• Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
• Generalized matrix completion and algebraic natural proofs
• Lie Groups, Lie Algebras, and Representations
• A super-polynomial lower bound for regular arithmetic formulas
• On the size of homogeneous and of depth four formulas with low individual degree
• Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity
• Affine projections of polynomials
• Approaching the Chasm at Depth Four
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• Natural proofs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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