Electronic Colloquium on Computational Complexity, Volume 17, 2010
Volume 17, 2010
Iftach Haitner, Mohammad Mahmoody, David Xiao: A New Sampling Protocol and Applications to Basing Cryptographic Primitives on the Hardness of NP. 1- Ran Raz: Tensor-Rank and Lower Bounds for Arithmetic Formulas. 2
- Venkatesan Guruswami, Johan Håstad, Swastik Kopparty: On the List-Decodability of Random Linear Codes. 3
- Yi Wu, Ryan O'Donnell, David Zuckerman, Parikshit Gopalan: Fooling functions of halfspaces under product distributions. 6
- Shachar Lovett: Equivalence of polynomial conjectures in additive combinatorics. 10
- Nitin Saxena, C. Seshadhri: From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits. 13
- Daniele Micciancio, Panagiotis Voulgaris: A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations. 14
- Maurice J. Jansen, Youming Qiao, Jayalal M. N. Sarma: Deterministic Black-Box Identity Testing pi-Ordered Algebraic Branching Programs. 15
- Alexander Fanghänel, Sascha Geulen, Martin Hoefer, Berthold Vöcking: Online Capacity Maximization in Wireless Networks. 16
- Vitaly Feldman: A Complete Characterization of Statistical Query Learning with Applications to Evolvability. 18
- Andrew Drucker: A PCP Characterization of AM. 19
- Vipul Goyal, Yuval Ishai, Mohammad Mahmoody, Amit Sahai: Interactive Locking, Zero-Knowledge PCPs, and Unconditional Cryptography. 20
- Pavel Hrubes, Avi Wigderson, Amir Yehudayoff: Non-commutative circuits and the sum-of-squares problem. 21
- Vitaly Feldman, Homin K. Lee, Rocco A. Servedio: Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas. 22
- Henning Wunderlich, Stefan Arnold: On a singular value method in quantum communication complexity. 24
- Alexander A. Sherstov: Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. 25
- Hao Huang, Benny Sudakov: A counterexample to the Alon-Saks-Seymour conjecture and related problems. 26
- Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant: Testing monotonicity of distributions over general partial orders. 27
- Miklós Ajtai: Oblivious RAMs without Cryptographic Assumptions. 28
- Alexandra Kolla: Spectral Algorithms for Unique Games. 29
- Airat Khasianov: Stronger Lower Bounds on Quantum OBDD for the Hidden Subgroup Problem. 30
- Christian Glaßer, Christian Reitwießner, Heinz Schmitz, Maximilian Witek: Hardness and Approximability in Multi-Objective Optimization. 31
- Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka: Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over finite fields. 33
- Luca Trevisan: The Program-Enumeration Bottleneck in Average-Case Complexity Theory. 34
- Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff: Pseudorandom Generators for Regular Branching Programs. 35
- Amir Shpilka, Ilya Volkovich: On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors. 36
- Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson: Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors. 37
- Dieter van Melkebeek, Holger Dell: Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses. 38
- Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer: Improved Algorithms for Unique Games via Divide and Conquer. 41
- Thomas Watson: Relativized Worlds Without Worst-Case to Average-Case Reductions for NP. 42
- Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky: Interval Graphs: Canonical Representation in Logspace. 43
- Jakob Nordström: On the Relative Strength of Pebbling and Resolution. 45
- Ján Pich: Nisan-Wigderson generators in proof systems with forms of interpolation. 46
- Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma: Local list decoding with a constant number of queries. 47
- David García-Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briët: Monotonicity Testing and Shortest-Path Routing on the Cube. 48
- Alexey Pospelov: Bounds for Bilinear Complexity of Noncommutative Group Algebras. 49
- Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner: Graph Isomorphism for K{3, 3}-free and K5-free graphs is in Log-space. 50
- Madhu Sudan: Invariance in Property Testing. 51
- Melanie Winkler, Berthold Vöcking, Sascha Geulen: Regret Minimization for Online Buffering Problems Using the Weighted Majority Algorithm. 52
- Jan Krajícek: On the proof complexity of the Nisan-Wigderson generator based on a hard NP cap coNP function. 54
- Eric Allender: Avoiding Simplicity is Complex. 55
- Kord Eickmeyer, Martin Grohe: Randomisation and Derandomisation in Descriptive Complexity Theory. 56
- Dmitry Gavinsky, Alexander A. Sherstov: A Separation of NP and coNP in Multiparty Communication Complexity. 60
- Oded Goldreich: On Testing Computability by Small Width OBDDs. 61
- Michael Elberfeld, Andreas Jakoby, Till Tantau: Logspace Versions of the Theorems of Bodlaender and Courcelle. 62
- Venkatesan Guruswami, Yuan Zhou: Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set}. 63
- Xin Li: A New Approach to Affine Extractors and Dispersers. 64
- Tali Kaufman, Shachar Lovett: Testing of exponentially large codes, by a new extension to Weil bound for character sums. 65
- Sourav Chakraborty, Eldar Fischer, Arie Matsliah: Query Complexity Lower Bounds for Reconstruction of Codes. 67
- Shir Ben-Israel, Eli Ben-Sasson, David R. Karger: Breaking local symmetries can dramatically reduce the length of propositional refutations. 68
- Eric Allender, Vikraman Arvind, Fengming Wang: Uniform Derandomization from Pathetic Lower Bounds. 69
- Eric Allender, Klaus-Jörn Lange: Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata. 70
- Neeraj Kayal: Algorithms for Arithmetic Circuits. 73
- Ben Reichardt: Least span program witness size equals the general adversary lower bound on quantum query complexity. 75
- Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor: Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition. 76
- Venkatesan Guruswami, Adam Smith: Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate. 77
- Holger Dell, Thore Husfeldt, Martin Wahlen: Exponential Time Complexity of the Permanent and the Tutte Polynomial. 78
- Samir Datta, Raghav Kulkarni, Raghunath Tewari, N. V. Vinodchandran: Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs. 79
- Andrew Drucker: Improved Direct Product Theorems for Randomized Query Complexity. 80
- Olaf Beyersdorff, Nicola Galesi, Massimo Lauria: A Lower Bound for the Pigeonhole Principle in Tree-like Resolution by Asymmetric Prover-Delayer Games. 81
- Oded Goldreich: Introduction to Testing Graph Properties. 82
- Maurice J. Jansen, Youming Qiao, Jayalal M. N. Sarma: Deterministic Identity Testing of Read-Once Algebraic Branching Programs. 84
- Eli Ben-Sasson, Jan Johannsen: Lower bounds for width-restricted clause learning on small width formulas. 85
- Henning Wunderlich: On a Theorem of Razborov. 86
- Jirí Síma, Stanislav Zák: A Polynomial Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3. 88
- Iftach Haitner, Omer Reingold, Salil P. Vadhan: Efficiency Improvements in Constructing Pseudorandom Generators from One-way Functions. 89
- Nikolay K. Vereshchagin: {Algorithmic Minimal Sufficient Statistics: a New Definition. 90
- Nikolay K. Vereshchagin: An Encoding Invariant Version of Polynomial Time Computable Distributions. 91
- Charanjit S. Jutla, Arnab Roy: A Completeness Theorem for Pseudo-Linear Functions with Applications to UC Security. 92
- Sourav Chakraborty, David García-Soriano, Arie Matsliah: Nearly Tight Bounds for Testing Function Isomorphism. 93
- Masaki Yamamoto: A combinatorial analysis for the critical clause tree. 95
- Dana Moshkovitz: An Alternative Proof of The Schwartz-Zippel Lemma. 96
- Iddo Tzameret: Algebraic Proofs over Noncommutative Formulas. 97
- T. C. Vijayaraghavan: A Note on Closure Properties of ModL. 99
- Amit Chakrabarti: A Note on Randomized Streaming Space Bounds for the Longest Increasing Subsequence Problem. 100
- Samir Datta, Meena Mahajan, B. V. Raghavendra Rao, Michael Thomas, Heribert Vollmer: Counting Classes and the Fine Structure between NC1 and L. 101
- Yuichi Yoshida: Optimal Constant-Time Approximation Algorithms and (Unconditional) Inapproximability Results for Every Bounded-Degree CSP. 106
- Scott Aaronson: A Counterexample to the Generalized Linial-Nisan Conjecture. 109
- Ben Reichardt: Span programs and quantum query algorithms. 110
- Venkatesan Guruswami, Ali Kemal Sinop: The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number. 111
- Subhash Khot, Dana Moshkovitz: NP-Hardness of Approximately Solving Linear Equations Over Reals. 112
- Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie: Testing linear-invariant non-linear properties: A short report. 116
- Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner: Graph Isomorphism is not AC^0 reducible to Group Isomorphism. 117
- Maurice J. Jansen: Extracting Roots of Arithmetic Circuits by Adapting Numerical Methods. 118
- Michal Moshkovitz: Distance Estimators with Sublogarithmic Number of Queries. 119
- Ashwin Nayak: Inverting a permutation is as hard as unordered search. 121
- Zhixiang Chen, Bin Fu, Yang Liu, Robert T. Schweller: Algorithms for Testing Monomials in Multivariate Polynomials. 122
- Eli Ben-Sasson: Limitation on the rate of families of locally testable codes. 123
- Zhixiang Chen, Bin Fu: Approximating Multilinear Monomial Coefficients and Maximum Multilinear Monomials in Multivariate Polynomials. 124
- Eli Ben-Sasson, Jakob Nordström: Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions. 125
- Thomas Watson: Query Complexity in Errorless Hardness Amplification. 126
- Brett Hemenway, Rafail Ostrovsky: Building Injective Trapdoor Functions From Oblivious Transfer. 127
- Scott Aaronson: The Equivalence of Sampling and Searching. 128
- Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel: Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds. 129
- Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, Shinnosuke Seki: The Power of Nondeterminism in Self-Assembly. 131
- Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson: Approximating Linear Threshold Predicates. 132
- Parikshit Gopalan, Adam Klivans, Raghu Meka: Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs. 133
- Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma: A Note on Amplifying the Error-Tolerance of Locally Decodable Codes. 134
- Oded Goldreich: In a World of P=BPP. 135
- Arnab Bhattacharyya, Elena Grigorescu, Jakob Nordström, Ning Xie: Separations of Matroid Freeness Properties. 136
- Or Meir: IP = PSPACE using Error Correcting Codes. 137
- Eric Allender, Luke Friedman, William I. Gasarch: Exposition of the Muchnik-Positselsky Construction of a Prefix Free Entropy Function that is not Complete under Truth-Table Reductions. 138
- Eric Allender, Luke Friedman, William I. Gasarch: Limits on the Computational Power of Random Strings. 139
- Amit Chakrabarti, Oded Regev: An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance. 140
- Ran Raz: A Strong Parallel Repetition Theorem for Projection Games on Expanders. 141
- Bo'az Klartag, Oded Regev: Quantum One-Way Communication is Exponentially Stronger Than Classical Communication. 143
- Ron Rothblum: A Taxonomy of Enhanced Trapdoor Permutations. 145
- Ron Rothblum: Homomorphic Encryption: from Private-Key to Public-Key. 146
- Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin: High-rate codes with sublinear-time decoding. 148
- Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff: Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes. 149
- Bjørn Kjos-Hanssen: A strong law of computationally weak subsets. 150
- Alexey Pospelov: Faster Polynomial Multiplication via Discrete Fourier Transforms. 152
- Derrick Stolee, N. V. Vinodchandran: Space-Efficient Algorithms for Reachability in Surface-Embedded Graphs. 154
- Shiva Kintali: Realizable Paths and the NL vs L Problem. 158
- Zeev Dvir, Dan Gutfreund, Guy N. Rothblum, Salil P. Vadhan: On Approximating the Entropy of Polynomial Mappings. 160
- Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira: A Unified Framework for Testing Linear-Invariant Properties. 161
- Zohar Shay Karnin: Deterministic Construction of a high dimensional lp section in l1n for any p<2. 162
- Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolai K. Vereshchagin: Sparse Selfreducible Sets and Nonuniform Lower Bounds. 163
- Falk Unger: Better gates can make fault-tolerant computation impossible. 164
- Nitin Saxena, C. Seshadhri: Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter. 167
- Thomas Watson: Pseudorandom Generators for Combinatorial Checkerboards. 168
- 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. 169
- Michael Viderman: A Note on high-rate Locally Testable Codes with sublinear query complexity. 171
- Yeow Meng Chee, Tao Feng, San Ling, Huaxiong Wang, Liang Feng Zhang: Query-Efficient Locally Decodable Codes. 173
- Scott Aaronson, Baris Aydinlioglu, Harry Buhrman, John M. Hitchcock, Dieter van Melkebeek: A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games. 174
- Emanuele Viola: Randomness buys depth for approximate counting. 175
- Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman: Pseudorandom Generators for Combinatorial Shapes. 176
- Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu: Bypassing UGC from some optimal geometric inapproximability results. 177
- Gregory Valiant, Paul Valiant: Estimating the unseen: A sublinear-sample canonical estimator of distributions. 180
- Hamed Hatami, Shachar Lovett: Higher-order Fourier analysis of Fpn and the complexity of systems of linear forms. 181
- Shachar Lovett: An elementary proof of anti-concentration of polynomials in Gaussian variables. 182
- Gregory Valiant, Paul Valiant: Estimating the unseen: A sublinear-sample canonical estimator of distributions. 184
- Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu: Agnostic Learning of Monomials by Halfspaces is Hard. 185
- Bill Fefferman, Ronen Shaltiel, Christopher Umans, Emanuele Viola: On beating the hybrid argument. 186
- Gus Gutoski: Interactive proofs with competing teams of no-signaling provers. 187
- Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich: Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae. 188
- Xin Li: Improved Constructions of Three Source Extractors. 190
- Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland: Symmetry-assisted adversaries for quantum state generation. 191
- Frédéric Magniez, Ashwin Nayak, Miklos Santha, David Xiao: Improved bounds for the randomized decision tree complexity of recursive majority. 192
- Edward A. Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal: On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography. 193
- Thanh Minh Hoang: Isolation of Matchings via Chinese Remaindering. 194
- Ho-Lin Chen, David Doty, Shinnosuke Seki, David Soloveichik: Parallelism, Program Size, Time, and Temperature in Self-Assembly. 195
- Bin Fu: NE is not NP Turing Reducible to Nonexpoentially Dense NP Sets. 196
- Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov: Parameterized Bounded-Depth Frege is Not Optimal. 198
- Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan: Symmetric LDPC codes are not necessarily locally testable. 199
- Eli Ben-Sasson, Michael Viderman: Towards lower bounds on locally testable codes via density arguments. 200
- Samir Datta, Raghav Kulkarni, Raghunath Tewari: Perfect Matching in Bipartite Planar Graphs is in UL. 201
- Bin Fu: Multivariate Polynomial Integration and Derivative Are Polynomial Time Inapproximable unless P=NP. 202
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-19T201401 by the dblp team