Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024

DOI10.4171/owr/2024/15zbMath1546.00046MaRDI QIDQ6613418

No author found.

Publication date: 2 October 2024

Published in: Oberwolfach Reports (Search for Journal in Brave)

Analysis of algorithms and problem complexity (68Q25) Proceedings of conferences of miscellaneous specific interest (00B25) Proceedings, conferences, collections, etc. pertaining to computer science (68-06) Collections of abstracts of lectures (00B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Proceedings, conferences, collections, etc. pertaining to mathematical logic and foundations (03-06) Complexity of proofs (03F20) Networks and circuits as models of computation; circuit complexity (68Q06) Communication complexity, information complexity (68Q11)

Cites Work

An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
Strongly refuting random CSPs below the spectral threshold
Sum of squares lower bounds for refuting any CSP
Explicit, almost optimal, epsilon-balanced codes
Strongly exponential lower bounds for monotone computation
Reducibility among Combinatorial Problems
Introduction to Semirandom Models
On Small-depth Frege Proofs for Tseitin for Grids
Clique Is Hard on Average for Regular Resolution
AC0 Unpredictability
Adventures in monotone complexity and TFNP
Coding for Sunflowers
Frege Systems for Quantified Boolean Logic
The Log-Approximate-Rank Conjecture Is False
Automating Resolution is NP-Hard
Semi-algebraic proofs, IPS lower bounds, and the τ-conjecture: can a natural number be negative?
Automating cutting planes is NP-hard
Parity Games and Propositional Proofs
New Resolution-Based QBF Calculi and Their Proof Complexity
Supercritical Space-Width Trade-offs for Resolution
Semialgebraic Proofs and Efficient Algorithm Design
A converse to Banach's fixed point theorem and its CLS-completeness
Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
Implicit proofs
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Poly-logarithmic Frege depth lower bounds via an expander switching lemma
Separations in query complexity using cheat sheets
Undecidability of linear inequalities in graph homomorphism densities
The Monotone Complexity of $k$-Clique on Random Graphs
Some trade-off results for polynomial calculus
On Worst‐Case to Average‐Case Reductions for NP Problems
Hardness Characterisations and Size-width Lower Bounds for QBF Resolution
Dependency Quantified Boolean Formulas: An Overview of Solution Methods and Applications
On the complexity of $k$-SAT
Lower bounds for multiplayer noncooperative games of incomplete information
Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random
Automating algebraic proof systems is NP-hard
Strong co-nondeterministic lower bounds for NP cannot be proved feasibly
Models of VTC0$\mathsf {VTC^0}$ as exponential integer parts
Proof complexity of natural formulas via communication arguments
On the power and limitations of branch and cut
A lower bound for polynomial calculus with extension rule
Undecidability of polynomial inequalities in weighted graph homomorphism densities
Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution
Proof Complexity of Quantified Boolean Logic — A Survey
A simple and sharper proof of the hypergraph Moore bound
On the Consistency of Circuit Lower Bounds for Non-Deterministic Time
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation
Certified dominance and symmetry breaking for combinatorial optimisation
Certified Core-Guided MaxSAT Solving
The complexity of gradient descent: CLS = PPAD $\cap$ pls
Linear branching programs and directional affine extractors
Further collapses in TFNP
Certified CNF translations for pseudo-Boolean solving
On disperser/lifting properties of the index and inner-product functions
PPP-completeness and extremal combinatorics
Lifting to parity decision trees via stifling
Extremal combinatorics, iterated pigeonhole arguments and generalizations of PPP
Low-depth arithmetic circuit lower bounds: bypassing set-multilinearization
Colourful TFNP and propositional proofs
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Propositional proofs and reductions between NP search problems
The tropical Nullstellensatz for congruences
On the complexity of cutting-plane proofs
Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
Fixed-parameter tractability and completeness II: On completeness for W[1]
Exponential lower bounds for the pigeonhole principle
Building discretely ordered Bezout domains and GCD domains
On total functions, existence theorems and computational complexity
Strong computational lower bounds via parameterized complexity
Integer factoring and modular square roots
Soundness of $\mathcal{Q}$-resolution with dependency schemes
Resolution for Max-SAT
$\Sigma_ 1^ 1$-formulae on finite structures
The intractability of resolution
The monotone circuit complexity of Boolean functions
Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
How easy is local search?
Relativized Arthur-Merlin versus Merlin-Arthur games
The relative complexity of NP search problems
On the complexity of the parity argument and other inefficient proofs of existence
The complexity of the pigeonhole principle
Some consequences of cryptographical conjectures for $S_2^1$ and EF
On reducibility and symmetry of disjoint NP pairs.
Homogenization and the polynomial calculus
On space and depth in resolution
$\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}$ lower bounds for the Boolean inner product
Shortening QBF proofs with dependency schemes
The complexity of proving that a graph is Ramsey
Cliques enumeration and tree-like resolution proofs
Reductions in \textbf{PPP}
Tropical effective primary and dual Nullstellensätze
Prediction from partial information and hindsight, an alternative proof
Non-automatizability of bounded-depth Frege proofs
Monotone simulations of non-monotone proofs.
On the automatizability of resolution and related propositional proof systems
Top-down lower bounds for depth-three circuits
Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
Lower bounds for the polynomial calculus and the Gröbner basis algorithm
Separation of the monotone NC hierarchy
Feasibly constructive proofs of succinct weak circuit lower bounds
Resolution with counting: dag-like lower bounds and different moduli
Nullstellensatz size-degree trade-offs from reversible pebbling
Improved bounds for the sunflower lemma
A counter-example to the probabilistic universal graph conjecture via randomized communication complexity
Large clique is hard on average for resolution
On $\epsilon$-sensitive monotone computations
Polynomial time ultrapowers and the consistency of circuit lower bounds
Prediction from partial information and hindsight, with application to circuit lower bounds
Notes on resolution over linear equations
Resolution over linear equations modulo two
Dag-like communication and its applications
Long-distance Q-resolution with dependency schemes
A well-mixed function with circuit complexity $5n$: tightness of the Lachish-Raz-type bounds
The resolution complexity of independent sets and vertex covers in random graphs
A combinatorial characterization of resolution width
Error-bounded probabilistic computations between MA and AM
The resolution complexity of random graph $k$-colorability
Equivalence between systems stronger than resolution
QMaxSATpb: a certified MaxSAT solver
On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems
Proofs as Games
Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space
Graph-Coloring Ideals
Lower Bounds for Splittings by Linear Combinations
Sum-of-squares Lower Bounds for Planted Clique
Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic
Parameterized Bounded-Depth Frege Is not Optimal
Unprovability of circuit upper bounds in Cook's theory PV
Expander codes
Space Complexity in Propositional Calculus
A New Kind of Tradeoffs in Propositional Proof Complexity
Intersection Theorems for Systems of Sets
Parity, circuits, and the polynomial-time hierarchy
Resolution Is Not Automatizable Unless W[P Is Tractable]
Limitations of Algebraic Approaches to Graph Isomorphism Testing
Monotone Circuits for Connectivity Require Super-Logarithmic Depth
Quantified propositional calculi and fragments of bounded arithmetic
Separating and collapsing results on the relativized probabilistic polynomial-time hierarchy
Many hard examples for resolution
Arithmetization of the field of reals with exponentiation extended abstract
Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz
Linear FPT reductions and computational lower bounds
Approximation and Small-Depth Frege Proofs
Interpolation by a Game
Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
On Interpolation and Automatization for Frege Systems
Deterministic Communication vs. Partition Number
Randomized feasible interpolation and monotone circuits with a local oracle
Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
On the Width of Semialgebraic Proofs and Algorithms
Some Subsystems of Constant-Depth Frege with Parity
Proof Complexity Meets Algebra
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
3-coloring in time

This page was built for publication: Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024