archive
Every paper Pith has read. Search by title, abstract, or pith.
424 papers in cs.CC · page 1
-
ODE schemas characterize every FAC0[n] circuit class
Recursion and proof theoretical characterizations of small circuit classes with modulo counting via discrete differential equations (long version)
-
MAX-ETR-INV is ∃R-hard to approximate better than 1-ε
Probabilistically checkable proofs for the Existential Theory of the Reals
-
Approximate degree polynomially bounded by non-deterministic degrees for monotone and read
On the Approximate Non-Deterministic Degree of Total Boolean Functions
-
Omega(n/eps^2) queries needed for clustering approximation
Query Lower Bounds for Correlation Clustering under Memory Constraints
-
Transformers have fixed accuracy limits set by layers and width
The Deterministic Horizon: Impossibility Results as Design Specifications for Trustworthy AI Systems
-
Min-Sum-Radii stays W[1]-hard for k plus cost on bipartite graphs
On the Parameterized Complexity of Min-Sum-Radii
-
QAOA sampling hard at degree 3
A sharp interaction-degree threshold for simulating QAOA
-
Deciding Quoridor winners is PSPACE-complete
Quoridor is PSPACE-Complete
-
Projection of flags complex gives sub-polynomial expander
A Simple Sub-Polynomial Degree Coboundary Expander
5 Piths -
Asymptotic rank of cw_2 drops below 3.931
Asymptotic Rank Speedup Theorems, Revisited
-
Mixed test characterizes adaptive separation rates in sparse functional testing
Linear Functional Testing with General Loadings in Sparse Regression: Separation Rates and Computational Barriers
-
DP solves IA fragment in 4^n time
Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming
-
Any sequence reduces to a poly-time random one in quasi-polynomial time
Resource bounded Ku\v{c}era-G\'{a}cs Theorems
4 Piths -
Grid sketch achieves optimal Wasserstein runtime for smooth laws
Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation
-
Position-dependent attention fixes constant risk on shifted reasoning
A Measure-Theoretic Analysis of Reasoning: Structural Generalization and Approximation Limits
-
Tinhofer hierarchy has P-hard level checks
A Hierarchy of Tinhofer Graphs: Separations and Membership Testing
-
CVaR Pandora's box keeps exact index solution
Risk of Bad Tails: CVaR-Aware Pandora's Box and Prophet Inequality
-
Quantum algorithm beats Grover bound using depth-d states
An Entropy-Governed Speedup for Quantum Algorithms on Local Hamiltonians
-
Interconnection trees NP-complete to find but fast with few parts
Complexity of Finding and Enumerating Interconnection Trees
-
Low-precision softmax transformers simulate Turing machines via CoT
The Expressive Power of Low Precision Softmax Transformers with (Summarized) Chain-of-Thought
-
Controller placement games on graphs are NP-complete or ΣP2-complete
Modelling Network Resilience: The Complexity of Some Graph Division Games
-
Reductions spread hidden NP witness info for local inference
Information Redistribution Under Reductions in NP Search
-
Extremum stack minimally encodes rate-independent functionals
The Extremum Stack is a Minimal Sufficient Statistic for Rate-Independent Functionals: A Kolmogorov Complexity Characterisation
-
Stoquastic multi-prover proofs collapse to single prover
The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems
2 Piths -
FPT algorithms for broadcast independence via treewidth and diameter
On the parameterized complexity of Broadcast Independence and Broadcast Packing
-
Sampling from demand gives 2-approx for robotaxi placement
The Robotaxi Placement Problem: Minimizing Expected ETA for Stochastic Demand
-
The paper shows that low-energy states of non-Abelian topological orders have extensive…
Extensive long-range magic in non-Abelian topological orders
-
Unanimity opinion rules allow efficient PAC learning of influence networks
On the Limits of PAC Learning of Networks from Opinion Dynamics
-
Nested reset counters hit exact F_Ωk levels
The Complexity of Nested Reset Counter Systems
-
O(n log h) prep yields O(1) leaf-to-ancestor min queries
Fast Leaf-to-Ancestor Minimum Query in the Oracle Model
-
Unary recoding enables polynomial-time rule learning for LLMs
Enhanced and Efficient Reasoning in Large Learning Models
-
Symmetric Boolean CSP non-redundancy classified up to O(n^3)
Non-Redundancy of Low-Arity Symmetric Boolean CSPs
-
Min-max optimization needs exponentially many queries
Min-Max Optimization Requires Exponentially Many Queries
-
Exact small-marginal match forces exponential closeness in larger ones
Upper Bounds for Symmetric Approximate Bounded Indistinguishability
-
Region switches set regret rate in polyhedral online learning
Polyhedral Instability Governs Regret in Online Learning
-
Gallai vertex decision is Θ₂^p-complete
The Gallai Vertex Problem is $\Theta_2^p$-Complete
4 Piths -
Shortcut problem NP-hard for k>=2 and rho>=k+2
On the Complexity of the Minimum-($k,\rho$)-Shortcut Problem
-
Correlation Clustering gets poly kernels from bounded fuzzy degeneracy
Clustering with Locally Bounded Ignorance
-
Symmetric difference quantifies diversity of argument extensions
Diversity of Extensions in Abstract Argumentation
-
Greedy builds small approximating trees on product distributions
Decision Tree Learning on Product Spaces
-
Mechanized proofs confirm LFPL captures polynomial time exactly
LFPL: Revisited and Mechanized
-
LCL complexity on trees shifts without exact n knowledge
The Distributed Complexity Landscape on Trees Depends on the Knowledge About the Network Size
1 Piths -
Tight query bounds set for non-Hermitian QSP simulation
Optimal Bounds, Barriers, and Extensions for Non-Hermitian Bivariate Quantum Signal Processing
-
Mixed-state quantum isomorphism is QSZK-complete
Quantum state isomorphism problems for groups
-
Bivariate QSP gives optimal simulation of non-Hermitian Hamiltonians
Simulation of Non-Hermitian Hamiltonians with Bivariate Quantum Signal Processing
-
SDD and d-SDNNF systems produce smaller refutations than OBDDs
Proof Systems Based on Structured Circuits
-
Clausal deletions yield FPT for QBF on two base classes
Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approach
-
Promise rank problem resists approximation past tiny factor
Strong Inapproximability for a Promise Rank Problem
-
Feedback sets NP-complete on degree-3 digraphs
Feedback Set Problems on Bounded-Degree (Planar) Graphs
-
Random dense graphs force exponential refutations for binary clique
Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity