- Eli Ben-Sasson, Michael Viderman:
Low Rate Is Insufficient for Local Testability. Electron. Colloquium Comput. Complex. TR10 (2010) - Eli Ben-Sasson, Michael Viderman:
Towards lower bounds on locally testable codes via density arguments. Electron. Colloquium Comput. Complex. TR10 (2010) - Eli Ben-Sasson, Noga Zewi:
From Affine to Two-Source Extractors via Approximate Duality. Electron. Colloquium Comput. Complex. TR10 (2010) - Siavosh Benabbas, Konstantinos Georgiou, Avner Magen:
The Sherali-Adams System Applied to Vertex Cover: Why Borsuk Graphs Fool Strong LPs and some Tight Integrality Gaps for SDPs. Electron. Colloquium Comput. Complex. TR10 (2010) - Olaf Beyersdorff, Nicola Galesi, Massimo Lauria:
Hardness of Parameterized Resolution. Electron. Colloquium Comput. Complex. TR10 (2010) - Olaf Beyersdorff, Nicola Galesi, Massimo Lauria:
A Lower Bound for the Pigeonhole Principle in Tree-like Resolution by Asymmetric Prover-Delayer Games. Electron. Colloquium Comput. Complex. TR10 (2010) - Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov:
Parameterized Bounded-Depth Frege is Not Optimal. Electron. Colloquium Comput. Complex. TR10 (2010) - Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie:
Testing linear-invariant non-linear properties: A short report. Electron. Colloquium Comput. Complex. TR10 (2010) - Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant:
Testing monotonicity of distributions over general partial orders. Electron. Colloquium Comput. Complex. TR10 (2010) - Arnab Bhattacharyya, Elena Grigorescu, Jakob Nordström, Ning Xie:
Separations of Matroid Freeness Properties. Electron. Colloquium Comput. Complex. TR10 (2010) - Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira:
A Unified Framework for Testing Linear-Invariant Properties. Electron. Colloquium Comput. Complex. TR10 (2010) - Mark Braverman, Anup Rao:
Efficient Communication Using Partial Information. Electron. Colloquium Comput. Complex. TR10 (2010) - Mark Braverman, Anup Rao:
Towards Coding for Maximum Errors in Interactive Communication. Electron. Colloquium Comput. Complex. TR10 (2010) - Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff:
Pseudorandom Generators for Regular Branching Programs. Electron. Colloquium Comput. Complex. TR10 (2010) - Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, Shinnosuke Seki:
The Power of Nondeterminism in Self-Assembly. Electron. Colloquium Comput. Complex. TR10 (2010) - Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolai K. Vereshchagin:
Sparse Selfreducible Sets and Nonuniform Lower Bounds. Electron. Colloquium Comput. Complex. TR10 (2010) - Lorenzo Carlucci, Nicola Galesi, Massimo Lauria:
Paris-Harrington tautologies. Electron. Colloquium Comput. Complex. TR10 (2010) - Amit Chakrabarti:
A Note on Randomized Streaming Space Bounds for the Longest Increasing Subsequence Problem. Electron. Colloquium Comput. Complex. TR10 (2010) - Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor:
Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition. Electron. Colloquium Comput. Complex. TR10 (2010) - Amit Chakrabarti, Oded Regev:
An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance. Electron. Colloquium Comput. Complex. TR10 (2010) - Sourav Chakraborty, Eldar Fischer, Arie Matsliah:
Query Complexity Lower Bounds for Reconstruction of Codes. Electron. Colloquium Comput. Complex. TR10 (2010) - Sourav Chakraborty, David García-Soriano, Arie Matsliah:
Nearly Tight Bounds for Testing Function Isomorphism. Electron. Colloquium Comput. Complex. TR10 (2010) - Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner:
Graph Isomorphism is not AC0 reducible to Group Isomorphism. Electron. Colloquium Comput. Complex. TR10 (2010) - Yeow Meng Chee, Tao Feng, San Ling, Huaxiong Wang, Liang Feng Zhang:
Query-Efficient Locally Decodable Codes. Electron. Colloquium Comput. Complex. TR10 (2010) - Ho-Lin Chen, David Doty, Shinnosuke Seki, David Soloveichik:
Parallelism, Program Size, Time, and Temperature in Self-Assembly. Electron. Colloquium Comput. Complex. TR10 (2010) - Yijia Chen, Jörg Flum:
On optimal proof systems and logics for PTIME. Electron. Colloquium Comput. Complex. TR10 (2010) - Zhixiang Chen, Bin Fu:
The Complexity of Testing Monomials in Multivariate Polynomials. Electron. Colloquium Comput. Complex. TR10 (2010) - Zhixiang Chen, Bin Fu:
Approximating Multilinear Monomial Coefficients and Maximum Multilinear Monomials in Multivariate Polynomials. Electron. Colloquium Comput. Complex. TR10 (2010) - Zhixiang Chen, Bin Fu, Yang Liu, Robert T. Schweller:
Algorithms for Testing Monomials in Multivariate Polynomials. Electron. Colloquium Comput. Complex. TR10 (2010) - Victor Chen, Madhu Sudan, Ning Xie:
Property Testing via Set-Theoretic Operations. Electron. Colloquium Comput. Complex. TR10 (2010)