archive
Every paper Pith has read. Search by title, abstract, or pith.
424 papers in cs.CC · page 8
-
Weighted models track knowledge gain via upskilling and loss via downskilling
Epistemic Skills: Reasoning about Knowledge and Oblivion
-
Merge Sort gains 1.5x from network base cases
Improving Merge Sort and Quick Sort Performance by Utilizing Alphadev's Sorting Networks as Base Cases
-
Low-degree polynomials fail below BBP and Kesten-Stigum thresholds
Sharp Phase Transitions in Estimation with Low-Degree Polynomials
-
Stoquastic Hamiltonians on 2D lattices are StoqMA-complete
The Complexity of Local Stoquastic Hamiltonians on 2D Lattices
-
Dichotomy classifies monoid equations with added relations
Equations over Finite Monoids with Infinite Promises
-
Fair graph problems are FPT by cluster vertex deletion under a condition
Fair Vertex Problems Parameterized by Cluster Vertex Deletion
-
Poly-time algorithm builds minimal faithful reps for Fitting-free groups
Complexity of Constructing Minimal Faithful Permutation Representations for Fitting-free Groups
-
Jelly-No is PSPACE-complete with multiple colors
Complexity of Jelly-No and Hanano games with various constraints
-
Approximate hypergraph colouring is NP-hard except one case
Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings
-
Independent Set stays hard under n^{1/2-o(1)} edits
Answering Related Questions
-
Smallest graph with rank ℓ needs exactly 3ℓ vertices
Stable Set Polytopes with Rank $|V(G)|/3$ for the Lov\'{a}sz--Schrijver SDP Operator
-
CMSO-transductions output modular
CMSO-transducing tree-like graph decompositions
-
New problems enable unconditional quantumness proofs under tiny space
Unconditional proofs of quantumness between small-space machines
-
L1 vector of size (m+n)/2 avoids m hyperplanes
Hyperplanes Avoiding Problem and Integer Points Counting in Polyhedra
-
Proof of ML AGI impossibility rests on unstated data distribution
Barriers to Complexity-Theoretic Proofs that "AGI" Using Machine Learning is Impossible
-
Junta distributions learned with O(2^k log n / ε²) samples
Learning junta distributions, quantum junta states, and QAC$^0$ circuits
-
Bosonic min-energy problem is NP-complete at constant stellar rank
Bosonic Quantum Computational Complexity
-
Parameters split line-based dial-a-ride into easy and hard cases
The Complexity of Counting Turns in the Line-Based Dial-a-Ride Problem
-
Bipartite graphs resist fixed-s-club partitioning for most constant s
Disjoint covering of bipartite graphs with $s$-clubs
-
Hybrid algorithm matches hardness for satisfiable Max-CSPs
On Approximability of Satisfiable k-CSPs: V
-
Parallel counting matches sequential work via log-depth sampling reduction
Work-Efficient Parallel Counting via Sampling
-
Survey maps zkSNARK tradeoffs across blockchain and ML uses
A Survey on the Applications of Zero-Knowledge Proofs
-
Gadget reductions mark exactly the CSPs solvable by slam Datalog
Symmetric Linear Arc Monadic Datalog and Gadget Reductions
-
Non-determinism required for super-linear paths in directed non-cooperative aTAM
A linear bound for the size of the finite terminal assembly of a directed non-cooperative tile assembly system
-
Polymer placements obey recurrences for any k and width n
Recurrence solution of monomer-polymer models on two-dimensional rectangular lattices
-
Hamiltonicity in degree-3 grid graphs is ASP-complete
ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles
-
NP-hardness for projection games nearly matches 1/q soundness
Near Optimal Alphabet-Soundness Tradeoff PCPs
-
Universal Turing machines can have zero entropy
Topological entropy of Turing complete dynamics
-
-
Learning ω(log log N) halfspaces takes super-polynomial time
Improved Hardness Results for Learning Intersections of Halfspaces
-
Hausdorff classes prove P^NExp equals NP^NExp
Hausdorff Reductions and the Exponential Hierarchies
-
No OWSGs exist with O(log λ) qubit outputs
A Note on Output Length of One-Way State Generators and EFIs
-
Upgraded proofs equate NP, coNP and PSPACE
Proofs of NP = coNP = PSPACE: Current upgrade
-
NL equals C_=L and sits inside PL
Some derivations among Logarithmic Space Bounded Counting Classes
-
Parity is only symmetric function with instance complexity 1
Instance complexity of Boolean functions
-
Graph edit distance NP-hard even with equal edges
Three Hardness Results for Graph Similarity Problems
-
Probabilistic machines decide language outside deterministic P
Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
-
Tarski fixed point enumeration requires lattice width queries
On the enumeration of Tarski fixed points
-
Modal product logic reduces to propositional product logic
On the local consequence of modal Product logic: standard completeness and decidability
-
Algorithm classifies every VPL into AC^0
The $\mathsf{AC}^0$-Complexity Of Visibly Pushdown Languages
-
FO properties on pathwidth admit elementary algorithms
First Order Logic on Pathwidth Revisited Again
-
Flip-flop net synthesis via bounded changes is NP-complete
On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets
-
NP-hardness holds for one-hidden-layer nets with weights in {-1,0,1}
Reachability In Simple Neural Networks
-
Subset Sum needs 2^Omega(r) size refutations in modular resolution
Lower Bounds for Subset Sum in Resolution with Modular Counting
-
Block cipher reduces key cracking to exponential search
A proof of P != NP (New symmetric encryption algorithm against any linear attacks and differential attacks)
-
Circuit descriptions revisit foundational quantum algorithms
Basic Quantum Algorithms
-
Grover search yields 2^{n/2} bound for n-qubit unitaries
Query and Depth Upper Bounds for Quantum Unitaries via Grover Search
-
No (nW)^{o(pw)} algorithm for minimum stable cut under ETH
Minimum Stable Cut and Treewidth
-
One equality relation makes QCSP PSPACE-complete
The complete classification for quantified equality constraints
-
2nfa(k) languages admit constant-coin verifiers with arbitrary low error
Constant-Space, Constant-Randomness Verifiers with Arbitrarily Small Error