scientific article; zbMATH DE number 1256733
From MaRDI portal
Publication:4228469
zbMath0938.68825MaRDI QIDQ4228469
Matthew Clegg, Russell Impagliazzo, Jeffery Edmonds
Publication date: 18 May 1999
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
From Small Space to Small Width in Resolution, Narrow Proofs May Be Maximally Long, Computation with Polynomial Equations and Inequalities Arising in Combinatorial Optimization, Limitations of Algebraic Approaches to Graph Isomorphism Testing, Unnamed Item, Randomized feasible interpolation and monotone circuits with a local oracle, Representing and solving finite-domain constraint problems using systems of polynomials, Proof complexity in algebraic systems and bounded depth Frege systems with modular counting, Characterizing Propositional Proofs as Noncommutative Formulas, Some consequences of cryptographical conjectures for \(S_2^1\) and EF, Space Complexity in Polynomial Calculus, A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝 Frege systems], Collapsing modular counting in bounded arithmetic and constant depth propositional proofs, The power of the binary value principle, Algebraic proof systems over formulas., Resolution lower bounds for the weak functional pigeonhole principle., Obtaining and solving systems of equations in key variables only for the small variants of AES, Space characterizations of complexity measures and size-space trade-offs in propositional proof systems, Algebraic Attacks against Random Local Functions and Their Countermeasures, On vanishing sums of roots of unity in polynomial calculus and sum-of-squares, Propositional proofs and reductions between NP search problems, Algebraic proofs over noncommutative formulas, On the automatizability of polynomial calculus, Proof Complexity Meets Algebra, An Introduction to Lower Bounds on Resolution Proof Systems, Unnamed Item, The complexity of properly learning simple concept classes, Solving hybrid Boolean constraints in continuous space via multilinear Fourier expansions, Automatizability and Simple Stochastic Games, Formal Verification of Integer Multiplier Circuits Using Algebraic Reasoning: A Survey, A combinatorial characterization of resolution width, On the complexity of Hilbert refutations for partition, Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution, Uniformly generated submodules of permutation modules over fields of characteristic 0., Space proof complexity for random 3-CNFs, Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity, Linear gaps between degrees for the polynomial calculus modulo distinct primes, Several notes on the power of Gomory-Chvátal cuts, Unnamed Item, Resolution with counting: dag-like lower bounds and different moduli, Complexity of Null- and Positivstellensatz proofs, A Framework for Space Complexity in Algebraic Proof Systems, Nullstellensatz size-degree trade-offs from reversible pebbling, On the correspondence between arithmetic theories and propositional proof systems – a survey, Short propositional refutations for dense random 3CNF formulas, Supercritical Space-Width Trade-offs for Resolution, A combinatorial characterization of treelike resolution space, Proof Complexity of Non-classical Logics, Propositional proof complexity, Conservative Retractions of Propositional Logic Theories by Means of Boolean Derivatives: Theoretical Foundations, Short Proofs Are Hard to Find, Size-degree trade-offs for sums-of-squares and positivstellensatz proofs, Good degree bounds on Nullstellensatz refutations of the induction principle, Polybori: A framework for Gröbner-basis computations with Boolean polynomials, Nullstellensatz size-degree trade-offs from reversible pebbling, Unnamed Item, Unnamed Item, Unnamed Item, Another look at degree lower bounds for polynomial calculus, Space bounds for resolution, The resolution complexity of random graph \(k\)-colorability, Reflections on Proof Complexity and Counting Principles, Polynomials for classification trees and applications
