archive
Every paper Pith has read. Search by title, abstract, or pith.
424 papers in cs.CC · page 3
-
Quantum codes deliver exponential speedups for experiment learning
Exponential speedups in fault-tolerant processing of quantum experiments
-
Influence-weighted butterfly layers yield Schur-convex invariant for Boolean functions
The Banach-Butterfly Invariant: Influence-Adaptive Walsh Geometry for Ternary Polynomial Threshold Functions
-
The paper gives a linear-time algorithm to find a central vertex in 1/2-hyperbolic graphs…
A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
-
Low approximate sign-rank forces large monochromatic rectangles
Lower Bounds for Approximate Sign Rank
-
Polynomial samplers miss Ber(1/3) product by 1-o(1)
On Sampling Lower Bounds for Polynomials
-
Perturbed knapsack threshold keeps SOS rank at O(sqrt n log n)
On the Distribution of Unweighted Minimum Knapsack Instances with Large SOS Rank
-
Local queries yield vanishing info on sparse matrix violations
Information Accessibility Limits in Structured NP Search
-
Local queries cannot locate sparse violations in P-matrix families
Information Accessibility Limits in Structured NP Search
-
Termination of linear and affine loops over the reals admits sound partial decision…
Termination of Real Linear Loops
-
Minimizing average coalitional gains yields optimal-time equilibria
Computing Equilibrium beyond Unilateral Deviation
-
Explicit CNF families resist short tree-like semantic Frege refutations
Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
-
Symmetrized determinant is #P-hard over polynomial-sized algebras
On the Principal Minor Expansion and Complexity of the Symmetrized Determinant
-
NP inside StoqMA(2) with square-root size proofs
Unentangled stoquastic Merlin-Arthur proof systems: the power of unentanglement without destructive interference
-
Consistency implications may control simulations in arithmetic theories
Toward a Characterization of Simulation Between Arithmetic Theories
-
56-addition scheme multiplies 3x3 matrices at rank 23
An Exact 56-Addition, Rank-23 Scheme for General 3*3 Matrix Multiplication
-
Tensor spectral threshold decision is ∃R-hard
Tensor Spectral Threshold is $\exists\mathbb{R}$-Hard
-
T-wise independence sets hardness for refuting any random k-CSP
Strongly Refuting Random CSP without Literals
-
Approximate Fisher equilibria need PCP-for-PPAD conjecture for hardness
Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD
-
Classical oracle separates QMA1 from restricted QCMA
En Route to a Standard QMA1 vs. QCMA Oracle Separation
-
Quantum channel certification shows strict hierarchy in query costs
Strict Hierarchy for Quantum Channel Certification to Unitary
-
-
-
Ulam k-center on permutations is FPT for k+d
Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
-
S^1_2 stays consistent with EXP not in P/poly
From G\"odel incompleteness to the consistency of circuit lower bounds
-
Concise secant varieties correspond exactly to minimal border rank tensors
Unrestrictions and concise secant varieties
-
Active learning uses constant CoT per thinker with log-log thinkers
Learning to Think from Multiple Thinkers
-
Every primitive recursive function is iteration of one fixed ReLU network
Primitive Recursion without Composition: Dynamical Characterizations, from Neural Networks to Polynomial ODEs
-
Complexity map for vertex merges to chordal subclasses
Identification to Subclasses of Chordal Graphs
-
Maximum matching size in general graphs is in catalytic logspace
Maximum Matching and Related Problems in Catalytic Logspace
-
7-vertex tree detectable as induced minor in polynomial time
On Detecting $H$-Induced Minors for Small $H$
-
Regular grammars give singly-exponential recognizers for SP graphs
Regular Grammars as Effective Representations of Recognizable Sets of Series-Parallel Graphs
-
Polynomial-time method completes overlapping phylogenetic trees
Polynomial-time completion of phylogenetic tree sets
-
Gate elimination proofs now yield algorithms to refute small circuits
Constructive Separations from Gate Elimination
-
Finding a 3-vertex TC subgraph is NP-hard
On the Hardness of Finding Temporally Connected Subgraphs of Any Size
-
Fourier analysis classifies Boolean promise problems
Boolean PCSPs through the lens of Fourier Analysis
-
Quantum moment estimation needs exactly half-order replicas
The Exact Replica Threshold for Nonlinear Moments of Quantum States
-
Continuous clustering matches hardness of real polynomial equations
How Hard Is Continuous Clustering? Lower Bounds from the Existential Theory of the Reals
-
Dynamic planar graph isomorphism is in DynFO
Dynamic Planar Graph Isomorphism is in DynFO
-
Turnstile algorithms on poly-length streams reduce to linear sketches
Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
-
Non-commutative circuits need Omega(n^1.5) product gates for degree-n polynomials
Polynomial Lower Bounds for Arithmetic Circuits over Non-Commutative Rings
-
Non-redundancy sets single-pass streaming space for CSPs
Characterizing Streaming Decidability of CSPs via Non-Redundancy
-
Non-redundancy sets single-pass space for CSP satisfiability
Characterizing Streaming Decidability of CSPs via Non-Redundancy
-
Efficient sampler for hardcore model on bipartite graphs up to λ ≲ 1/√Δ
Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold
-
Circuits over simple algebras classify languages exactly
Complexity Classes Arising from Circuits over Finite Algebraic Structures
-
Reproducible experiments compute definite physical functions
Experiments, Computability, and the Existence of Physical Functions
-
Exact kernel exponent pinned for rainbow-free coloring
Kernelization Bounds for Constrained Coloring
-
Noncommutative circuits for palindromes need size Omega(nd)
A Quadratic Lower Bound for Noncommutative Circuits
-
Noncommutative circuits need quadratic size for palindromes
A Quadratic Lower Bound for Noncommutative Circuits
-
Border subrank computed exactly for higher-order algebra tensors
Border subrank of higher order tensors and algebras
-
Allowed CNOT synthesis removes qubit routing overhead
Qubit Routing for (Almost) Free