default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDElectronic Colloquium on Computational Complexity, 2013
Volume TR13, 2013
- Gillat Kol, Ran Raz:
Interactive Channel Capacity. - Venkatesan Guruswami, Krzysztof Onak:
Superlinear lower bounds for multipass graph processing. - Eric Miles, Emanuele Viola:
Shielding circuits with groups. - A. C. Cem Say, Abuzer Yakaryilmaz:
Finite state verifiers with constant randomness. - Alexander A. Sherstov:
Communication Lower Bounds Using Directional Derivatives. - Balagopal Komarath, Jayalal Sarma:
Pebbling, Entropy and Branching Program Size Lower Bounds. - Bruno Bauwens, Anton Makhlin, Nikolay K. Vereshchagin, Marius Zimand:
Short lists with short programs in short time. - Adam R. Klivans, Raghu Meka:
Moment-Matching Polynomials. - Zahra Jafargholi, Emanuele Viola:
3SUM, 3XOR, Triangles. - Yang Liu, Shengyu Zhang:
Quantum and randomized communication complexity of XOR functions in the SMP model. - Nader H. Bshouty:
Multilinear Complexity is Equivalent to Optimal Tester Size. - Hasan Abasi, Nader H. Bshouty:
A Simple Algorithm for Undirected Hamiltonicity. - Daniel Apon, Jonathan Katz, Alex J. Malozemoff:
One-Round Multi-Party Communication Complexity of Distinguishing Sums. - Zvika Brakerski, Moni Naor:
Fast Algorithms for Interactive Coding. - Iordanis Kerenidis, Mathieu Laurière, David Xiao:
New lower bounds for privacy in communication protocols. - Olaf Beyersdorff:
The Complexity of Theorem Proving in Autoepistemic Logic. - Pratik Worah:
A Short Excursion into Semi-Algebraic Hierarchies. - Luke Friedman, Yixin Xu:
Exponential Lower Bounds for Refuting Random Formulas Using Ordered Binary Decision Diagrams. - Stephen A. Fenner, Rohit Gurjar, Arpita Korwar, Thomas Thierauf:
On Two-Level Poset Games. - Tom Gur, Ran Raz:
Arthur-Merlin Streaming Complexity. - Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii:
Polynomial threshold functions and Boolean threshold circuits. - Michael Viderman:
Strong LTCs with inverse poly-log rate and constant soundness. - Alexander A. Sherstov:
Approximating the AND-OR Tree. - Valentine Kabanets, Antonina Kolokolova:
Compression of Boolean Functions. - Xin Li:
Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy. - Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi:
Arithmetic circuits: A chasm at depth three. - Luke Friedman:
A Framework for Proving Proof Complexity Lower Bounds on Random CNFs Using Encoding Techniques. - Mrinal Kumar, Gaurav Maheshwari, Jayalal Sarma:
Arithmetic Circuit Lower Bounds via MaxRank. - Deeparnab Chakrabarty, C. Seshadhri:
A o(n) monotonicity tester for Boolean functions over the hypercube. - Elad Haramaty, Noga Ron-Zewi, Madhu Sudan:
Absolutely Sound Testing of Lifted Codes. - Irit Dinur, Elazar Goldenberg:
Clustering in the Boolean Hypercube in a List Decoding Regime. - Mark Bun, Justin Thaler:
Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities. - Michael A. Forbes, Amir Shpilka:
Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing. - Louay Bazzi, Nagi Nahas:
Small-bias is not enough to hit read-once CNF. - Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff:
Direct product via round-preserving compression. - Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev:
Lower Bounds for Testing Properties of Functions on Hypergrid Domains. - Alexander Knop:
Circuit Lower Bounds for Heuristic MA. - Massimo Lauria, Pavel Pudlák, Vojtech Rödl, Neil Thapen:
The complexity of proving that a graph is Ramsey. - Arturs Backurs, Mohammad Bavarian:
On the sum of L1 influences. - Michaël Cadilhac, Andreas Krebs, Pierre McKenzie:
The Algebraic Theory of Parikh Automata. - Igor Sergeev:
On the complexity of parallel prefix circuits. - Siu Man Chan:
Just a Pebble Game. - Oded Goldreich, Avi Wigderson:
On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions. - Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang:
Shared Randomness and Quantum Communication in the Multi-Party Model. - Marek Karpinski, Michael Lampis, Richard Schmied:
New Inapproximability Bounds for TSP. - Venkatesan Guruswami, Chaoping Xing:
Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets. - Christian Glaßer, Dung T. Nguyen, Christian Reitwießner, Alan L. Selman, Maximilian Witek:
Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions. - Jin-Yi Cai, Aaron Gorenstein:
Matchgates Revisited. - Amir Shpilka, Ben lee Volk:
On the Structure of Boolean Functions with Small Spectral Norm. - Venkatesan Guruswami, Patrick Xia:
Polar Codes: Speed of polarization and polynomial gap to capacity. - Eric Blais, Li-Yang Tan:
Approximating Boolean functions with depth-2 circuits. - Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh:
Upper Bounds on Fourier Entropy. - Alan Guo:
High rate locally correctable codes via lifting. - Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook:
Average Case Lower Bounds for Monotone Switching Networks. - David Gamarnik, Madhu Sudan:
Limits of local algorithms over sparse random graphs. - Gábor Braun, Sebastian Pokutta:
Common information and unique disjointness. - Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman:
Mining Circuit Lower Bound Proofs for Meta-Algorithms. - Ilan Komargodski, Ran Raz, Avishay Tal:
Improved Average-Case Lower Bounds for DeMorgan Formula Size. - Lior Gishboliner, Asaf Shapira:
Deterministic vs Non-deterministic Graph Property Testing. - Venkatesan Guruswami, Swastik Kopparty:
Explicit Subspace Designs. - Zeev Dvir, Guangda Hu:
Matching-Vector Families and LDCs Over Large Modulo. - Deeparnab Chakrabarty, C. Seshadhri:
An optimal lower bound for monotonicity testing over hypergrids. - Dung T. Nguyen, Alan L. Selman:
Non-autoreducible Sets for NEXP. - Anat Ganor, Ran Raz:
Space Pseudorandom Generators by Communication Complexity Lower Bounds. - Yijia Chen, Jörg Flum:
On Limitations of the Ehrenfeucht-Fraisse-method in Descriptive Complexity. - Marek Karpinski, Richard Schmied:
Approximation Hardness of Graphic TSP on Cubic Graphs. - Oded Goldreich:
On Multiple Input Problems in Property Testing. - Mrinal Kumar, Shubhangi Saraf:
Lower Bounds for Depth 4 Homogenous Circuits with Bounded Top Fanin. - Kousha Etessami, Alistair Stewart, Mihalis Yannakakis:
A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing. - Iddo Tzameret:
On Sparser Random 3SAT Refutation Algorithms and Feasible Interpolation. - Venkatesan Guruswami, Sushant Sachdeva, Rishi Saket:
Inapproximability of Minimum Vertex Cover on k-uniform k-partite Hypergraphs. - Jan Johannsen:
Exponential Separations in a Hierarchy of Clause Learning Proof Systems. - Oded Goldreich:
On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing. - Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky:
Helly Circular-Arc Graph Isomorphism is in Logspace. - Subhash Khot, Madhur Tulsiani, Pratik Worah:
A Characterization of Strong Approximation Resistance. - Divesh Aggarwal, Chandan K. Dubey:
Improved hardness results for unique shortest vector problem. - Ján Pich:
Circuit Lower Bounds in Bounded Arithmetics. - Tom Gur, Ron Rothblum:
Non-Interactive Proofs of Proximity. - Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff:
Direct Sum Fails for Zero Error Average Communication. - Dmitry Gavinsky, Shachar Lovett:
En Route to the log-rank Conjecture: New Reductions and Equivalent Formulations. - Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett:
Non-malleable Codes from Additive Combinatorics. - Eldar Fischer, Yonatan Goldhirsh, Oded Lachish:
Some properties are not even partially testable. - Miklós Ajtai:
Lower Bounds for RAMs and Quantifier Elimination. - Shachar Lovett:
Communication is bounded by root of rank. - Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth:
Constant rate PCPs for circuit-SAT with sublinear query complexity. - Omer Reingold, Thomas Steinke, Salil P. Vadhan:
Pseudorandomness for Regular Branching Programs via Fourier Analysis. - Hamed Hatami, Shachar Lovett:
Estimating the distance from testable affine-invariant properties. - Zachary Remscrim, Michael Sipser:
AC0 Pseudorandomness of Natural Operations. - Abhishek Bhrushundi:
On testing bent functions. - Elena Grigorescu, Karl Wimmer, Ning Xie:
Tight Lower Bounds for Testing Linear Isomorphism. - Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi:
A super-polynomial lower bound for regular arithmetic formulas. - Pavel Pudlák, Arnold Beckmann, Neil Thapen:
Parity Games and Propositional Proofs. - Anna Gál, Jing-Tang Jang:
A Generalization of Spira's Theorem and Circuits with Small Segregators or Separators. - Brendan Juba:
On Non-automatizability in PAC-Semantics. - Uriel Feige, Rani Izsak:
Welfare Maximization and the Supermodular Degree. - Dana Ron, Rocco A. Servedio:
Exponentially improved algorithms and lower bounds for testing signed majorities. - Mikolás Janota, João Marques-Silva:
On Propositional QBF Expansions and Q-Resolution. - Benny Applebaum, Yoni Moses:
Locally Computable UOWHF with Linear Shrinkage. - Hamidreza Jahanjou, Eric Miles, Emanuele Viola:
Local reductions. - Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan:
Lower bounds for depth 4 formulas computing iterated matrix multiplication. - Colin Jia Zheng, Salil P. Vadhan:
A Uniform Min-Max Theorem with Applications in Cryptography. - Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah:
Small Depth Proof Systems. - Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha:
Generalized Wong sequences and their applications to Edmonds' problems. - Parikshit Gopalan, Cheng Huang, Bob Jenkins, Sergey Yekhanin:
Explicit Maximally Recoverable Codes with Locality. - Raghu Meka, Avi Wigderson:
Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique. - Shay Moran, Amir Yehudayoff:
A note on average-case sorting. - Gil Cohen, Ivan Bjerre Damgård, Yuval Ishai, Jonas Kölker, Peter Bro Miltersen, Ran Raz, Ron Rothblum:
Efficient Multiparty Protocols via Log-Depth Threshold Formulae. - Rahul Santhanam, Ryan Williams:
New Algorithms for QBF Satisfiability and Implications for Circuit Complexity. - Oded Goldreich, Dana Ron:
On Sample-Based Testers. - Xiaoming Sun, Marcos Villagra:
Exponential Quantum-Classical Gaps in Multiparty Nondeterministic Communication Complexity. - Gregory Valiant, Paul Valiant:
Instance-by-instance optimal identity testing. - Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf:
Exact Perfect Matching in Complete Graphs. - Moritz Müller, Stefan Szeider:
Revisiting Space in Proof Complexity: Treewidth and Pathwidth. - Parikshit Gopalan, Salil P. Vadhan, Yuan Zhou:
Locally Testable Codes and Cayley Graphs. - Daniele Micciancio:
Locally Dense Codes. - Albert Atserias, Moritz Müller, Sergi Oliva:
Lower Bounds for DNF-Refutations of a Relativized Weak Pigeonhole Principle. - Igor C. Oliveira:
Algorithms versus Circuit Lower Bounds. - Mahdi Cheraghchi, Venkatesan Guruswami:
Capacity of Non-Malleable Codes. - Emanuele Viola:
Challenges in computational lower bounds. - Zeyu Guo:
Randomness-efficient Curve Samplers. - Mahdi Cheraghchi, Venkatesan Guruswami:
Non-Malleable Coding Against Bit-wise and Split-State Tampering. - Irit Dinur, Venkatesan Guruswami:
PCPs via low-degree long code and hardness for constrained hypergraph coloring. - Joshua A. Grochow, Youming Qiao:
Algorithms for group isomorphism via group extensions and cohomology. - Thomas Watson:
The Complexity of Deciding Statistical Properties of Samplable Distributions. - Venkatesan Guruswami, Euiwoong Lee:
Complexity of approximating CSP with Balance / Hard Constraints. - Arman Fazeli, Shachar Lovett, Alexander Vardy:
Nontrivial t-designs over finite fields exist for all t. - Paul Beame, Raphaël Clifford, Widad Machmouchi:
Element Distinctness, Frequency Moments, and Sliding Windows. - Pavel Hrubes:
A note on semantic cutting planes. - Adam R. Klivans, Pravesh Kothari, Igor C. Oliveira:
Constructing Hard Functions from Learning Algorithms. - Mark Braverman, Ankit Garg:
Public vs private coin in bounded-round information. - Nikhil Balaji, Samir Datta:
Collapsing Exact Arithmetic Hierarchies. - Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka:
Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order. - Cassio P. de Campos, Georgios Stamoulis, Dennis Weyland:
A Structured View on Weighted Counting with Relations to Quantum Computation and Applications. - Or Meir:
Combinatorial PCPs with Short Proofs. - Scott Aaronson:
BosonSampling Is Far From Uniform. - Paul W. Goldberg, Aaron Roth:
Bounds for the Query Complexity of Approximate Equilibria. - Mohammad Mahmoody, Hemanta K. Maji, Manoj Prabhakaran:
On the Power of Public-key Encryption in Secure Computation. - Itai Benjamini, Gil Cohen, Igor Shinkar:
Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball. - Peter Floderus, Andrzej Lingas, Mia Persson, Dzmitry Sledneu:
Detecting Monomials with k Distinct Variables. - Atri Rudra, Mary Wootters:
Every list-decodable code for high noise has abundant near-optimal rate puncturings. - Leonid Gurvits:
Boolean matrices with prescribed row/column sums and stable homogeneous polynomials: combinatorial and algorithmic applications. - Abhishek Bhrushundi, Sourav Chakraborty, Raghav Kulkarni:
Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees. - Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, David Zuckerman:
Robust Pseudorandom Generators. - VyasRam Selvam:
The two queries assumption and Arthur-Merlin classes. - Gil Cohen, Avishay Tal:
Two Structural Results for Low Degree Polynomials and Applications. - Subhash Khot, Madhur Tulsiani, Pratik Worah:
A Characterization of Approximation Resistance. - Adam Bouland, Scott Aaronson:
Any Beamsplitter Generates Universal Quantum Linear Optics. - Irit Dinur, Igor Shinkar:
On the Conditional Hardness of Coloring a 4-colorable Graph with Super-Constant Number of Colors. - Albert Atserias, Neil Thapen:
The Ordering Principle in a Fragment of Approximate Counting. - Ruiwen Chen, Valentine Kabanets, Nitin Saurabh:
An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas. - Mark Bun, Justin Thaler:
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits. - Oded Goldreich, Avi Wigderson:
On Derandomizing Algorithms that Err Extremely Rarely. - Mrinal Kumar, Shubhangi Saraf:
The Limits of Depth Reduction for Arithmetic Formulas: It's all about the top fan-in. - Martin Schwarz, Maarten Van den Nest:
Simulating Quantum Circuits with Sparse Output Distributions. - Gil Cohen, Amnon Ta-Shma:
Pseudorandom Generators for Low Degree Polynomials from Algebraic Geometry Codes. - Jan Krajícek:
A reduction of proof complexity to computational complexity for AC0[p] Frege systems. - Bin Fu:
Derandomizing Polynomial Identity over Finite Fields Implies Super-Polynomial Circuit Lower Bounds for NEXP. - Gábor Braun, Rahul Jain, Troy Lee, Sebastian Pokutta:
Information-theoretic approximations of the nonnegative rank. - Per Austrin, Venkatesan Guruswami, Johan Håstad:
(2+ε)-SAT is NP-hard. - Zeev Dvir, Shubhangi Saraf, Avi Wigderson:
Breaking the quadratic barrier for 3-LCCs over the Reals. - Jack H. Lutz:
The Frequent Paucity of Trivial Strings. - Janka Chlebíková, Morgan Chopin:
The Firefighter Problem: A Structural Analysis. - Russell Impagliazzo, Valentine Kabanets:
Fourier Concentration from Shrinkage. - Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian:
Weak Parity. - Michael Walfish, Andrew J. Blumberg:
Verifying computations without reexecuting them: from theoretical possibility to near-practicality. - Arnab Bhattacharyya:
On testing affine-invariant properties. - Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma:
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes. - Raghav Kulkarni, Avishay Tal:
On Fractional Block Sensitivity. - Benjamin Rossman:
Formulas vs. Circuits for Small Distance Connectivity. - Venkatesan Guruswami, Carol Wang:
Explicit rank-metric codes list-decodable with optimal redundancy. - Anindya De, Ilias Diakonikolas, Rocco A. Servedio:
Deterministic Approximate Counting for Juntas of Degree-2 Polynomial Threshold Functions. - Anindya De, Ilias Diakonikolas, Rocco A. Servedio:
Deterministic Approximate Counting for Degree-2 Polynomial Threshold Functions. - Anindya De, Rocco A. Servedio:
Efficient deterministic approximate counting for low degree polynomial threshold functions. - Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena:
Hitting-sets for low-distance multilinear depth-3. - Venkatesan Guruswami, Chaoping Xing:
Hitting Sets for Low-Degree Polynomials with Optimal Density. - Daniel M. Kane, Osamu Watanabe:
A Short Implicant of CNFs with Relatively Many Satisfying Assignments. - Eric Allender, Nikhil Balaji, Samir Datta:
Low-depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs. - Nikolay K. Vereshchagin:
Randomized communication complexity of appropximating Kolmogorov complexity. - Irit Dinur, David Steurer:
Direct Product Testing. - Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian:
On Interactivity in Arthur-Merlin Communication and Stream Computation. - Mrinal Kumar, Shubhangi Saraf:
Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits. - Boaz Barak:
Structure vs Combinatorics in Computational Complexity. - Yael Tauman Kalai, Ran Raz, Ron Rothblum:
How to Delegate Computations: The Power of No-Signaling Proofs. - Boaz Barak, Jonathan A. Kelner, David Steurer:
Rounding Sum-of-Squares Relaxations. - Fu Li, Iddo Tzameret:
Generating Matrix Identities and Proof Complexity Lower Bounds. - Nitin Saxena:
Progress on Polynomial Identity Testing - II. - Peyman Afshani, Kevin Matulef, Bryan T. Wilkinson:
Property Testing on Linked Lists. - Christian Glaßer, Maximilian Witek:
Autoreducibility and Mitoticity of Logspace-Complete Sets for NP and Other Classes. - Periklis A. Papakonstantinou, Dominik Scheder, Hao Song:
Overlays and Limited Memory Communication Mode(l)s. - Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson:
Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture. - Petr Savický:
Boolean functions with a vertex-transitive group of automorphisms.
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-05-05 20:53 CEST 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:
