


default search action
ACM Transactions on Computation Theory, Volume 12
Volume 12, Number 1, February 2020
- Ryan O'Donnell:
Editorial from the New Editor-in-Chief. 1e:1 - Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra:
FPT Algorithms for Embedding into Low-Complexity Graphic Metrics. 1:1-1:41 - Neeraj Kayal, Vineet Nair, Chandan Saha:
Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth-three Circuits. 2:1-2:27 - Edith Hemaspaandra, Lane A. Hemaspaandra
, Curtis Menton:
Search versus Decision for Election Manipulation Problems. 3:1-3:42 - Montserrat Hermo
, Ana Ozaki:
Exact Learning: On the Boundary between Horn and CNF. 4:1-4:25 - Mrinal Kumar:
On the Power of Border of Depth-3 Arithmetic Circuits. 5:1-5:8 - Henning Fernau
, Florin Manea, Robert Mercas, Markus L. Schmid:
Pattern Matching with Variables: Efficient Algorithms and Complexity Results. 6:1-6:37 - Elazar Goldenberg, Karthik C. S.
:
Toward a General Direct Product Testing Theorem. 7:1-7:18
Volume 12, Number 2, May 2020
- Rohit Gurjar, Ben Lee Volk:
Pseudorandom Bits for Oblivious Branching Programs. 8:1-8:12 - Nicola Galesi, Navid Talebanfard
, Jacobo Torán:
Cops-Robber Games and the Resolution of Tseitin Formulas. 9:1-9:22 - Olaf Beyersdorff
, Luke Hinde, Ján Pich
:
Reasons for Hardness in QBF Proof Systems. 10:1-10:27 - Andrei A. Bulatov, Stanislav Zivný
:
Approximate Counting CSP Seen from the Other Side. 11:1-11:19 - David J. Rosenbaum:
Beating the Generator-Enumeration Bound for Solvable-Group Isomorphism. 12:1-12:18 - Victor Lagerkvist, Magnus Wahlström
:
Sparsification of SAT and CSP Problems via Tractable Extensions. 13:1-13:29 - Thomas Watson:
Quadratic Simulations of Merlin-Arthur Games. 14:1-14:11
Volume 12, Number 3, July 2020
- Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný:
The Complexity of Approximately Counting Retractions. 15:1-15:43 - Alessandro Chiesa, Peter Manohar, Igor Shinkar:
Testing Linearity against Non-signaling Strategies. 16:1-16:51 - Stasys Jukna
:
Coin Flipping in Dynamic Programming Is Almost Useless. 17:1-17:26 - Md Lutfar Rahman, Thomas Watson:
Complexity of Unordered CNF Games. 18:1-18:18 - Dusan Knop, Michal Pilipczuk, Marcin Wrochna
:
Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints. 19:1-19:19 - Mika Göös, Thomas Watson:
A Lower Bound for Sampling Disjoint Sets. 20:1-20:13 - Mahdi Cheraghchi
, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis
:
Circuit Lower Bounds for MCSP from Local Pseudorandom Generators. 21:1-21:27
Volume 12, Number 4, November 2020
- Robert Ganian, Ronald de Haan, Iyad Kanj, Stefan Szeider
:
On Existential MSO and Its Relation to ETH. 22:1-22:32 - Srikanth Srinivasan
:
Strongly Exponential Separation between Monotone VP and Monotone VNP. 23:1-23:12 - Benny Applebaum, Barak Arkis:
On the Power of Amortization in Secret Sharing: d-Uniform Secret Sharing and CDS with Constant Information Rate. 24:1-24:21 - Srikanth Srinivasan
, Utkarsh Tripathi, S. Venkitesh
:
Decoding Variants of Reed-Muller Codes over Finite Grids. 25:1-25:11 - Vladimir V. Podolskii
, Alexander A. Sherstov:
Inner Product and Set Disjointness: Beyond Logarithmically Many Parties. 26:1-26:28 - Thomas Watson:
A ZPPNP[1] Lifting Theorem. 27:1-27:20 - Oded Goldreich, Dana Ron:
The Subgraph Testing Model. 28:1-28:32

manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.