archive
Every paper Pith has read. Search by title, abstract, or pith.
424 papers in cs.CC · page 7
-
2-local qubit Hamiltonians with succinct states are MA-complete
On the Complexity of the Succinct State Local Hamiltonian Problem
-
ReLU positivity is W[1]-hard parameterized by dimension
Parameterized Hardness of Zonotope Containment and Neural Network Verification
-
Trusted accurate AI cannot match humans on every task
Limitations on Accurate, Trusted, Human-level Reasoning
-
Computational relative entropy defined for polynomial quantum resources
Computational relative entropy
-
CHSH and Magic Square games certify Pauli observables under high noise
Nonlocal Games in the High-Noise Regime: Optimal Quantum Values and Rigidity
-
3-SAT recast as volume filling to locate phase transition
Geometric Interpretation of 3-SAT and Phase Transition
-
-
Dictionaries yield upper bounds on Koopman spectra in L^p
Residual SCI Upper Bounds And Lower Witnesses For Koopman Approximate Point Spectra In $L^p$ For $1<p<\infty$: Extended Version
-
DQI simulation fits inside the polynomial hierarchy
On the Complexity of Decoded Quantum Interferometry
-
Winner decision for 4-uniform Maker-Breaker games is PSPACE-complete
4-uniform Maker-Breaker and Maker-Maker games are PSPACE-complete
-
Treewidth makes basic vehicle routing tractable
Parameterized Complexity of Vehicle Routing
-
Rational affine verifiers match real-valued power
Rational-Valued Affine Verifiers in Arthur--Merlin Proof Systems
-
Treewidth near n/10 on real graphs makes FPT practical
The Parameter Report: An Orientation Guide for Data-Driven Parameterization
-
Linearizability check runs fast for small process counts
Fixed Parameter Tractable Linearizability Monitoring
-
Introspection with budget separates relativized P from NP
Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
-
Holant problems on hypergraphs classify parameterised VCSPs
Symmetric Parameterised Holants on Hypergraphs: Towards a Classification for Parameterised VCSPs
-
Push-1 is PSPACE-complete without fixed walls
Pushing Blocks without Fixed Walls via Checkable Gizmos: Push-1 is PSPACE-Complete
-
Grundy Domination Variants Are W[1]-Complete by Sequence Length
On the Parameterized Complexity of Grundy Domination and Zero Forcing Problems
-
Prover-adversary games characterize eLDT and eLNDT
Prover-Adversary games for systems over (non-deterministic) branching programs
-
Production control alone realizes any polynomial analog dynamics
Analog computation with transcriptional networks
-
Deterministic communication complexity is NP-complete to compute
NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing
-
Circuit complexity measures topological distance for phase learning
Quantum circuit complexity and unsupervised machine learning of topological order
-
Controlled unitaries add nothing beyond global phase info
Are controlled unitaries helpful?
-
Quantum search speedups need unitary inverse
Amplitude amplification and estimation require inverses
-
Bichromatic triangle search is PPP-complete
The PPP-completeness of the Ward-Szabo theorem
-
Undecidability of Θ(n)-block gluing shown for homshifts
Undecidability of the block gluing classes of homshifts
-
Edge-coloring with odd-cycle and clique forbids splits into P or NP-complete
Edge-coloring problems with forbidden patterns and planted colors
-
Improved semiring machines capture weighted NP logic
Fagin's Theorem for Semiring Turing Machines
-
Variables merge to strongly sparsify 1-in-3-SAT
Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
-
PageRank queries reach theoretical optimality for most graphs
Near-Optimality for Single-Source Personalized PageRank
-
Diffusion models fail on inherently serial tasks
The Serial Scaling Hypothesis
-
Constant gradients possible in super-polynomial quantum landscapes
Gradient Scalability and Taylor Surrogation of Quantum Cost Landscapes
-
Framework solves local search flips for partitioning in τ^k 2^O(k) time
Fantastic Flips and Where to Find Them: A General Framework for Parameterized Local Search on Partitioning Problems
-
Proof search hardness implies NP differs from coNP
On $NP \cap coNP$ proof complexity generators
-
No algorithm decides qPDS model-checking against PCTL
Computational Complexity of Model-Checking Quantum Pushdown Systems
-
Short Resolution proofs of Ref(φ) extract satisfying assignments
The Proof Analysis Problem
-
Generalized Hive makes winning-strategy decisions PSPACE-hard
Hive is PSPACE-Hard
-
Blocked Jacobi matches matrix multiplication communication bound
Minimizing the Arithmetic and Communication Complexity of Jacobi's Method for Eigenvalues and Singular Values: Part One -- Serial Algorithms
-
Fixed non-unitary gate lets circuits decide PostBQP problems
Computational Complexity and Simulability of Non-Hermitian Quantum Dynamics
-
Block-encoded Laplacians estimate Betti numbers in polylog time
New aspects of quantum topological data analysis: Betti number estimation, and testing and tracking of homology and cohomology classes
-
Regular hypercliques match general-case detection complexity
The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs
-
Entanglement solves some problems with zero communication
Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement
-
Deciding minimum firefighters to save a graph is NP-hard
Complexity of Firefighting on Graphs
-
Stabilizer entropy witnesses magic in mixed states
Efficient witnessing and testing of magic in mixed quantum states
-
AKS primality test proven correct in VTC^0_2
Feasibility of Primality in Bounded Arithmetic
-
Constant-distance tree codes with immediacy must vanish in rate
The Rate-Immediacy Barrier in Explicit Tree Code Constructions
-
Isometric embedding achieves constant rate 1/8 from Hamming to edit
Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric
-
CVP has no subexponential algorithm under ETH in any p-norm
Mind the Gap? Not for SVP Hardness under ETH!
-
k-round coin flips biased by O(ℓ / log^k ℓ) bad players
Improved Bounds for Coin Flipping, Leader Election, and Random Selection
-
Weighted models track knowledge gain as upskilling and loss as downskilling
Epistemic Skills: Reasoning about Knowledge and Oblivion