default search action
ACM Transactions on Computation Theory, Volume 11
Volume 11, Number 1, January 2019
- Moses Ganardi, Markus Lohrey:
A Universal Tree Balancing Theorem. 1:1-1:25 - Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas:
Reconstruction of Full Rank Algebraic Branching Programs. 2:1-2:56 - Benoît Larose, Barnaby Martin
, Daniël Paulusma
Surjective H-Colouring over Reflexive Digraphs. 3:1-3:21 - Peter Fulla, Hannes Uppman
The Complexity of Boolean Surjective General-Valued CSPs. 4:1-4:31 - Kazuo Iwama, Atsuki Nagao
Read-Once Branching Programs for Tree Evaluation Problems. 5:1-5:12
Volume 11, Number 2, April 2019
- Eric Blais, Clément L. Canonne
Distribution Testing Lower Bounds via Reductions from Communication Complexity. 6:1-6:37 - Jin-Yi Cai, Michael Kowalczyk, Tyson Williams:
Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy. 7:1-7:26 - Krishnamoorthy Dinesh
Characterization and Lower Bounds for Branching Program Size using Projective Dimension. 8:1-8:22 - Iordanis Kerenidis, Adi Rosén, Florent Urrutia:
Multi-Party Protocols, Information Complexity and Privacy. 9:1-9:29 - C. Ramya, B. V. Raghavendra Rao
Lower bounds for Sum and Sum of Products of Read-once Formulas. 10:1-10:27 - Sudeshna Kolay, Fahad Panolan
Communication Complexity and Graph Families. 11:1-11:28
Volume 11, Number 3, June 2019
- Grant Schoenebeck
Beyond Worst-case (In)approximability of Nonsubmodular Influence Maximization. 12:1-12:56 - Marthe Bonamy, Lukasz Kowalik
Tight Lower Bounds for the Complexity of Multicoloring. 13:1-13:19 - Timothy Black:
Monotone Properties of k-Uniform Hypergraphs Are Weakly Evasive. 14:1-14:14 - Nir Aviv, Amnon Ta-Shma
On the Entropy Loss and Gap of Condensers. 15:1-15:14 - Baris Aydinlioglu, Eric Bach:
Corrigendum to Affine Relativization: Unifying the Algebrization and Relativization Barriers. 16:1 - Oded Goldreich, Tom Gur
Strong Locally Testable Codes with Relaxed Local Decoders. 17:1-17:38 - Akanksha Agrawal
Split Contraction: The Untold Story. 18:1-18:22
Volume 11, Number 4, September 2019
- Emanuele Viola:
Constant-Error Pseudorandomness Proofs from Hardness Require Majority. 19:1-19:11 - Ishay Haviv:
On Minrank and Forbidden Subgraphs. 20:1-20:13 - Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola:
Bounded Independence versus Symmetric Tests. 21:1-21:27 - Mateus de Oliveira Oliveira
Representations of Monotone Boolean Functions by Linear Programs. 22:1-22:31 - Leslie Ann Goldberg, Mark Jerrum:
Approximating Pairwise Correlations in the Ising Model. 23:1-23:20 - Eric Blais, Clément L. Canonne
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism. 24:1-24:33 - Dominik Scheder
PPSZ for k ≥ 5: More Is Better. 25:1-25:22 - Olaf Beyersdorff
New Resolution-Based QBF Calculi and Their Proof Complexity. 26:1-26:42 - Eric Allender
New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems. 27:1-27:27 - Bart M. P. Jansen
Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials. 28:1-28:26
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.
last updated on 2024-11-22 19:32 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: