- Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson:
Approximating Linear Threshold Predicates. Electron. Colloquium Comput. Complex. TR10 (2010) - Gil Cohen, Amir Shpilka:
On the degree of symmetric functions on the Boolean cube. Electron. Colloquium Comput. Complex. TR10 (2010) - Graham Cormode, Justin Thaler, Ke Yi:
Verifying Computations with Streaming Interactive Proofs. Electron. Colloquium Comput. Complex. TR10 (2010) - Samir Datta, Raghav Kulkarni, Raghunath Tewari:
Perfect Matching in Bipartite Planar Graphs is in UL. Electron. Colloquium Comput. Complex. TR10 (2010) - Samir Datta, Raghav Kulkarni, Raghunath Tewari, N. V. Vinodchandran:
Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs. Electron. Colloquium Comput. Complex. TR10 (2010) - Samir Datta, Meena Mahajan, B. V. Raghavendra Rao, Michael Thomas, Heribert Vollmer:
Counting Classes and the Fine Structure between NC1 and L. Electron. Colloquium Comput. Complex. TR10 (2010) - Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner:
Graph Isomorphism for K3,3-free and K5-free graphs is in Log-space. Electron. Colloquium Comput. Complex. TR10 (2010) - Holger Dell, Thore Husfeldt, Martin Wahlen:
Exponential Time Complexity of the Permanent and the Tutte Polynomial. Electron. Colloquium Comput. Complex. TR10 (2010) - Irit Dinur, Or Meir:
Derandomized Parallel Repetition via Structured PCPs. Electron. Colloquium Comput. Complex. TR10 (2010) - Andrew Drucker:
A PCP Characterization of AM. Electron. Colloquium Comput. Complex. TR10 (2010) - Andrew Drucker:
Improved Direct Product Theorems for Randomized Query Complexity. Electron. Colloquium Comput. Complex. TR10 (2010) - Zeev Dvir, Dan Gutfreund, Guy N. Rothblum, Salil P. Vadhan:
On Approximating the Entropy of Polynomial Mappings. Electron. Colloquium Comput. Complex. TR10 (2010) - Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin:
Matching Vector Codes. Electron. Colloquium Comput. Complex. TR10 (2010) - Kord Eickmeyer, Martin Grohe:
Randomisation and Derandomisation in Descriptive Complexity Theory. Electron. Colloquium Comput. Complex. TR10 (2010) - Noa Eidelstein, Alex Samorodnitsky:
Lower bounds for designs in symmetric spaces. Electron. Colloquium Comput. Complex. TR10 (2010) - Michael Elberfeld, Andreas Jakoby, Till Tantau:
Logspace Versions of the Theorems of Bodlaender and Courcelle. Electron. Colloquium Comput. Complex. TR10 (2010) - Alexander Fanghänel, Sascha Geulen, Martin Hoefer, Berthold Vöcking:
Online Capacity Maximization in Wireless Networks. Electron. Colloquium Comput. Complex. TR10 (2010) - Bill Fefferman, Ronen Shaltiel, Christopher Umans, Emanuele Viola:
On beating the hybrid argument. Electron. Colloquium Comput. Complex. TR10 (2010) - Vitaly Feldman:
A Complete Characterization of Statistical Query Learning with Applications to Evolvability. Electron. Colloquium Comput. Complex. TR10 (2010) - Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu:
Agnostic Learning of Monomials by Halfspaces is Hard. Electron. Colloquium Comput. Complex. TR10 (2010) - Vitaly Feldman, Homin K. Lee, Rocco A. Servedio:
Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas. Electron. Colloquium Comput. Complex. TR10 (2010) - Bin Fu:
NE is not NP Turing Reducible to Nonexpoentially Dense NP Sets. Electron. Colloquium Comput. Complex. TR10 (2010) - Bin Fu:
Multivariate Polynomial Integration and Derivative Are Polynomial Time Inapproximable unless P=NP. Electron. Colloquium Comput. Complex. TR10 (2010) - David García-Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briët:
Monotonicity Testing and Shortest-Path Routing on the Cube. Electron. Colloquium Comput. Complex. TR10 (2010) - Dmitry Gavinsky, Tsuyoshi Ito:
Quantum Fingerprints that Keep Secrets. Electron. Colloquium Comput. Complex. TR10 (2010) - Dmitry Gavinsky, Alexander A. Sherstov:
A Separation of NP and coNP in Multiparty Communication Complexity. Electron. Colloquium Comput. Complex. TR10 (2010) - Christian Glaßer, Christian Reitwießner, Heinz Schmitz, Maximilian Witek:
Hardness and Approximability in Multi-Objective Optimization. Electron. Colloquium Comput. Complex. TR10 (2010) - Oded Goldreich:
On Testing Computability by Small Width OBDDs. Electron. Colloquium Comput. Complex. TR10 (2010) - Oded Goldreich:
Introduction to Testing Graph Properties. Electron. Colloquium Comput. Complex. TR10 (2010) - Oded Goldreich:
In a World of P=BPP. Electron. Colloquium Comput. Complex. TR10 (2010)