Derandomizing polynomial identity tests means proving circuit lower bounds
From MaRDI portal
Publication:5916126
DOI10.1007/s00037-004-0182-6zbMath1089.68042OpenAlexW2026036943WikidataQ29399306 ScholiaQ29399306MaRDI QIDQ5916126
Russell Impagliazzo, Valentine Kabanets
Publication date: 23 February 2005
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-004-0182-6
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
A Combinatorial Algorithm for Computing the Rank of a Generic Partitioned Matrix with 2 $$\times $$ 2 Submatrices, Equality Testing of Compressed Strings, Constructive Non-Commutative Rank Computation Is in Deterministic Polynomial Time., Unnamed Item, Quantified Derandomization: How to Find Water in the Ocean, Nonuniform ACC Circuit Lower Bounds, Derandomization from Algebraic Hardness, Evaluating Matrix Circuits, Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space, Connections between graphs and matrix spaces, Sampling Algebraic Varieties for Sum of Squares Programs, Schur polynomials do not have small formulas if the determinant does not, A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with \(2 \times 2\) submatrices, Unnamed Item, Unnamed Item, Interactions of computational complexity theory and mathematics, Sylvester-Gallai type theorems for quadratic polynomials, Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs, Catch them if you can, Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints, Robust optimization in the presence of uncertainty, Sorting noisy data with partial information, New affine-invariant codes from lifting, H-wise independence, Sparse extractor families for all the entropy, On the power of conditional samples in distribution testing, Unnamed Item, Subspace Arrangements, Graph Rigidity and Derandomization Through Submodular Optimization, Algorithms Based on *-Algebras, and Their Applications to Isomorphism of Polynomials with One Secret, Group Isomorphism, and Polynomial Identity Testing, Witnessing matrix identities and proof complexity, Recent Results on Polynomial Identity Testing, Pseudo-Derandomizing Learning and Approximation, Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth, Algebraic Independence and Blackbox Identity Testing, Sums of Read-Once Formulas: How Many Summands Suffice?, Depth-4 Identity Testing and Noether’s Normalization Lemma, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Parallel identity testing for skew circuits with big powers and applications, Linear representation of transversal matroids and gammoids parameterized by rank, Computing the nc-Rank via Discrete Convex Optimization on CAT(0) Spaces, In a World of P=BPP, Unnamed Item, A generalized sylvester-gallai type theorem for quadratic polynomials, Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings, On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models, Unnamed Item, From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces, Emptiness Problems for Integer Circuits, Trading GRH for algebra: Algorithms for factoring polynomials and related structures, Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace, Unnamed Item, Parallel algorithms for matroid intersection and matroid parity, Constructive non-commutative rank computation is in deterministic polynomial time, Subexponential size hitting sets for bounded depth multilinear formulas, Factors of low individual degree polynomials, Faster sparse multivariate polynomial interpolation of straight-line programs, Circuit lower bounds from learning-theoretic approaches, Monomials, multilinearity and identity testing in simple read-restricted circuits, Reconstructive dispersers and hitting set generators, Amplifying circuit lower bounds against polynomial time, with applications, Is Valiant-Vazirani's isolation probability improvable?, Uniform derandomization from pathetic lower bounds, Non-commutative Edmonds' problem and matrix semi-invariants, Tripartite-to-bipartite entanglement transformation by stochastic local operations and classical communication and the structure of matrix spaces, Emptiness problems for integer circuits, Parallel Identity Testing for Skew Circuits with Big Powers and Applications, Isomorphism testing of read-once functions and polynomials, Pseudorandom generators for combinatorial checkerboards, Sums of read-once formulas: how many summands are necessary?, Deterministic identity testing for sum of read-once oblivious arithmetic branching programs, Ranks of linear matrix pencils separate simultaneous similarity orbits, Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing, Deterministic polynomial identity tests for multilinear bounded-read formulae, On derandomization and average-case complexity of monotone functions, Pseudorandom generators, typically-correct derandomization, and circuit lower bounds, Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms, Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds, Weak derandomization of weak algorithms: explicit versions of Yao's lemma, Massive online teaching to bounded learners, Learning mixtures of spherical gaussians, Low-weight halfspaces for sparse boolean vectors, Learnability of DNF with representation-specific queries, Can theories be tested?, Making evolution rigorous, On the convergence of the Hegselmann-Krause system, Is privacy compatible with truthfulness?, Differentially private data analysis of social networks via restricted sensitivity, Characterizing the sample complexity of private learners, Barriers in cryptography with weak, correlated and leaky sources, On the possibilities and limitations of pseudodeterministic algorithms, Evasiveness through a circuit lens, The garden-hose model, Space-bounded communication complexity, Towards an optimal query efficient PCP?, A characterization of approximation resistance for even k-partite CSPs, On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction, On the power of many one-bit provers, Approaching utopia, Learning and incentives in user-generated content, Welfare maximization and the supermodular degree, Reachability in graph timelines, Runtime guarantees for regression problems, An energy complexity model for algorithms, Streaming computations with a loquacious prover, Adversary lower bound for the k-sum problem, Stronger methods of making quantum interactive proofs perfectly complete, Active self-assembly of algorithmic shapes and patterns in polylogarithmic time, An equational approach to secure multi-party computation, Publicly verifiable proofs of sequential work, On the power of nonuniformity in proofs of security, Fast reductions from RAMs to delegatable succinct constraint satisfaction problems, Resource-based corruptions and the combinatorics of hidden diversity, Time hierarchies for sampling distributions, Properties and applications of boolean function composition, Pseudo-partitions, transversality and locality, Competing provers protocols for circuit evaluation, Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in, A Wronskian approach to the real \(\tau\)-conjecture, Lower bounds against weakly-uniform threshold circuits, Read-once polynomial identity testing, The complexity of two problems on arithmetic circuits, Evaluation of circuits over nilpotent and polycyclic groups, Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games, Fourier concentration from shrinkage, Deterministically testing sparse polynomial identities of unbounded degree, Finding paths of length \(k\) in \(O^{*}(2^k)\) time, A note on parameterized polynomial identity testing using hitting set generators, Building above read-once polynomials: identity testing and hardness of representation, On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant, Complexity of packing common bases in matroids, Blackbox identity testing for sum of special ROABPs and its border class, Natural Proofs versus Derandomization, Efficient learning algorithms yield circuit lower bounds, Factorization of polynomials given by arithmetic branching programs, Arithmetic Circuits: A Chasm at Depth 3, Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties), Exotic quantifiers, complexity classes, and complete problems, Operator scaling: theory and applications, A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with \(2\times 2\) submatrices, Geometric complexity theory V: Efficient algorithms for Noether normalization, Edmonds' problem and the membership problem for orbit semigroups of quiver representations, Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly, Book Review: Inevitable randomness in discrete mathematics, Improved hitting set for orbit of ROABPs, A combinatorial algorithm for computing the rank of a generic partitioned matrix with \(2 \times 2\) submatrices, Computing valuations of the Dieudonné determinants, Equivalence of polynomial identity testing and polynomial factorization, Mining circuit lower bound proofs for meta-algorithms, Monomials in arithmetic circuits: complete problems in the counting hierarchy, Generalized Wong sequences and their applications to Edmonds' problems, Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization, Compression techniques in group theory
