FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
From MaRDI portal
Publication:5897760
DOI10.1007/11590156zbMath1172.68479MaRDI 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
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Lower bounds for matrix factorization, Derandomization from Algebraic Hardness, Sylvester-Gallai type theorems for quadratic polynomials, A generalized sylvester-gallai type theorem for quadratic polynomials, Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits, Depth-4 Identity Testing and Noether’s Normalization Lemma, Unnamed Item, Testing the satisfiability of algebraic formulas over the field of two elements, Subexponential size hitting sets for bounded depth multilinear formulas, A Wronskian approach to the real \(\tau\)-conjecture, Lower bounds against weakly-uniform threshold circuits, Read-once polynomial identity testing, Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in, Deterministically testing sparse polynomial identities of unbounded degree, Deterministic identity testing for sum of read-once oblivious arithmetic branching programs, Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing, A case of depth-3 identity testing, sparse factorization and duality, Linear matroid intersection is in quasi-NC, Lower bounds for matrix factorization, Blackbox identity testing for sum of special ROABPs and its border class, Equivalence of polynomial identity testing and polynomial factorization, Mining circuit lower bound proofs for meta-algorithms, Unifying known lower bounds via geometric complexity theory, 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, 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, Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
