archive
Every paper Pith has read. Search by title, abstract, or pith.
424 papers in cs.CC · page 6
-
Random strings block poly-time halting oracle for chosen machine
Limit on the computational power of $\mathrm{C}$-random strings
-
Curvature changes flag critical graph edges
On Identifying Critical Network Edges via Analyzing Changes in Shapes (Curvatures)
-
Local Nash convergence implies P equals PPAD
On the Complexity of Learning Nash Equilibria
-
Algebraic conditions decide all finite-domain CSP complexity
Graph Homomorphisms and Universal Algebra
-
Binary strings listed with fixed time and fixed extra memory
Gray Codes With Constant Delay and Constant Auxiliary Space
-
DTMs solve SAT and Subset-Sum inside polynomial bounds
Implementation of Polynomial NP-Complete Algorithms Based on the NP Verifier Simulation Framework
-
Common subgraph without isolates is NP-hard but FPT by h
Parameterized Complexity of Finding a Maximum Common Vertex Subgraph Without Isolated Vertices
-
Local inspection fails to decide dominating sets in random graphs
Self-referential instances of the dominating set problem are irreducible
-
Classical oracle separates QMA from QCMA
Separating Quantum and Classical Advice with Good Codes
-
Scaling map on complexity space is expansive iff factor ≠1
Expansive homeomorphisms on complexity quasi-metric spaces
-
Heisenberg antiferromagnet phase signs reduce to Max-Cut
Graph-Theoretic Analysis of Phase Optimization Complexity in Variational Wave Functions for Heisenberg Antiferromagnets
-
Chordal graphs have a unique minimal meg-set
An Algorithm for Monitoring Edge-geodetic Sets in Chordal Graphs
-
Counting homs to non-abelian groups is #P-hard
Obstruction theory and the complexity of counting group homomorphisms
-
Heap polymorphism metaproblem is NP-complete
The complexity of finding coset-generating polymorphisms and the promise metaproblem
-
Block sensitivity cannot condense losslessly to O(k) variables
Bounds for Hardness Condensation in the Query Model
-
Infinite CSPs split into FO-definable or L-hard
Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
-
FPT algorithm for #k-matching disproves ETH
$\#$W[1] = $\text{FPT}$: Fixed-Parameter Tractable Exact Algorithms for the $\#k$-Matching Problem
-
AgentDoG diagnoses root causes of unsafe AI agent actions
AgentDoG: A Diagnostic Guardrail Framework for AI Agent Safety and Security
-
Assembly index decision problem is NP-complete
Computational Complexity of Determining the Assembly Index
-
Next prime resists shortcut algorithms beyond sequential checks
Prime Successor Irreducibility: Turing Machine Complexity, Kolmogorov Complexity, and Weakness-Based Formulations
-
Free expander walks build explicit codes matching GV bound
Explicit Almost-Optimal $\varepsilon$-Balanced Codes via Free Expander Walks
-
Boolean function degree at most cube of rational degree
Rational degree is polynomially related to degree
-
Rank-2 quantum entropies hard to estimate for all orders
Computational hardness of estimating quantum entropies via binary entropy bounds
-
Symmetric measure tracks net information change while conserving totals
Conserved active information
-
Billiard paths simulate Turing machines
Classical billiards can compute
-
Bin packing needs |I|^{2^{o(d)}} time unless ETH fails
A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
-
First explicit formula for three-row Kronecker coefficient
Algebraic Obstructions and the Collapse of Elementary Structure in the Kronecker Problem
-
Constraint embedding lifts QAOA feasible mass exponentially for permutations
Fundamental Limitations of QAOA on Constrained Problems and a Route to Exponential Enhancement
-
Hybrid protocols obey c plus q squared lower bound
A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
-
Connectivity-preserving separators enumerated in 2^{O(k log k)}
Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems
-
Tighter shadow bounds boost randomized simplex success probability
Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming
-
Unbiased estimator preserves protected matrix queries exactly
Graded Projection Recursion (GPR): Corrections, Obstructions, and Conservative Approximate Matrix Multiplication
-
f-Critical Set problem is NP-complete on planar subcubic bipartite graphs
Parameterized complexity of the f-Critical Set problem
-
Heavy hitters recovered with exp(sqrt(d)) Fourier coefficients
Model-agnostic super-resolution in high dimensions
-
Log(n) qubits suffice for anticoncentrated n-bit sampling
Anticoncentrated $n$-bit distribution from $\log(n)$ qubits
-
Testable Boolean properties match those with computable partition symmetry
Efficient and Private Property Testing via Indistinguishability
-
Quasipolylog rounds for (Δ+1)-coloring when neighborhood independence is bounded
Distributed $(\Delta+1)$-Coloring in Graphs of Bounded Neighborhood Independence
-
Every MAX-k-SAT instance has exponentially many near-optimal assignments
A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
-
Giant component in knowledge graph cuts augmentation queries to constant
Prior Knowledge Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methods
-
Lexicographic local search for 4-SAT is PLS-complete
PLS-complete problems with lexicographic cost functions: Max-$k$-SAT and Abelian Permutation Orbit Minimization
-
Unit-distance graph recognition in Z^2 is NP-complete
Determining unit distance graphs with coordinates in $\mathbb{Z}^2$ is NP-complete
-
Constant complexity clashes with linear lower bound on SAT messages
A Quantale-Weakness Route to $P \neq NP$ via CD Evidence Normalization and Gauge-Buffered Locked Ensembles
-
Quantized GNN verification is decidable yet (co)NEXPTIME-complete
Verifying Quantized GNNs With Readout Is Decidable But Highly Intractable
-
Tree algorithm learns MPS in log depth with cubic samples
Efficient Matrix Product State Learning in Logarithmic Depth
-
Conjugate queries solve oracle problems no inverse queries can
Conjugate queries can help
-
Polynomial samples verify samplable distributions against adversaries
Cryptographic Conditions for Efficient Testing of Distributions and Quantum States
-
Quantum queries estimate CVaR subgradients in O(1/ε)
Quantum Subgradient Estimation for Conditional Value-at-Risk Optimization
-
Cubic equations encode proof checking at each fixed resource level
Considering The Satisfiability of Cubic Diophantine Equations
-
Black-box stats privatized via data-query trade-off
Privately Estimating Black-Box Statistics
-
Stoquastic Hamiltonians stay BPP-hard even with guiding states
The Guided Local Hamiltonian Problem for Stoquastic Hamiltonians