scientific article; zbMATH DE number 1256733

Cited in

(95)

A combinatorial characterization of treelike resolution space
Polybori: A framework for Gröbner-basis computations with Boolean polynomials
Good degree bounds on Nullstellensatz refutations of the induction principle
Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
Some consequences of cryptographical conjectures for \(S_2^1\) and EF
Algebraic proof systems over formulas.
Resolution lower bounds for the weak functional pigeonhole principle.
Space bounds for resolution
On the automatizability of polynomial calculus
Space proof complexity for random 3-CNFs
Resolution with counting: dag-like lower bounds and different moduli
Nullstellensatz size-degree trade-offs from reversible pebbling
Solving hybrid Boolean constraints in continuous space via multilinear Fourier expansions
On the complexity of Hilbert refutations for partition
Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
Another look at degree lower bounds for polynomial calculus
The complexity of properly learning simple concept classes
A combinatorial characterization of resolution width
Several notes on the power of Gomory-Chvátal cuts
Polynomials for classification trees and applications
The resolution complexity of random graph \(k\)-colorability
A framework for space complexity in algebraic proof systems
Computation with polynomial equations and inequalities arising in combinatorial optimization
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
Automatizability and simple stochastic games
The relation between polynomial calculus, Sherali-Adams, and sum-of-squares proofs
Limitations of algebraic approaches to graph isomorphism testing
Representing and solving finite-domain constraint problems using systems of polynomials
On the correspondence between arithmetic theories and propositional proof systems – a survey
Conservative Retractions of Propositional Logic Theories by Means of Boolean Derivatives: Theoretical Foundations
Propositional proofs and reductions between NP search problems
Randomized feasible interpolation and monotone circuits with a local oracle
Characterizing propositional proofs as noncommutative formulas
Algebraic attacks against random local functions and their countermeasures
Proof Complexity Meets Algebra
A finite-model-theoretic view on propositional proof complexity
Efficient reduction of nondeterministic automata with application to language inclusion testing
scientific article; zbMATH DE number 7029312 (Why is no real title available?)
Reflections on Proof Complexity and Counting Principles
scientific article; zbMATH DE number 7471587 (Why is no real title available?)
Short Proofs Are Hard to Find
Nullstellensatz size-degree trade-offs from reversible pebbling
Size-degree trade-offs for sums-of-squares and positivstellensatz proofs
scientific article; zbMATH DE number 7561756 (Why is no real title available?)
An Introduction to Lower Bounds on Resolution Proof Systems
Formal Verification of Integer Multiplier Circuits Using Algebraic Reasoning: A Survey
Supercritical space-width trade-offs for resolution
From small space to small width in resolution
Narrow proofs may be maximally long
Proof complexity of non-classical logics
Uniformly generated submodules of permutation modules over fields of characteristic 0.
Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
Linear gaps between degrees for the polynomial calculus modulo distinct primes
Complexity of Null- and Positivstellensatz proofs
The power of the binary value principle
Propositional proof complexity
Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
On vanishing sums of roots of unity in polynomial calculus and sum-of-squares
Obtaining and solving systems of equations in key variables only for the small variants of AES
Algebraic proofs over noncommutative formulas
Perfect matching in random graphs is as hard as Tseitin
Semialgebraic proofs, IPS lower bounds, and the -conjecture: can a natural number be negative?
Graphs with large girth and chromatic number are hard for Nullstellensatz
Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
First-order reasoning and efficient semi-algebraic proofs
Cutting planes width and the complexity of graph isomorphism refutations
Practical algebraic calculus and Nullstellensatz with the checkers Pacheck and Pastèque and Nuss-Checker
Polynomial calculus for optimization
Feasible interpolation for polynomial calculus and sums-of-squares
Polynomial calculus space and resolution width
Towards an understanding of polynomial calculus: new separations and lower bounds
New lower bounds for polynomial calculus over non-Boolean bases
Bounds on the total coefficient size of nullstellensatz proofs of the pigeonhole principle
Lower bounds for set-blocked clauses proofs
TFNP intersections through the Lens of feasible disjunction
Proving unsatisfiability with hitting formulas
A simple supercritical tradeoff between size and height in resolution
The power of the binary value principle
Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphs
A generalized method for proving polynomial calculus degree lower bounds
Separations in proof complexity and TFNP
Resolution over linear equations: combinatorial games for tree-like size and space
Polynomial calculus for quantified Boolean logic: lower bounds through circuits and degree
Pebble games and algebraic proof systems
Pebble games and algebraic proof systems
A classical proof system for quantum unsatisfiability, based on a matrix Nullstellensatz
Tropical proof systems: between R(CP) and resolution
A lower bound for polynomial calculus with extension rule
The ideal membership problem and abelian groups
Symmetric proofs in the ideal proof system
New bounds for the ideal proof system in positive characteristic
On the degree automatability of sum-of-squares proofs
Short propositional refutations for dense random 3CNF formulas

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4228469)