Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDElectronic 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 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, Ning Chen, Shengyu Zhang:
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, Madhur Tulsiani:
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.