default search action
Electronic Colloquium on Computational Complexity, 2012
Volume TR12, 2012
- Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett:
Testing Low Complexity Affine-Invariant Properties. - Akinori Kawachi, Benjamin Rossman, Osamu Watanabe:
Query Complexity and Error Tolerance of Witness Finding Algorithms. - Pratik Worah:
Rank Bounds for a Hierarchy of Lovász and Schrijver. - Marcos Villagra, Masaki Nakanishi, Shigeru Yamashita, Yasuhiko Nakashima:
Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication. - Periklis A. Papakonstantinou, Guang Yang:
A remark on one-wayness versus pseudorandomness. - Gregory Valiant:
Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas with Noise. - Ruiwen Chen, Valentine Kabanets:
Lower Bounds against Weakly Uniform Circuits. - Marek Karpinski, Richard Schmied:
On Approximation Lower Bounds for TSP with Bounded Metrics. - Prabhu Manyem, Julien Ugon:
Computational Complexity, NP Completeness and Optimization Duality: A Survey. - Shafi Goldwasser, Guy N. Rothblum:
How to Compute in the Presence of Leakage. - Nader H. Bshouty:
Testers and their Applications. - Oded Goldreich:
On the Effect of the Proximity Parameter on Property Testers. - Tomás Feder, Carlos S. Subi:
Packing Edge-Disjoint Triangles in Given Graphs. - Johannes Mittmann, Nitin Saxena, Peter Scheiblechner:
Algebraic Independence in Positive Characteristic - A p-Adic Calculus. - Albert Atserias, Anuj Dawar:
Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers. - Anindya De, Elchanan Mossel:
Explicit Optimal hardness via Gaussian stability results. - Venkatesan Guruswami, Srivatsan Narayanan:
Combinatorial limitations of a strong form of list decoding. - Jörg Flum, Moritz Müller:
Some definitorial suggestions for parameterized proof complexity. - Eric Miles, Emanuele Viola:
On the complexity of constructing pseudorandom functions (especially when they don't exist). - Daniele Micciancio:
Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction. - Oded Goldreich:
Two-Sided Error Proximity Oblivious Testing. - Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler:
Annotations in Data Streams. - Sophie Laplante, Virginie Lerays, Jérémie Roland:
Classical and quantum partition bound and detector inefficiency. - Scott Aaronson, Paul F. Christiano:
Quantum Money from Hidden Subspaces. - 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. - Thomas Watson:
Time Hierarchies for Sampling Distributions. - Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, Bangsheng Tang:
Time-space tradeoffs for width-parameterized SAT: Algorithms and lower bounds. - Eric Allender, George Davie, Luke Friedman, Samuel B. Hopkins, Iddo Tzameret:
Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic. - Shachar Lovett:
An exposition of Sanders quasi-polynomial Freiman-Ruzsa theorem. - Deeparnab Chakrabarty, C. Seshadhri:
Optimal bounds for monotonicity and Lipschitz testing over the hypercube. - Tom Gur, Omer Tamuz:
Testing Booleanity and the Uncertainty Principle. - Sebastian Kuhnert, Johannes Köbler, Osamu Watanabe:
Interval graph representation with given interval and intersection lengths. - Ankit Gupta, Neeraj Kayal, Youming Qiao:
Random Arithmetic Formulas can be Reconstructed Efficiently. - Abhishek Bhowmick, Zeev Dvir, Shachar Lovett:
New Lower Bounds for Matching Vector Codes. - Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler
:
Finding Cycles and Trees in Sublinear Time. - Venkatesan Guruswami, Chaoping Xing:
Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding. - Alexander A. Sherstov:
Making Polynomials Robust to Noise. - Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jérémie Roland, David Xiao:
Lower bounds on information complexity via zero-communication protocols and applications. - Stasys Jukna:
Clique Problem, Cutting Plane Proofs, and Communication Complexity. - Sangxia Huang:
Approximation Resistance on Satisfiable Instances for Predicates Strictly Dominating Parity. - Stasys Jukna:
Limitations of Incremental Dynamic Programs. - Chris Beck, Russell Impagliazzo, Shachar Lovett:
Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits. - Zvika Brakerski, Yael Tauman Kalai:
Efficient Interactive Coding Against Adversarial Noise. - Swastik Kopparty:
List-Decoding Multiplicity Codes. - Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer:
On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs. - Madhu Sudan, Noga Zewi:
A new upper bound on the query complexity for testing generalized Reed-Muller codes. - Emanuele Viola:
Extractors for Turing-machine sources. - Alan Guo, Madhu Sudan:
Some closure features of locally testable affine-invariant properties. - Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan:
Sparse affine-invariant linear codes are locally testable. - Avraham Ben-Aroya, Gil Cohen:
Gradual Small-Bias Sample Spaces. - Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan:
A Tail Bound for Read-k Families of Functions. - Mohammad Mahmoody, David Xiao:
Languages with Efficient Zero-Knowledge PCPs are in SZK. - Ankur Moitra:
A Singly-Exponential Time Algorithm for Computing Nonnegative Rank. - Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff:
Reductions to the set of random strings: the resource-bounded case. - Reut Levi, Dana Ron, Ronitt Rubinfeld:
Testing Similar Means. - Rocco A. Servedio, Li-Yang Tan, Justin Thaler:
Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions. - Russell Impagliazzo, Raghu Meka, David Zuckerman:
Pseudorandomness from Shrinkage. - Benny Applebaum, Yuval Ishai, Eyal Kushilevitz:
How to Garble Arithmetic Circuits. - Rahul Santhanam, Ryan Williams:
Uniform Circuits, Lower Bounds, and QBF Algorithms. - Parikshit Gopalan, Raghu Meka, Omer Reingold:
DNF Sparsification and a Faster Deterministic Counting. - Pavel Hrubes, Amir Yehudayoff:
Formulas are exponentially stronger than monotone circuits in non-commutative setting. - Ilan Komargodski, Ran Raz:
Average-Case Lower Bounds for Formula Size. - Raghav Kulkarni, Miklos Santha:
Query complexity of matroids. - Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala, Ying Xiao:
Statistical Algorithms and a Lower Bound for Planted Clique. - Mohammad Mahmoody, Hemanta K. Maji, Manoj Prabhakaran:
Limits of Random Oracles in Secure Computation. - Jinyu Huang:
Parallel Complexity for Matroid Intersection and Matroid Parity Problems. - Xiaohui Bei
On the Complexity of Trial and Error. - Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena:
Deterministic Polynomial Factoring and Association Schemes. - Lakhdar Saïs, Mohand-Said Hacid, François Hantry:
On the complexity of computing minimal unsatisfiable LTL formulas. - Thomas Watson:
The Complexity of Estimating Min-Entropy. - Kazuhisa Seto, Suguru Tamaki:
A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis. - Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco A. Servedio:
Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces. - Venkatesan Guruswami, Carol Wang:
Linear-algebraic list decoding for variants of Reed-Solomon codes. - Venkatesan Guruswami, Yuan Zhou:
Approximating Bounded Occurrence Ordering CSPs. - Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova:
Limitations of Local Filters of Lipschitz and Monotone Functions. - Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova:
Testing Lipschitz Functions on Hypergrid Domains. - Chiranjit Chakraborty, Rahul Santhanam:
Instance Compression for the Polynomial Hierarchy and Beyond. - Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Yadu Vasudev:
Approximate Graph Isomorphism. - Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer:
Verifying Proofs in Constant Depth. - Baris Aydinlioglu, Dieter van Melkebeek:
Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Games. - Neeraj Kayal:
An exponential lower bound for the sum of powers of bounded degree polynomials. - Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker:
Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes. - Thomas Steinke:
Pseudorandomness for Permutation Branching Programs Without the Group Theory. - Rahul Santhanam:
Ironic Complicity: Satisfiability Algorithms and Circuit Lower Bounds. - Tsuyoshi Ito, Thomas Vidick:
A multi-prover interactive proof for NEXP sound against entangled provers. - Shlomi Dolev, Nova Fandina, Dan Gutfreund:
Succinct Permanent is NEXP-hard with Many Hard Instances. - Peyman Afshani, Manindra Agrawal, Benjamin Doerr, Carola Winzen, Kasper Green Larsen, Kurt Mehlhorn:
The Deterministic and Randomized Query Complexity of a Simple Guessing Game. - Irit Dinur, Gillat Kol:
Covering CSPs. - Meena Boppana:
Lattice Variant of the Sensitivity Conjecture. - Michael Blondin, Andreas Krebs, Pierre McKenzie:
The Complexity of Intersecting Finite Automata Having Few Final States. - Abuzer Yakaryilmaz:
One-counter verifiers for decidable languages. - Pavol Duris:
A Note On the Hierarchy of One-way Data-Independent Multi-Head Finite Automata. - Charanjit S. Jutla, Vijay Kumar, Atri Rudra:
On the Circuit Complexity of Composite Galois Field Transformations. - Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva:
Testing Permanent Oracles - Revisited. - Avraham Ben-Aroya, Igor Shinkar:
A Note on Subspace Evasive Sets. - Albert Atserias, Sergi Oliva:
Bounded-width QBF is PSPACE-complete. - Andrej Bogdanov, Siyao Guo:
Sparse extractor families for all the entropy. - Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi:
An exponential lower bound for homogeneous depth four arithmetic circuits with bounded bottom fanin. - Nikos Leonardos:
An improved lower bound for the randomized decision tree complexity of recursive majority. - Tomas Jirotka:
NP Search Problems. - Oded Goldreich, Shafi Goldwasser, Dana Ron:
On the possibilities and limitations of pseudodeterministic algorithms. - Swastik Kopparty, Srikanth Srinivasan:
Certifying Polynomials for AC0[⊕] circuits, with applications. - Arnab Bhattacharyya, Yuichi Yoshida:
Testing Assignments of Boolean CSPs. - Matthew K. Franklin, Ran Gelles, Rafail Ostrovsky, Leonard J. Schulman:
Optimal Coding for Streaming Authentication and Interactive Communication. - Madhur Tulsiani, Pratik Worah:
$LS_+$ Lower Bounds from Pairwise Independence. - Alan Guo, Madhu Sudan:
New affine-invariant codes from lifting. - Brendan Juba, Ryan Williams:
Massive Online Teaching to Bounded Learners. - Arkadev Chattopadhyay, Rahul Santhanam:
Lower Bounds on Interactive Compressibility by Constant-Depth Circuits. - Subhash Khot, Muli Safra
Towards An Optimal Query Efficient PCP? - Siu On Chan:
Approximation Resistance from Pairwise Independent Subgroups. - Venkatesan Guruswami, Ali Kemal Sinop:
Faster SDP hierarchy solvers for local rounding algorithms. - Andrew Drucker:
New Limits to Classical and Quantum Instance Compression. - Manindra Agrawal, Chandan Saha, Nitin Saxena:
Quasi-polynomial Hitting-set for Set-depth-$\Delta$ Formulas. - Mikhail Anokhin:
Constructing a Pseudo-Free Family of Finite Computational Groups under the General Integer Factoring Intractability Assumption. - Michael A. Forbes, Amir Shpilka:
Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs. - Luca Trevisan:
A Derandomized Switching Lemma and an Improved Derandomization of AC0. - Loïck Magnin, Jérémie Roland:
Explicit relation between all lower bound techniques for quantum query complexity. - Avi Wigderson, Amir Yehudayoff:
Population Recovery and Partial Identification. - Ilario Bonacina, Nicola Galesi:
Pseudo-partitions, Transversality and Locality: A Combinatorial Characterization for the Space Measure in Algebraic Proof Systems. - Boaz Barak:
Proof vs. Truth in Computational Complexity. - Pavel Hrubes:
A note on the real $\tau$-conjecture and the distribution of roots. - Giorgio Ausiello, Francesco Cristiano, Luigi Laura:
Syntactic Isomorphism of CNF Boolean Formulas is Graph Isomorphism Complete. - Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil P. Vadhan:
Better pseudorandom generators from milder pseudorandom restrictions. - Massimo Lauria:
A rank lower bound for cutting planes proofs of Ramsey Theorem. - Zahra Jafargholi, Hamidreza Jahanjou, Eric Miles, Jaideep Ramachandran, Emanuele Viola:
From RAM to SAT. - Shiva Kintali, Sinziana Munteanu:
Computing Bounded Path Decompositions in Logspace. - Eshan Chattopadhyay, Adam R. Klivans, Pravesh Kothari:
An Explicit VC-Theorem for Low-Degree Polynomials. - Nathanaël François, Frédéric Magniez:
Streaming Complexity of Checking Priority Queues. - Iftach Haitner, Eran Omri, Hila Zarosim:
On the Power of Random Oracles. - Abuzer Yakaryilmaz:
Public-qubits versus private-coins. - Mark Braverman, Ankur Moitra:
An Information Complexity Approach to Extended Formulations. - Yuval Filmus, Massimo Lauria, Jakob Nordström, Noga Ron-Zewi, Neil Thapen:
Space Complexity in Polynomial Calculus. - Noga Alon, Gil Cohen:
On Rigid Matrices and Subspace Polynomials. - Alexander A. Razborov, Emanuele Viola:
Real Advantage. - Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, Julia Wolf:
Sampling-based proofs of almost-periodicity results and algorithmic applications. - Dan Boneh, Mark Zhandry:
Quantum-Secure Message Authentication Codes. - Johan Håstad:
On the correlation of parity and small-depth circuits. - Zeev Dvir, Shubhangi Saraf, Avi Wigderson:
Improved rank bounds for design matrices and a new proof of Kelly's theorem. - Albert Ai, Zeev Dvir, Shubhangi Saraf, Avi Wigderson:
Sylvester-Gallai type theorems for approximate collinearity. - Mark Zhandry:
How to Construct Quantum Random Functions. - Dmitry Itsykson, Dmitry Sokolov:
Lower bounds for myopic DPLL algorithms with a cut heuristic. - Markus Bläser:
Noncommutativity makes determinants hard. - Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff:
Direct Products in Communication Complexity. - Rocco A. Servedio, Emanuele Viola:
On a special case of rigidity. - Cenny Wenner:
Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four. - Venkatesan Guruswami, Chaoping Xing:
List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound. - Xin Li:
New Independent Source Extractors with Exponential Improvement. - Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf:
A new family of locally correctable codes based on degree-lifted algebraic geometry codes. - Alan Guo, Swastik Kopparty, Madhu Sudan:
New affine-invariant codes from lifting. - Michael Elberfeld, Christoph Stockhusen, Till Tantau:
On the Space Complexity of Parameterized Problems. - Subhash Khot, Madhur Tulsiani, Pratik Worah:
The Complexity of Somewhat Approximation Resistant Predicates. - Anindya De, Ilias Diakonikolas, Rocco A. Servedio:
Inverse Problems in Approximate Uniform Generation. - Joshua Brody, Amit Chakrabarti, Ranganath Kondapally:
Certifying Equality With Limited Interaction. - Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah:
On the Power of Conditional Samples in Distribution Testing. - Clément L. Canonne, Dana Ron, Rocco A. Servedio:
Testing probability distributions using conditional samples. - Andrej Bogdanov, Chin Ho Lee:
Limits of provable security for homomorphic encryption. - Andrej Bogdanov, Chin Ho Lee:
On the depth complexity of homomorphic encryption schemes. - Aditya Bhaskara, Devendra Desai, Srikanth Srinivasan:
Optimal Hitting Sets for Combinatorial Shapes. - Eli Ben-Sasson, Michael Viderman:
A Combinatorial Characterization of smooth LTCs and Applications. - Frederic Green, Daniel Kreymer, Emanuele Viola:
Block-symmetric polynomials correlate with parity better than symmetric. - Olaf Beyersdorff, Nicola Galesi, Massimo Lauria:
A Characterization of Tree-Like Resolution Size. - Hans-Joachim Böckenhauer, Juraj Hromkovic, Dennis Komm, Sacha Krug, Jasmin Smula, Andreas Sprock:
The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity. - Avishay Tal:
Properties and Applications of Boolean Function Composition. - Rafail Ostrovsky, Ivan Visconti:
Simultaneous Resettability from Collision Resistance. - Martin R. Albrecht, Pooya Farshim, Jean-Charles Faugère, Gottfried Herold, Ludovic Perret:
Polly Cracker, Revisited. - Elad Haramaty, Madhu Sudan:
Deterministic Compression with Uncertain Priors. - Periklis A. Papakonstantinou, Charles Rackoff, Yevgeniy Vahlis:
How powerful are the DDH hard groups? - Michael Viderman:
Strong LTCs with inverse polylogarithmic rate and soundness. - Noga Alon, Santosh S. Vempala:
The Approximate Rank of a Matrix and its Algorithmic Applications. - Scott Aaronson, Travis Hance:
Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent. - Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein:
From Information to Exact Communication. - Mahdi Cheraghchi, Anna Gál, Andrew Mills:
Correctness and Corruption of Locally Decodable Codes. - Kfir Barhum, Thomas Holenstein:
A Cookbook for Black-Box Separations and a Recipe for UOWHFs. - Anat Ganor, Ilan Komargodski, Ran Raz:
The Spectrum of Small DeMorgan Formulas. - James Cook, Omid Etesami, Rachel Miller, Luca Trevisan:
On the One-Way Function Candidate Proposed by Goldreich. - Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu:
Optimal Cuts and Partitions in Tree Metrics in Polynomial Time. - Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein:
Information lower bounds via self-reducibility. - Paul Beame, Raphaël Clifford, Widad Machmouchi:
Sliding Windows With Limited Storage. - Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman:
Towards a Reverse Newman's Theorem in Interactive Information Complexity. - Chaim Even-Zohar, Shachar Lovett:
The Freiman-Ruzsa Theorem in Finite Fields. - Anindya De, Ilias Diakonikolas, Rocco A. Servedio:
The Inverse Shapley Value Problem. - Itay Berman, Iftach Haitner, Ilan Komargodski, Moni Naor:
Hardness Preserving Reductions via Cuckoo Hashing. - András Z. Salamon:
Streaming bounds from difference ramification. - Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett:
Every locally characterized affine-invariant property is testable. - Siu Man Chan, Aaron Potechin:
Tight Bounds for Monotone Switching Networks via Fourier Analysis. - Andreas Krebs, Nutan Limaye:
DLOGTIME-Proof Systems.
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 2025-11-14 22:26 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: