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

scientific article; zbMATH DE number 7921249

Language	Label	Description	Also known as
English	Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024	scientific article; zbMATH DE number 7921249

Statements

instance of

scholarly article

0 references

title

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

0 references

published in

Oberwolfach Reports

0 references

publication date

2 October 2024

0 references

MaRDI profile type

Publication

0 references

cites work

Propositional proofs and reductions between NP search problems

0 references

Colourful TFNP and propositional proofs

0 references

Further collapses in TFNP

0 references

Adventures in monotone complexity and TFNP

0 references

Reductions in \textbf{PPP}

0 references

The relative complexity of NP search problems

0 references

PPP-completeness and extremal combinatorics

0 references

Integer factoring and modular square roots

0 references

How easy is local search?

0 references

On total functions, existence theorems and computational complexity

0 references

On the complexity of the parity argument and other inefficient proofs of existence

0 references

Extremal combinatorics, iterated pigeonhole arguments and generalizations of PPP

0 references

Q5365081

0 references

A converse to Banach's fixed point theorem and its CLS-completeness

0 references

The complexity of gradient descent: CLS = PPAD $\cap$ pls

0 references

Q4856172

0 references

On reducibility and symmetry of disjoint NP pairs.

0 references

Monotone simulations of non-monotone proofs.

0 references

On $\epsilon$-sensitive monotone computations

0 references

A combinatorial characterization of resolution width

0 references

On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems

0 references

Q5140848

0 references

Deterministic Communication vs. Partition Number

0 references

Monotone Circuits for Connectivity Require Super-Logarithmic Depth

0 references

Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic

0 references

Interpolation by a Game

0 references

Strongly exponential lower bounds for monotone computation

0 references

Proofs as Games

0 references

Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic

0 references

Separation of the monotone NC hierarchy

0 references

Dag-like communication and its applications

0 references

Resolution Is Not Automatizable Unless W[P] Is Tractable

0 references

On the automatizability of resolution and related propositional proof systems

0 references

Automating Resolution is NP-Hard

0 references

Parity Games and Propositional Proofs

0 references

Non-automatizability of bounded-depth Frege proofs

0 references

On Interpolation and Automatization for Frege Systems

0 references

Automating algebraic proof systems is NP-hard

0 references

Automating cutting planes is NP-hard

0 references

Some consequences of cryptographical conjectures for $S_2^1$ and EF

0 references

Low-depth arithmetic circuit lower bounds: bypassing set-multilinearization

0 references

Clique Is Hard on Average for Regular Resolution

0 references

A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem

0 references

The resolution complexity of independent sets and vertex covers in random graphs

0 references

Parameterized Bounded-Depth Frege Is not Optimal

0 references

On Worst‐Case to Average‐Case Reductions for NP Problems

0 references

Linear FPT reductions and computational lower bounds

0 references

Strong computational lower bounds via parameterized complexity

0 references

Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems

0 references

Fixed-parameter tractability and completeness II: On completeness for W[1]

0 references

Q4736859

0 references

On the complexity of $k$-SAT

0 references

Sum of squares lower bounds for refuting any CSP

0 references

Cliques enumeration and tree-like resolution proofs

0 references

The complexity of proving that a graph is Ramsey

0 references

Sum-of-squares Lower Bounds for Planted Clique

0 references

Q3688439

0 references

Large clique is hard on average for resolution

0 references

Space Complexity in Propositional Calculus

0 references

Proof Complexity Meets Algebra

0 references

The resolution complexity of random graph $k$-colorability

0 references

3-coloring in time

0 references

Q4228469

0 references

Graph-Coloring Ideals

0 references

Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility

0 references

Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz

0 references

Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz

0 references

Lower bounds for the polynomial calculus and the Gröbner basis algorithm

0 references

Reducibility among Combinatorial Problems

0 references

Q5111132

0 references

Limitations of Algebraic Approaches to Graph Isomorphism Testing

0 references

Homogenization and the polynomial calculus

0 references

Nullstellensatz size-degree trade-offs from reversible pebbling

0 references

The complexity of the pigeonhole principle

0 references

Approximation and Small-Depth Frege Proofs

0 references

The intractability of resolution

0 references

On Small-depth Frege Proofs for Tseitin for Grids

0 references

An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle

0 references

Exponential lower bounds for the pigeonhole principle

0 references

Poly-logarithmic Frege depth lower bounds via an expander switching lemma

0 references

On disperser/lifting properties of the index and inner-product functions

0 references

Lifting to parity decision trees via stifling

0 references

Some Subsystems of Constant-Depth Frege with Parity

0 references

Notes on resolution over linear equations

0 references

Linear branching programs and directional affine extractors

0 references

Proof complexity of natural formulas via communication arguments

0 references

Lower Bounds for Splittings by Linear Combinations

0 references

Resolution over linear equations modulo two

0 references

Randomized feasible interpolation and monotone circuits with a local oracle

0 references

Resolution with counting: dag-like lower bounds and different moduli

0 references

The monotone circuit complexity of Boolean functions

0 references

Intersection Theorems for Systems of Sets

0 references

The Monotone Complexity of $k$-Clique on Random Graphs

0 references

Separations in query complexity using cheat sheets

0 references

Supercritical Space-Width Trade-offs for Resolution

0 references

The Log-Approximate-Rank Conjecture Is False

0 references

Q6187026

0 references

Q6126308

0 references

A counter-example to the probabilistic universal graph conjecture via randomized communication complexity

0 references

A New Kind of Tradeoffs in Propositional Proof Complexity

0 references

On space and depth in resolution

0 references

On the Width of Semialgebraic Proofs and Algorithms

0 references

$\Sigma_ 1^ 1$-formulae on finite structures

0 references

Improved bounds for the sunflower lemma

0 references

Error-bounded probabilistic computations between MA and AM

0 references

$\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}$ lower bounds for the Boolean inner product

0 references

Q6126305

0 references

Parity, circuits, and the polynomial-time hierarchy

0 references

Top-down lower bounds for depth-three circuits

0 references

Separating and collapsing results on the relativized probabilistic polynomial-time hierarchy

0 references

Prediction from partial information and hindsight, with application to circuit lower bounds

0 references

Coding for Sunflowers

0 references

Lower bounds on the size of bounded depth circuits over a complete basis with logical addition

0 references

Relativized Arthur-Merlin versus Merlin-Arthur games

0 references

Prediction from partial information and hindsight, an alternative proof

0 references

AC0 Unpredictability

0 references

Q6147277

0 references

A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation

0 references

Many hard examples for resolution

0 references

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

0 references

Introduction to Semirandom Models

0 references

Q2762790

0 references

Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random

0 references

A simple and sharper proof of the hypergraph Moore bound

0 references

Strongly refuting random CSPs below the spectral threshold

0 references

Semialgebraic Proofs and Efficient Algorithm Design

0 references

Expander codes

0 references

Explicit, almost optimal, epsilon-balanced codes

0 references

Undecidability of polynomial inequalities in weighted graph homomorphism densities

0 references

Undecidability of linear inequalities in graph homomorphism densities

0 references

Linear Diophantine Equations, Group CSPs, and Graph Isomorphism

0 references

The tropical Nullstellensatz for congruences

0 references

On the power and limitations of branch and cut

0 references

Tropical effective primary and dual Nullstellensätze

0 references

On the Consistency of Circuit Lower Bounds for Non-Deterministic Time

0 references

Q5114830

0 references

Polynomial time ultrapowers and the consistency of circuit lower bounds

0 references

Q5306365

0 references

Unprovability of circuit upper bounds in Cook's theory PV

0 references

Feasibly constructive proofs of succinct weak circuit lower bounds

0 references

Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic

0 references

Strong co-nondeterministic lower bounds for NP cannot be proved feasibly

0 references

Arithmetization of the field of reals with exponentiation extended abstract

0 references

Models of VTC0$\mathsf {VTC^0}$ as exponential integer parts

0 references

Q3140641

0 references

Q5341750

0 references

Building discretely ordered Bezout domains and GCD domains

0 references

Implicit proofs

0 references

Quantified propositional calculi and fragments of bounded arithmetic

0 references

Q4535027

0 references

Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space

0 references

Some trade-off results for polynomial calculus

0 references

Proof Complexity of Quantified Boolean Logic — A Survey

0 references

Q5148371

0 references

Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution

0 references

Lower bounds for multiplayer noncooperative games of incomplete information

0 references

Dependency Quantified Boolean Formulas: An Overview of Solution Methods and Applications

0 references

Soundness of $\mathcal{Q}$-resolution with dependency schemes

0 references

Shortening QBF proofs with dependency schemes

0 references

Long-distance Q-resolution with dependency schemes

0 references

New Resolution-Based QBF Calculi and Their Proof Complexity

0 references

Frege Systems for Quantified Boolean Logic

0 references

Hardness Characterisations and Size-width Lower Bounds for QBF Resolution

0 references

Q4625702

0 references

Resolution for Max-SAT

0 references

Equivalence between systems stronger than resolution

0 references

Certified Core-Guided MaxSAT Solving

0 references

Certified dominance and symmetry breaking for combinatorial optimisation

0 references

On the complexity of cutting-plane proofs

0 references

Certified CNF translations for pseudo-Boolean solving

0 references

QMaxSATpb: a certified MaxSAT solver

0 references

A lower bound for polynomial calculus with extension rule

0 references

Semi-algebraic proofs, IPS lower bounds, and the τ-conjecture: can a natural number be negative?

0 references

A well-mixed function with circuit complexity $5n$: tightness of the Lachish-Raz-type bounds

0 references

Q4708583

0 references

Identifiers

zbMATH Open document ID

1546.00046

0 references

DOI

10.4171/owr/2024/15

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:6613418