:: Library Catalog

Beeld op de omslag

Bewaard in:

Bibliografische gegevens
Hoofdauteurs:	Dawar, Anuj, Wilsenach, Gregory
Formaat:	Preprint
Gepubliceerd in:	2020
Onderwerpen:	Computational Complexity Discrete Mathematics Logic in Computer Science F.1.3; F.2.1
Online toegang:	https://arxiv.org/abs/2002.06451
Tags:	Voeg label toe Geen labels, Wees de eerste die dit record labelt!

Gelijkaardige items

Lower Bounds for Symmetric Circuits for the Determinant
door: Dawar, Anuj, et al.
Gepubliceerd in: (2021)

PosSLP and Sum of Squares
door: Bläser, Markus, et al.
Gepubliceerd in: (2024)

Notes on CSPs and Polymorphisms
door: Brady, Zarathustra
Gepubliceerd in: (2022)

The Banach-Butterfly Invariant: Influence-Adaptive Walsh Geometry for Ternary Polynomial Threshold Functions
door: Pavlov, Gorgi
Gepubliceerd in: (2026)

Hereditary First-Order Logic: the tractable quantifier prefix classes
door: Bodirsky, Manuel, et al.
Gepubliceerd in: (2024)

On the Computational Power of Extensional ESO
door: Bodirsky, Manuel, et al.
Gepubliceerd in: (2025)

Hardness of busy beaver value BB(15)
door: Stérin, Tristan, et al.
Gepubliceerd in: (2021)

Misère Partizan Arc Kayles is PSPACE-complete, even on Planar Graphs
door: Burke, Kyle, et al.
Gepubliceerd in: (2025)

Imperative process algebra and models of computation
door: Middelburg, C. A.
Gepubliceerd in: (2022)

On the Satisfaction Probabilities of $k$-CNF Formulas
door: Tantau, Till
Gepubliceerd in: (2022)

On the Complexity of Problems on Graphs Defined on Groups
door: Das, Bireswar, et al.
Gepubliceerd in: (2025)

On the Counting Complexity of the Skolem Problem
door: Jindal, Gorav, et al.
Gepubliceerd in: (2024)

Reduction of the graph isomorphism problem to equality checking of $n$-variables polynomials and the algorithms that use the reduction
door: Prolubnikov, Alexander
Gepubliceerd in: (2015)

Characterizing NC1 with Typed Monoids
door: Dawar, Anuj, et al.
Gepubliceerd in: (2025)

SAT problem and Limit of Solomonoff's inductive reasoning theory
door: Pan, Feng
Gepubliceerd in: (2025)

Rankwidth of Graphs with Balanced Separations: Expansion for Dense Graphs
door: Anand, Emile
Gepubliceerd in: (2025)

A Note on the NP-Hardness of PARTITION Via First-Order Projections
door: Iturralde, Paúl Risco
Gepubliceerd in: (2025)

Homomorphism Indistinguishability and Game Comonads for Restricted Conjunction and Requantification
door: Schindling, Georg
Gepubliceerd in: (2025)

Polynomial-time Tractable Problems over the $p$-adic Numbers
door: Fehm, Arno, et al.
Gepubliceerd in: (2025)

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
door: de Rezende, Susanna F., et al.
Gepubliceerd in: (2019)

Algorithmic hardness of the partition function for nucleic acid strands
door: Ducloz, Gwendal, et al.
Gepubliceerd in: (2025)

The Bit Complexity of Dynamic Algebraic Formulas and their Determinants
door: Anand, Emile, et al.
Gepubliceerd in: (2024)

Constructibility and the P versus NP problem
door: Hole, Arne
Gepubliceerd in: (2024)

Guaranteed Bounds on Posterior Distributions of Discrete Probabilistic Programs with Loops
door: Zaiser, Fabian, et al.
Gepubliceerd in: (2024)

Beyond Worst-Case Subset Sum: An Adaptive, Structure-Aware Solver with Sub-$2^{n/2}$ Enumeration
door: Salas, Jesus
Gepubliceerd in: (2025)

On Sampling Lower Bounds for Polynomials
door: Khodabandeh, Mohammad Mahdi, et al.
Gepubliceerd in: (2026)

Graph Neural Networks and Arithmetic Circuits
door: Barlag, Timon, et al.
Gepubliceerd in: (2024)

Average Attention Transformers and Arithmetic Circuits
door: Ehrmuth, Lena, et al.
Gepubliceerd in: (2026)

Lower Bounds on Inverse Cellular Automata via Proof Complexity
door: Kapytka, Maryia
Gepubliceerd in: (2026)

The Unit Gap: How Sharing Works in Boolean Circuits
door: Krinkin, Kirill
Gepubliceerd in: (2026)

Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations
door: Antonelli, Melissa, et al.
Gepubliceerd in: (2025)

Recurrent Graph Neural Networks and Arithmetic Circuits
door: Barlag, Timon, et al.
Gepubliceerd in: (2026)

A LOCAL View of the Polynomial Hierarchy
door: Reiter, Fabian
Gepubliceerd in: (2023)

A Complete Finitary Refinement Type System for Scott-Open Properties
door: Riba, Colin, et al.
Gepubliceerd in: (2026)

A SAT-based Approach for Specification, Analysis, and Justification of Reductions between NP-complete Problems
door: Janičić, Predrag
Gepubliceerd in: (2025)

Supercritical Tradeoffs for Monotone Circuits
door: Göös, Mika, et al.
Gepubliceerd in: (2024)

Arithmetic Complexity of Solutions of the Dirichlet Problem
door: Boche, Holger, et al.
Gepubliceerd in: (2026)

An efficient algorithm to compute the minimum free energy of interacting nucleic acid strands
door: Shalaby, Ahmed, et al.
Gepubliceerd in: (2024)

Finitely (In)tractable Promise Constraint Satisfaction Problems
door: Asimi, Kristina, et al.
Gepubliceerd in: (2020)

An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
door: Lela, Marko
Gepubliceerd in: (2025)