archive
Every paper Pith has read. Search by title, abstract, or pith.
424 papers in cs.CC · page 4
-
Quasi-polynomial simulation of bosonic circuits with log Kerr gates
Coherent-State Propagation: A Computational Framework for Simulating Bosonic Quantum Systems
-
Diversity subset selection is NP-hard even for Euclidean plane points
Maximum Solow--Polasky Diversity Subset Selection Is NP-hard Even in the Euclidean Plane
-
Maximum-finding algorithm extended to inputs with ties
Parity Tests with Ties
-
Lions clear trees with pathwidth or one extra lion
Lions and Contamination: Trees and General Graphs
-
Quantum embedding counts graph motifs in logspace
Quantum embedding of graphs for subgraph counting
-
Capacitated Vertex Cover needs k^{Omega(k)} time under ETH
Parameterized Capacitated Vertex Cover Revisited
-
Quantum functionals anchor new points in Strassen's asymptotic spectrum
On quantum functionals for higher-order tensors
-
Tensoring one-coordinate coverings isolates small balanced subgraphs in vector-labeled dig
Coordinatewise Balanced Covering for Linear Gain Graphs, with an Application to Coset-List Min-2-Lin over Powers of Two
-
Cache size s forces depth to scale as k/s times log n for reasoning
How Much Cache Does Reasoning Need? Depth-Cache Tradeoffs in KV-Compressed Transformers
-
Network caching is FPT parameterized by number of caches
Homogeneous Network Caching is Fixed-Parameter Tractable Parameterized by the Number of Caches
-
Inhibitory CRNs turn deletion-only reachability NP-complete
Reachability with Restricted Reactions in Inhibitory Chemical Reaction Networks
-
Turing machine metastable closure is non-computable
Metastability-Containing Turing Machines
-
Greedy alignment methods reach constant regret
Demystifying the unreasonable effectiveness of online alignment methods
-
Tensor degeneracy is ∃ℝ-complete via algebraic reductions
$\exists\mathbb{R}$-Completeness of Tensor Degeneracy and a Derandomization Barrier for Hyperdeterminants
-
Complexity hides most entanglement from efficient observers
Accessible Quantum Correlations Under Complexity Constraints
-
The paper studies the parameterized complexity of coloring mixed graphs that combine…
The Parameterized Complexity of Coloring Mixed Graphs
-
IQP circuits solve 2-Forrelation in two queries
IQP circuits for 2-Forrelation
-
Constant alphabet subspace design codes constructed explicitly
Explicit Constant-Alphabet Subspace Design Codes
-
Fungal automata prediction is P-complete for majority rule at radius 1.5
Complexity of Fungal Automaton Prediction
-
Spread clauses enable sub-exponential SAT gap solvers
A Hypergraph Container Method on Spread SAT: Approximation and Speedup
-
Online CoT equates multi-layer SSMs with streaming algorithms
On the Expressive Power and Limitations of Multi-Layer SSMs
-
CRNs compute all semilinear predicates with reversible reactions
Reverse-Robust Computation with Chemical Reaction Networks
-
Pinwheel problem proven NP-hard
NP-Hardness and a PTAS for the Pinwheel Problem
-
Group isomorphism for key families lands in AC³
Parallel Algorithms for Group Isomorphism via Code Equivalence
-
VQCs reach exact ground states only if module projection norms match
Reachability Constraints in Variational Quantum Circuits: Optimization within Polynomial Group Module
-
Reachability undecidable under Release/Acquire without RMWs
On the Decidability of Verification under Release/Acquire
-
Local Hamiltonians split into three complexity classes at EPR*
A complexity phase transition at the EPR Hamiltonian
-
Symmetric subrank growth rate determined for degree-d forms
Symmetric subrank and its border analogue
-
Sharpness equals worst-case exactness for SCI but not pointwise
From Witness-Space Sharpness To Family-Pointwise Exactness For The Solvability Complexity Index
-
Three exactness levels for SCI on problem families
From Witness-Space Sharpness To Family-Pointwise Exactness For The Solvability Complexity Index
-
0-1 edge weights for distinct vertex sums are hard by feedback vertex set
The Parameterized Complexity of Vertex-Coloring Edge-Weighting
-
Classical algorithms match short-path quantum speed for CSPs
Dequantizing Short-Path Quantum Algorithms
-
BQP ⊆ MIP relativizes to every classical oracle
A Relativizing MIP for BQP
-
Borsuk problem extended to graphs in two diameter settings
The Borsuk number of a graph
-
Intelligence is the ratio of independent outputs to description length
A Quantitative Definition of Intelligence
-
Private coins drop out of DP distribution proofs at moderate privacy
Differentially Private Verification of Distribution Properties
-
Noisy k-XOR recovered above n^{k/2}/(D^{k/2-1} δ²) threshold
Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
-
Discrepancy bounds give faster algorithms for k-constraint ILPs
Algorithms for Standard-form ILP Problems via Koml\'os' Discrepancy Setting
-
Linear ODEs blow up in simulation complexity except for degenerate cases
Complexity Theory meets Ordinary Differential Equations
-
Linear space required for single-pass Max-CSP approximation under LP gaps
Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
-
MSO2 models represented by linear-size decision diagrams
Parameterized Complexity Of Representing Models Of MSO Formulas
-
Spectral test detects planted cliques from hypergraph matrix at √n
Planted clique detection and recovery from the hypergraph adjacency matrix
-
Tarski fixed points on 2D grids need Omega((log n)^2) quantum queries
The Quantum Query Complexity of Finding a Tarski Fixed Point on the 2D Grid
-
Degree-d PTFs have polylog Boolean surface area
The Boolean surface area of polynomial threshold functions
-
Quantum unidirectional tests need n to a power less than 1/2 queries
Quantum Property Testing for Bounded-Degree Directed Graphs
-
Small quantum computers classify massive data with exponential size savings
Exponential quantum advantage in processing massive classical data
-
One C program harbours countably infinite vulnerabilities
Vulnerability Abundance: A formal proof of infinite vulnerabilities in code
-
Affine witness produces orbit disagreements blocking exact classification
Descent Before Hardness: Orbit-Gap Obstructions in Exact Certification
-
Orbit gaps block exact structural classification of tractability
Descent Before Hardness: Orbit-Gap Obstructions in Exact Certification
-
SoS cannot refute kt planted cliques below n to a power less than 1/2
Multiple Planted Structures Below $\sqrt{n}$: An SoS Integrality Gap and an SQ Lower Bound