EUVIMED · CrossrefZeitschrift
ACM Transactions on Computation Theory
ISSN 1942-3454 · Association for Computing Machinery (ACM)
Neueste Artikel
On the Hardness of Compressing Weights
Broadcasting Under Structural Restrictions
Optimal Polynomial-Time Compression for Boolean Max CSP
On the Power of Amortization in Secret Sharing
Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials
(Leveled) Fully Homomorphic Encryption without Bootstrapping
Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
Editor’s Foreword
Algebrization
A Simple Proof of Bazzi’s Theorem
Directed Planar Reachability Is in Unambiguous Log-Space
Improved Separations between Nondeterministic and Randomized Multiparty Communication
Hardness of Solving Sparse Overdetermined Linear Systems
Sound 3-Query PCPPs Are Long
Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case
Formula Caching in DPLL
Planarity, Determinants, Permanents, and (Unique) Matchings
Cell-Probe Proofs
Tradeoffs and Average-Case Equilibria in Selfish Routing
Lower Bounds for Coin-Weighing Problems
Solvable Group Isomorphism Is (Almost) in NP ∩ coNP
A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems
Kolmogorov Complexity in Randomness Extraction
On the Power of Isolation in Planar Graphs
Approximate Query Complexity
Pebbles and Branching Programs for Tree Evaluation
Three-Query Locally Decodable Codes with Higher Correctness Require Exponential Length
The Value of Multiple Read/Write Streams for Approximating Frequency Moments
Exact Quantum Algorithms for the Leader Election Problem
Approximating Linear Threshold Predicates
EUVIMED