archive
Every paper Pith has read. Search by title, abstract, or pith.
424 papers in cs.CC · page 5
-
Learning pseudorandom data forces ML models toward uniform outputs
How Does Machine Learning Manage Complexity?
-
NP definition forces forbidden complete proof systems
On Formally Undecidable Propositions of Nondeterministic Complexity and Related Classes
-
Majority is least stable only below tight noise thresholds for n≥5
When Majority Fails: Tight Bounds for Correlation Distillation Conjectures
-
Polymorphism minion alone decides CSP solvability by consistency hierarchies
Toward a Uniform Algorithm and Uniform Reduction for Constraint Problems
-
Maximizing Solow-Polasky diversity is NP-hard in general metrics
Selecting a Maximum Solow-Polasky Diversity Subset in General Metric Spaces Is NP-hard
-
All SMB algebras yield tractable CSP templates
SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks
-
Strong proof systems fail feasible disjunction property under hardness
Failure of the strong feasible disjunction property
-
Symmetric modular circuits need subexponential size for AND
Optimal Lower Bounds for Symmetric Modular Circuits
-
Reduction turns subset balancing into one infinity-norm SVP instance
Subset Balancing and Generalized Subset Sum via Lattices
-
Vehicle routing encoded with colored permutations needs no extra capacity qubits
Optimal, Qubit-Efficient Quantum Vehicle Routing via Colored-Permutations
-
Symmetric generators tighten equivalence-query round bounds
Learning from Equivalence Queries, Revisited
-
Point-line incidence needs Θ(log n) communication
No Constant-Cost Protocol for Point--Line Incidence
-
Double-commutator eigenvector recovers optimal covariance group
Polynomial-Time Optimal Group Selection via the Double-Commutator Eigenvalue Problem
-
QAC0 computes Parity exactly when it has high Fourier mass
Parity $\notin$ QAC0 $\iff$ QAC0 is Fourier-Concentrated
-
TreeEval solved in poly time with almost log space
Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling
-
Method finds efficient algorithms for bounded hard problems
Towards Solving NP-Complete and Other Hard Problems Efficiently in Practice
-
Minimum recoloring to end p-illusion is NP-hard on bipartite DAGs
Eliminating Illusion in Directed Networks
-
Exact Matching on bipartite graphs solved in O(n^6) time
Bipartite Exact Matching in P
-
SVP hard to approximate within nearly 2^{log n} in any lattice norm
Deterministic Hardness of Approximation For SVP in all Finite $\ell_p$ Norms
-
Streaming CSPs need Ω(√n/p) space to beat LP threshold
Near-Optimal Space Lower Bounds for Streaming CSPs
-
Shallow circuits learn any trivial-phase mixed state from measurements
Learning and Generating Mixed States Prepared by Shallow Channel Circuits
-
Shallow circuits learn any trivial-phase mixed state from measurements
Learning and Generating Mixed States Prepared by Shallow Channel Circuits
-
Low-degree algorithms distort tensor spectral norm by p^{d/4-1/2}
A Framework for Computational Lower Bounds in Nontrivial Norm Approximation
-
Polynomial-size mABPs compute full-rank multilinear polynomials
An Unconditional Barrier for Proving Multilinear Algebraic Branching Program Lower Bounds
-
New encoding uses 2n + 2√(2n) clauses for AtMostOne
Near-Optimal Encodings of Cardinality Constraints
-
Commitment depth matches the polynomial hierarchy
On the Complexity of Determinations
-
Maximize signal per token to keep LLM conversations coherent
The Root Theorem of Context Engineering
-
Graph model shows BVA reencodes 2-CNFs to ~0.4 n²/lg n clauses
Automated Reencoding Meets Graph Theory
-
Quadratic bosonic simulation is BQP-complete for key cases
Complexity of Quadratic Bosonic Hamiltonian Simulation: $\mathsf{BQP}$-Completeness and $\mathsf{PostBQP}$-Hardness
-
Generator choice does not change non-deterministic power
Dual-Tape Perspective and Generator Independence: The Algebraic Foundation of Real Boolean Turing Machines
-
Non-determinism equals field extension in GF(4)
Complex Boolean Turing Machines: An Algebraic Semantic Framework for Computational Complexity
-
b-Chromatic number hard on some H-free graphs while tight version is easy
Optimal b-Colourings and Fall Colourings in $H$-Free Graphs
-
Estimation of high-order tensors succeeds where detection fails
Detection Is Harder Than Estimation in Certain Regimes: Inference for Moment and Cumulant Tensors
-
Single RETURN statement simulates any 2-counter machine
Cypher is Turing-Complete: A Formal Proof via 2-Counter Machine Simulation
-
Correlation cone membership and rank problems are NP-hard
Hardness of some optimization problems over correlation polyhedra
-
Decision datasets compress to size d* with PAC rate O(d*/n)
Learning Decision-Sufficient Representations for Linear Optimization
-
New approximation notion lies strictly between FPTAS and P
An approximation notion between P and FPTAS
-
Counting dominating sets is #P-complete on 3-regular planar bipartite graphs
The Counting General Dominating Set Framework
-
Jaguar evaluates queries in N to the submodular width plus epsilon
Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time
-
Visibly recursive automata extend procedural automata
Visibly Recursive Automata
-
Parsing is always constrained by input while generation need not be
The Generation-Recognition Asymmetry: Six Dimensions of a Fundamental Divide in Formal Language Theory
-
LLM agent raises lower bounds on nine Ramsey numbers
Reinforced Generation of Combinatorial Structures: Ramsey Numbers
-
Tighter bound makes graph complexity track information measures more linearly
An improved upper bound measure of star complexity of graphs
-
3×3 matrix multiplication over F₂ needs at least 20 bilinear operations
Automated Lower Bounds for Small Matrix Multiplication Complexity over Finite Fields
-
3x3 matrix multiplication over F2 needs at least 20 multiplications
Automated Lower Bounds for Small Matrix Multiplication Complexity over Finite Fields
-
Polynomial probes yield o(1) bits for NP witness recovery
Intrinsic Information Flow in Structureless NP Search
-
Recurrent GNNs equal recurrent arithmetic circuits over reals
Recurrent Graph Neural Networks and Arithmetic Circuits
-
Single-writer rule puts release-acquire consistency in polynomial time
Complexity of Consistency Testing for the Release-Acquire Semantics
-
2-Solo Chess NP-complete for knights and kings
Completing the Complexity Classification of 2-Solo Chess: Knights and Kings are Hard
-
Short-output problems require exponential memory for best queries
On the Need for (Quantum) Memory with Short Outputs