Imagen de Portada

Proof complexity of positive branching programs

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Das, Anupam, Delkos, Avgerinos
Formato:	Preprint
Publicado:	2021
Materias:	Computational Complexity Logic in Computer Science Logic
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

A significance-based account of ceteris paribus counterfactuals
por: Delkos, Avgerinos, et al.
Publicado: (2023)

The Proof Analysis Problem
por: Arteche, Noel, et al.
Publicado: (2025)

Proof Complexity of Linear Logics
por: Tabatabai, Amirhossein Akbar, et al.
Publicado: (2026)

Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets
por: Atserias, Albert, et al.
Publicado: (2024)

Symmetric Proofs in the Ideal Proof System
por: Dawar, Anuj, et al.
Publicado: (2025)

Proof complexity of Mal'tsev CSP
por: Gaysin, Azza
Publicado: (2025)

New Bounds for the Ideal Proof System in Positive Characteristic
por: Behera, Amik Raj, et al.
Publicado: (2025)

The complete classification for quantified equality constraints
por: Zhuk, Dmitriy, et al.
Publicado: (2021)

Functional variant of Polynomial Analogue of Gandy's Fixed Point Theorem
por: Nechesov, Andrey
Publicado: (2024)

An order out of nowhere: a new algorithm for infinite-domain CSPs
por: Mottet, Antoine, et al.
Publicado: (2023)

Parallelism and Adaptivity in Student-Teacher Witnessing
por: Ježil, Ondřej, et al.
Publicado: (2026)

Effective Versions of Strong Measure Zero
por: Rayman, Matthew
Publicado: (2025)

Meta-Mathematics of Computational Complexity Theory
por: Oliveira, Igor C.
Publicado: (2025)

On the consistency of stronger lower bounds for NEXP
por: Thapen, Neil
Publicado: (2025)

$Π_{2}^{P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem
por: Zhuk, Dmitriy
Publicado: (2024)

On the Interplay of Cube Learning and Dependency Schemes in QCDCL Proof Systems
por: Choudhury, Abhimanyu, et al.
Publicado: (2025)

Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds
por: Li, Jiawei, et al.
Publicado: (2024)

Wider systems for linear logic with fixed points: proof theory and complexity
por: Das, Anupam, et al.
Publicado: (2026)

How to fit large complexity classes into TFNP
por: Thapen, Neil
Publicado: (2024)

Proof Complexity and Feasible Interpolation
por: Tabatabai, Amirhossein Akbar
Publicado: (2025)

Non-commutative linear logic fragments with sub-context-free complexity
por: Nishimiya, Yusaku, et al.
Publicado: (2025)

Semi-Algebraic Proof Systems for QBF
por: Beyersdorff, Olaf, et al.
Publicado: (2025)

Simulation of Turing machines with analytic discrete ODEs: FPTIME and FPSPACE over the reals characterised with discrete ordinary differential equations
por: Blanc, Manon, et al.
Publicado: (2023)

On Probabilistic and Causal Reasoning with Summation Operators
por: Ibeling, Duligur, et al.
Publicado: (2024)

Measuring Decidability as Related to Busy Beaver Numbers
por: Tandi, Gurpreet, et al.
Publicado: (2026)

Network Satisfaction Problems Solved by k-Consistency
por: Bodirsky, Manuel, et al.
Publicado: (2023)

Measuring robustness of dynamical systems. Relating time and space to length and precision
por: Blanc, Manon, et al.
Publicado: (2023)

Cyclic Implicit Complexity
por: Curzi, Gianluca, et al.
Publicado: (2021)

A proof theory of (omega-)context-free languages, via non-wellfounded proofs
por: Das, Anupam, et al.
Publicado: (2024)

On $NP \cap coNP$ proof complexity generators
por: Krajicek, Jan
Publicado: (2025)

Kleene algebra with commutativity conditions is undecidable
por: de Amorim, Arthur Azevedo, et al.
Publicado: (2024)

Complexity classification of counting graph homomorphisms modulo a prime number
por: Bulatov, Andrei A., et al.
Publicado: (2021)

Temporal Team Semantics Revisited
por: Gutsfeld, Jens Oliver, et al.
Publicado: (2021)

Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution
por: Beyersdorff, Olaf, et al.
Publicado: (2021)

Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras
por: Barto, Libor, et al.
Publicado: (2021)

Galois Energy Games: To Solve All Kinds of Quantitative Reachability Problems
por: Lemke, Caroline, et al.
Publicado: (2025)

On the Number of Quantifiers Needed to Define Boolean Functions
por: Carmosino, Marco, et al.
Publicado: (2024)

On the Unprovability of Circuit Size Bounds in Intuitionistic $\mathsf{S}^1_2$
por: Chen, Lijie, et al.
Publicado: (2024)

Hardness of monadic second-order formulae over succinct graphs
por: Gamard, Guilhem, et al.
Publicado: (2023)

Hard Clique Formulas for Resolution
por: Atserias, Albert
Publicado: (2026)