Google
Google Scholar
Semantic Scholar
MS Academic
CiteSeerX
ORCIDElectronic Colloquium on Computational Complexity, Volume 19
Volume 19, 2012
- Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett:
Testing Low Complexity Affine-Invariant Properties. 1 - Akinori Kawachi, Benjamin Rossman, Osamu Watanabe:
Query Complexity and Error Tolerance of Witness Finding Algorithms. 2 - Pratik Worah:
Rank Bounds for a Hierarchy of Lovász and Schrijver. 3 - Marcos Villagra, Masaki Nakanishi, Shigeru Yamashita, Yasuhiko Nakashima:
Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication. 4 - Periklis A. Papakonstantinou, Guang Yang:
A remark on one-wayness versus pseudorandomness. 5 - Gregory Valiant:
Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas with Noise. 6 - Ruiwen Chen, Valentine Kabanets:
Lower Bounds against Weakly Uniform Circuits. 7 - Marek Karpinski, Richard Schmied:
On Approximation Lower Bounds for TSP with Bounded Metrics. 8 - Prabhu Manyem, Julien Ugon:
Computational Complexity, NP Completeness and Optimization Duality: A Survey. 9 - Shafi Goldwasser, Guy N. Rothblum:
How to Compute in the Presence of Leakage. 10 - Nader H. Bshouty:
Testers and their Applications. 11 - Oded Goldreich:
On the Effect of the Proximity Parameter on Property Testers. 12 - Tomás Feder, Carlos S. Subi:
Packing Edge-Disjoint Triangles in Given Graphs. 13 - Johannes Mittmann, Nitin Saxena, Peter Scheiblechner:
Algebraic Independence in Positive Characteristic - A p-Adic Calculus. 14 - Albert Atserias, Anuj Dawar:
Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers. 15 - Anindya De, Elchanan Mossel:
Explicit Optimal hardness via Gaussian stability results. 16 - Venkatesan Guruswami, Srivatsan Narayanan:
Combinatorial limitations of a strong form of list decoding. 17 - Jörg Flum, Moritz Müller:
Some definitorial suggestions for parameterized proof complexity. 18 - Eric Miles, Emanuele Viola:
On the complexity of constructing pseudorandom functions (especially when they don't exist). 19 - Daniele Micciancio:
Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction. 20 - Oded Goldreich:
Two-Sided Error Proximity Oblivious Testing. 21 - Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler:
Annotations in Data Streams. 22 - Sophie Laplante, Virginie Lerays, Jérémie Roland:
Classical and quantum partition bound and detector inefficiency. 23 - Scott Aaronson, Paul F. Christiano:
Quantum Money from Hidden Subspaces. 24 - Kord Eickmeyer, Kristoffer Arnsfelt Hansen, Elad Verbin:
Approximating the minmax value of 3-player games within a constant is as hard as detecting planted cliques. 25 - Thomas Watson:
Time Hierarchies for Sampling Distributions. 26 - Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, Bangsheng Tang:
Time-space tradeoffs for width-parameterized SAT: Algorithms and lower bounds. 27 - Eric Allender, George Davie, Luke Friedman, Samuel Hopkins, Iddo Tzameret:
Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic. 28 - Shachar Lovett:
An exposition of Sanders quasi-polynomial Freiman-Ruzsa theorem. 29 - Deeparnab Chakrabarty, C. Seshadhri:
Optimal bounds for monotonicity and Lipschitz testing over the hypercube. 30 - Tom Gur, Omer Tamuz:
Testing Booleanity and the Uncertainty Principle. 31 - Sebastian Kuhnert, Johannes Köbler, Osamu Watanabe:
Interval graph representation with given interval and intersection lengths. 32 - Ankit Gupta, Neeraj Kayal, Youming Qiao:
Random Arithmetic Formulas can be Reconstructed Efficiently. 33 - Abhishek Bhowmick, Zeev Dvir, Shachar Lovett:
New Lower Bounds for Matching Vector Codes. 34 - Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler:
Finding Cycles and Trees in Sublinear Time. 35 - Venkatesan Guruswami, Chaoping Xing:
Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding. 36 - Alexander A. Sherstov:
Making Polynomials Robust to Noise. 37 - Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jérémie Roland, David Xiao:
Lower bounds on information complexity via zero-communication protocols and applications. 38 - Stasys Jukna:
Clique Problem, Cutting Plane Proofs, and Communication Complexity. 39 - Sangxia Huang:
Approximation Resistance on Satisfiable Instances for Predicates Strictly Dominating Parity. 40 - Stasys Jukna:
Limitations of Incremental Dynamic Programs. 41 - Chris Beck, Russell Impagliazzo, Shachar Lovett:
Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits. 42 - Zvika Brakerski, Yael Tauman Kalai:
Efficient Interactive Coding Against Adversarial Noise. 43 - Swastik Kopparty:
List-Decoding Multiplicity Codes. 44 - Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer:
On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs. 45 - Madhu Sudan, Noga Zewi:
A new upper bound on the query complexity for testing generalized Reed-Muller codes. 46 - Emanuele Viola:
Extractors for Turing-machine sources. 47 - Alan Guo, Madhu Sudan:
Some closure features of locally testable affine-invariant properties. 48 - Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan:
Sparse affine-invariant linear codes are locally testable. 49 - Avraham Ben-Aroya, Gil Cohen:
Gradual Small-Bias Sample Spaces. 50 - Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan:
A Tail Bound for Read-k Families of Functions. 51 - Mohammad Mahmoody, David Xiao:
Languages with Efficient Zero-Knowledge PCPs are in SZK. 52 - Ankur Moitra:
A Singly-Exponential Time Algorithm for Computing Nonnegative Rank. 53 - Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff:
Reductions to the set of random strings: the resource-bounded case. 54 - Reut Levi, Dana Ron, Ronitt Rubinfeld:
Testing Similar Means. 55 - Rocco A. Servedio, Li-Yang Tan, Justin Thaler:
Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions. 56 - Russell Impagliazzo, Raghu Meka, David Zuckerman:
Pseudorandomness from Shrinkage. 57 - Benny Applebaum, Yuval Ishai, Eyal Kushilevitz:
How to Garble Arithmetic Circuits. 58 - Rahul Santhanam, Ryan Williams:
Uniform Circuits, Lower Bounds, and QBF Algorithms. 59 - Parikshit Gopalan, Raghu Meka, Omer Reingold:
DNF Sparsification and a Faster Deterministic Counting. 60 - Pavel Hrubes, Amir Yehudayoff:
Formulas are exponentially stronger than monotone circuits in non-commutative setting. 61 - Ilan Komargodski, Ran Raz:
Average-Case Lower Bounds for Formula Size. 62 - Raghav Kulkarni, Miklos Santha:
Query complexity of matroids. 63 - Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala, Ying Xiao:
Statistical Algorithms and a Lower Bound for Planted Clique. 64 - Mohammad Mahmoody, Hemanta K. Maji, Manoj Prabhakaran:
Limits of Random Oracles in Secure Computation. 65 - Jinyu Huang:
Parallel Complexity for Matroid Intersection and Matroid Parity Problems. 66 - Xiaohui Bei
, Ning Chen, Shengyu Zhang:
On the Complexity of Trial and Error. 67 - Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena:
Deterministic Polynomial Factoring and Association Schemes. 68 - Lakhdar Saïs, Mohand-Said Hacid, François Hantry:
On the complexity of computing minimal unsatisfiable LTL formulas. 69 - Thomas Watson:
The Complexity of Estimating Min-Entropy. 70 - Kazuhisa Seto, Suguru Tamaki:
A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis. 71 - Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco A. Servedio:
Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces. 72 - Venkatesan Guruswami, Carol Wang:
Linear-algebraic list decoding for variants of Reed-Solomon codes. 73 - Venkatesan Guruswami, Yuan Zhou:
Approximating Bounded Occurrence Ordering CSPs. 74 - Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova:
Limitations of Local Filters of Lipschitz and Monotone Functions. 75 - Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova:
Testing Lipschitz Functions on Hypergrid Domains. 76 - Chiranjit Chakraborty, Rahul Santhanam:
Instance Compression for the Polynomial Hierarchy and Beyond. 77 - Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Yadu Vasudev:
Approximate Graph Isomorphism. 78 - Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer:
Verifying Proofs in Constant Depth. 79 - Baris Aydinlioglu, Dieter van Melkebeek:
Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Games. 80 - Neeraj Kayal:
An exponential lower bound for the sum of powers of bounded degree polynomials. 81 - Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker:
Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes. 82 - Thomas Steinke:
Pseudorandomness for Permutation Branching Programs Without the Group Theory. 83 - Rahul Santhanam:
Ironic Complicity: Satisfiability Algorithms and Circuit Lower Bounds. 84 - Tsuyoshi Ito, Thomas Vidick:
A multi-prover interactive proof for NEXP sound against entangled provers. 85 - Shlomi Dolev, Nova Fandina, Dan Gutfreund:
Succinct Permanent is NEXP-hard with Many Hard Instances. 86 - Peyman Afshani, Manindra Agrawal, Benjamin Doerr, Carola Winzen, Kasper Green Larsen, Kurt Mehlhorn:
The Deterministic and Randomized Query Complexity of a Simple Guessing Game. 87 - Irit Dinur, Gillat Kol:
Covering CSPs. 88 - Meena Boppana:
Lattice Variant of the Sensitivity Conjecture. 89 - Michael Blondin, Andreas Krebs, Pierre McKenzie:
The Complexity of Intersecting Finite Automata Having Few Final States. 90 - Abuzer Yakaryilmaz:
One-counter verifiers for decidable languages. 91 - Pavol Duris:
A Note On the Hierarchy of One-way Data-Independent Multi-Head Finite Automata. 92 - Charanjit S. Jutla, Vijay Kumar, Atri Rudra:
On the Circuit Complexity of Composite Galois Field Transformations. 93 - Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva:
Testing Permanent Oracles - Revisited. 94 - Avraham Ben-Aroya, Igor Shinkar:
A Note on Subspace Evasive Sets. 95 - Albert Atserias, Sergi Oliva:
Bounded-width QBF is PSPACE-complete. 96 - Andrej Bogdanov, Siyao Guo:
Sparse extractor families for all the entropy. 97 - Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi:
An exponential lower bound for homogeneous depth four arithmetic circuits with bounded bottom fanin. 98 - Nikos Leonardos:
An improved lower bound for the randomized decision tree complexity of recursive majority. 99 - Tomas Jirotka:
NP Search Problems. 100 - Oded Goldreich, Shafi Goldwasser, Dana Ron:
On the possibilities and limitations of pseudodeterministic algorithms. 101 - Swastik Kopparty, Srikanth Srinivasan:
Certifying Polynomials for $\mathrm{AC}^0[\oplus]$ circuits, with applications. 102 - Arnab Bhattacharyya, Yuichi Yoshida:
Testing Assignments of Boolean CSPs. 103 - Matthew K. Franklin, Ran Gelles, Rafail Ostrovsky, Leonard J. Schulman:
Optimal Coding for Streaming Authentication and Interactive Communication. 104 - Madhur Tulsiani, Pratik Worah:
$LS_+$ Lower Bounds from Pairwise Independence. 105 - Alan Guo, Madhu Sudan:
New affine-invariant codes from lifting. 106 - Brendan Juba, Ryan Williams:
Massive Online Teaching to Bounded Learners. 107 - Arkadev Chattopadhyay, Rahul Santhanam:
Lower Bounds on Interactive Compressibility by Constant-Depth Circuits. 108 - Subhash Khot, Muli Safra, Madhur Tulsiani:
Towards An Optimal Query Efficient PCP? 109 - Siu On Chan:
Approximation Resistance from Pairwise Independent Subgroups. 110 - Venkatesan Guruswami, Ali Kemal Sinop:
Faster SDP hierarchy solvers for local rounding algorithms. 111 - Andrew Drucker:
New Limits to Classical and Quantum Instance Compression. 112 - Manindra Agrawal, Chandan Saha, Nitin Saxena:
Quasi-polynomial Hitting-set for Set-depth-$\Delta$ Formulas. 113 - Mikhail Anokhin:
Constructing a Pseudo-Free Family of Finite Computational Groups under the General Integer Factoring Intractability Assumption. 114 - Michael A. Forbes, Amir Shpilka:
Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs. 115 - Luca Trevisan:
A Derandomized Switching Lemma and an Improved Derandomization of AC0. 116 - Loïck Magnin, Jérémie Roland:
Explicit relation between all lower bound techniques for quantum query complexity. 117 - Avi Wigderson, Amir Yehudayoff:
Population Recovery and Partial Identification. 118 - Ilario Bonacina, Nicola Galesi:
Pseudo-partitions, Transversality and Locality: A Combinatorial Characterization for the Space Measure in Algebraic Proof Systems. 119 - Boaz Barak:
Proof vs. Truth in Computational Complexity. 120 - Pavel Hrubes:
A note on the real $\tau$-conjecture and the distribution of roots. 121 - Giorgio Ausiello, Francesco Cristiano, Luigi Laura:
Syntactic Isomorphism of CNF Boolean Formulas is Graph Isomorphism Complete. 122 - Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil P. Vadhan:
Better pseudorandom generators from milder pseudorandom restrictions. 123 - Massimo Lauria:
A rank lower bound for cutting planes proofs of Ramsey Theorem. 124 - Zahra Jafargholi, Hamidreza Jahanjou, Eric Miles, Jaideep Ramachandran, Emanuele Viola:
From RAM to SAT. 125 - Shiva Kintali, Sinziana Munteanu:
Computing Bounded Path Decompositions in Logspace. 126 - Eshan Chattopadhyay, Adam R. Klivans, Pravesh Kothari:
An Explicit VC-Theorem for Low-Degree Polynomials. 127 - Nathanaël François, Frédéric Magniez:
Streaming Complexity of Checking Priority Queues. 128 - Iftach Haitner, Eran Omri, Hila Zarosim:
On the Power of Random Oracles. 129 - Abuzer Yakaryilmaz:
Public-qubits versus private-coins. 130 - Mark Braverman, Ankur Moitra:
An Information Complexity Approach to Extended Formulations. 131 - Yuval Filmus, Massimo Lauria, Jakob Nordström, Noga Ron-Zewi, Neil Thapen:
Space Complexity in Polynomial Calculus. 132 - Noga Alon, Gil Cohen:
On Rigid Matrices and Subspace Polynomials. 133 - Alexander A. Razborov, Emanuele Viola:
Real Advantage. 134 - Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, Julia Wolf:
Sampling-based proofs of almost-periodicity results and algorithmic applications. 135 - Dan Boneh, Mark Zhandry:
Quantum-Secure Message Authentication Codes. 136 - Johan Håstad:
On the correlation of parity and small-depth circuits. 137 - Zeev Dvir, Shubhangi Saraf, Avi Wigderson:
Improved rank bounds for design matrices and a new proof of Kelly's theorem. 138 - Albert Ai, Zeev Dvir, Shubhangi Saraf, Avi Wigderson:
Sylvester-Gallai type theorems for approximate collinearity. 139 - Mark Zhandry:
How to Construct Quantum Random Functions. 140 - Dmitry Itsykson, Dmitry Sokolov:
Lower bounds for myopic DPLL algorithms with a cut heuristic. 141