FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
From MaRDI portal
Publication:5897760
DOI10.1007/11590156zbMath1172.68479OpenAlexW2484051058MaRDI QIDQ5897760
Publication date: 14 November 2006
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11590156
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (35)
Subexponential size hitting sets for bounded depth multilinear formulas ⋮ Derandomization from Algebraic Hardness ⋮ Deterministic identity testing for sum of read-once oblivious arithmetic branching programs ⋮ Testing the satisfiability of algebraic formulas over the field of two elements ⋮ Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing ⋮ Unnamed Item ⋮ A case of depth-3 identity testing, sparse factorization and duality ⋮ Unnamed Item ⋮ Sylvester-Gallai type theorems for quadratic polynomials ⋮ Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in ⋮ Unnamed Item ⋮ Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size ⋮ A Wronskian approach to the real \(\tau\)-conjecture ⋮ Lower bounds against weakly-uniform threshold circuits ⋮ Read-once polynomial identity testing ⋮ On the Arithmetic Complexity of Euler Function ⋮ Recent Results on Polynomial Identity Testing ⋮ Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth ⋮ Algebraic Independence and Blackbox Identity Testing ⋮ Depth-4 Identity Testing and Noether’s Normalization Lemma ⋮ Deterministically testing sparse polynomial identities of unbounded degree ⋮ Unnamed Item ⋮ Linear matroid intersection is in quasi-NC ⋮ Lower bounds for matrix factorization ⋮ Blackbox identity testing for sum of special ROABPs and its border class ⋮ Arithmetic Circuits: A Chasm at Depth 3 ⋮ Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits ⋮ Geometric complexity theory V: Efficient algorithms for Noether normalization ⋮ A generalized sylvester-gallai type theorem for quadratic polynomials ⋮ Unnamed Item ⋮ Lower bounds for matrix factorization ⋮ Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits ⋮ Equivalence of polynomial identity testing and polynomial factorization ⋮ Mining circuit lower bound proofs for meta-algorithms ⋮ Unifying known lower bounds via geometric complexity theory
This page was built for publication: FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
