Google
Google Scholar
Semantic Scholar
MS Academic
CiteSeerX
ORCIDElectronic Colloquium on Computational Complexity, Volume 20
Volume 20, 2013
- Gillat Kol, Ran Raz:
Interactive Channel Capacity. 1 - Venkatesan Guruswami, Krzysztof Onak:
Superlinear lower bounds for multipass graph processing. 2 - Eric Miles, Emanuele Viola:
Shielding circuits with groups. 3 - A. C. Cem Say, Abuzer Yakaryilmaz:
Finite state verifiers with constant randomness. 4 - Alexander A. Sherstov:
Communication Lower Bounds Using Directional Derivatives. 5 - Balagopal Komarath, Jayalal Sarma:
Pebbling, Entropy and Branching Program Size Lower Bounds. 6 - Bruno Bauwens, Anton Makhlin, Nikolay K. Vereshchagin, Marius Zimand:
Short lists with short programs in short time. 7 - Adam R. Klivans, Raghu Meka:
Moment-Matching Polynomials. 8 - Zahra Jafargholi, Emanuele Viola:
3SUM, 3XOR, Triangles. 9 - Yang Liu, Shengyu Zhang:
Quantum and randomized communication complexity of XOR functions in the SMP model. 10 - Nader H. Bshouty:
Multilinear Complexity is Equivalent to Optimal Tester Size. 11 - Hasan Abasi, Nader H. Bshouty:
A Simple Algorithm for Undirected Hamiltonicity. 12 - Daniel Apon, Jonathan Katz, Alex J. Malozemoff:
One-Round Multi-Party Communication Complexity of Distinguishing Sums. 13 - Zvika Brakerski, Moni Naor:
Fast Algorithms for Interactive Coding. 14 - Iordanis Kerenidis, Mathieu Laurière, David Xiao:
New lower bounds for privacy in communication protocols. 15 - Olaf Beyersdorff:
The Complexity of Theorem Proving in Autoepistemic Logic. 16 - Pratik Worah:
A Short Excursion into Semi-Algebraic Hierarchies. 17 - Luke Friedman, Yixin Xu:
Exponential Lower Bounds for Refuting Random Formulas Using Ordered Binary Decision Diagrams. 18 - Stephen A. Fenner, Rohit Gurjar, Arpita Korwar, Thomas Thierauf:
On Two-Level Poset Games. 19 - Tom Gur, Ran Raz:
Arthur-Merlin Streaming Complexity. 20 - Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii:
Polynomial threshold functions and Boolean threshold circuits. 21 - Michael Viderman:
Strong LTCs with inverse poly-log rate and constant soundness. 22 - Alexander A. Sherstov:
Approximating the AND-OR Tree. 23 - Valentine Kabanets, Antonina Kolokolova:
Compression of Boolean Functions. 24 - Xin Li:
Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy. 25 - Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi:
Arithmetic circuits: A chasm at depth three. 26 - Luke Friedman:
A Framework for Proving Proof Complexity Lower Bounds on Random CNFs Using Encoding Techniques. 27 - Mrinal Kumar, Gaurav Maheshwari, Jayalal Sarma:
Arithmetic Circuit Lower Bounds via MaxRank. 28 - Deeparnab Chakrabarty, C. Seshadhri:
A o(n) monotonicity tester for Boolean functions over the hypercube. 29 - Elad Haramaty, Noga Ron-Zewi, Madhu Sudan:
Absolutely Sound Testing of Lifted Codes. 30 - Irit Dinur, Elazar Goldenberg:
Clustering in the Boolean Hypercube in a List Decoding Regime. 31 - Mark Bun, Justin Thaler:
Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities. 32 - Michael A. Forbes, Amir Shpilka:
Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing. 33 - Louay Bazzi, Nagi Nahas:
Small-bias is not enough to hit read-once CNF. 34 - Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff:
Direct product via round-preserving compression. 35 - Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev:
Lower Bounds for Testing Properties of Functions on Hypergrid Domains. 36 - Alexander Knop:
Circuit Lower Bounds for Heuristic MA. 37 - Massimo Lauria, Pavel Pudlák, Vojtech Rödl, Neil Thapen:
The complexity of proving that a graph is Ramsey. 38 - Arturs Backurs, Mohammad Bavarian:
On the sum of L1 influences. 39 - Michaël Cadilhac, Andreas Krebs, Pierre McKenzie:
The Algebraic Theory of Parikh Automata. 40 - Igor Sergeev:
On the complexity of parallel prefix circuits. 41 - Siu Man Chan:
Just a Pebble Game. 42 - Oded Goldreich, Avi Wigderson:
On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions. 43 - Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang:
Shared Randomness and Quantum Communication in the Multi-Party Model. 44 - Marek Karpinski, Michael Lampis, Richard Schmied:
New Inapproximability Bounds for TSP. 45 - Venkatesan Guruswami, Chaoping Xing:
Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets. 46 - 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. 47 - Jin-Yi Cai, Aaron Gorenstein:
Matchgates Revisited. 48 - Amir Shpilka, Ben lee Volk:
On the Structure of Boolean Functions with Small Spectral Norm. 49 - Venkatesan Guruswami, Patrick Xia:
Polar Codes: Speed of polarization and polynomial gap to capacity. 50 - Eric Blais, Li-Yang Tan:
Approximating Boolean functions with depth-2 circuits. 51 - Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh:
Upper Bounds on Fourier Entropy. 52 - Alan Guo:
High rate locally correctable codes via lifting. 53 - Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook:
Average Case Lower Bounds for Monotone Switching Networks. 54 - David Gamarnik, Madhu Sudan:
Limits of local algorithms over sparse random graphs. 55 - Gábor Braun, Sebastian Pokutta:
Common information and unique disjointness. 56 - Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman:
Mining Circuit Lower Bound Proofs for Meta-Algorithms. 57 - Ilan Komargodski, Ran Raz, Avishay Tal:
Improved Average-Case Lower Bounds for DeMorgan Formula Size. 58 - Lior Gishboliner, Asaf Shapira:
Deterministic vs Non-deterministic Graph Property Testing. 59 - Venkatesan Guruswami, Swastik Kopparty:
Explicit Subspace Designs. 60 - Zeev Dvir, Guangda Hu:
Matching-Vector Families and LDCs Over Large Modulo. 61 - Deeparnab Chakrabarty, C. Seshadhri:
An optimal lower bound for monotonicity testing over hypergrids. 62 - Dung T. Nguyen, Alan L. Selman:
Non-autoreducible Sets for NEXP. 63 - Anat Ganor, Ran Raz:
Space Pseudorandom Generators by Communication Complexity Lower Bounds. 64 - Yijia Chen, Jörg Flum:
On Limitations of the Ehrenfeucht-Fraisse-method in Descriptive Complexity. 65 - Marek Karpinski, Richard Schmied:
Approximation Hardness of Graphic TSP on Cubic Graphs. 66 - Oded Goldreich:
On Multiple Input Problems in Property Testing. 67 - Mrinal Kumar, Shubhangi Saraf:
Lower Bounds for Depth 4 Homogenous Circuits with Bounded Top Fanin. 68 - Kousha Etessami, Alistair Stewart, Mihalis Yannakakis:
A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing. 69 - Iddo Tzameret:
On Sparser Random 3SAT Refutation Algorithms and Feasible Interpolation. 70 - Venkatesan Guruswami, Sushant Sachdeva, Rishi Saket:
Inapproximability of Minimum Vertex Cover on k-uniform k-partite Hypergraphs. 71 - Jan Johannsen:
Exponential Separations in a Hierarchy of Clause Learning Proof Systems. 72 - Oded Goldreich:
On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing. 73 - Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky:
Helly Circular-Arc Graph Isomorphism is in Logspace. 74 - Subhash Khot, Madhur Tulsiani, Pratik Worah:
A Characterization of Strong Approximation Resistance. 75 - Divesh Aggarwal, Chandan K. Dubey:
Improved hardness results for unique shortest vector problem. 76 - Ján Pich:
Circuit Lower Bounds in Bounded Arithmetics. 77 - Tom Gur, Ron Rothblum:
Non-Interactive Proofs of Proximity. 78 - Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff:
Direct Sum Fails for Zero Error Average Communication. 79 - Dmitry Gavinsky, Shachar Lovett:
En Route to the log-rank Conjecture: New Reductions and Equivalent Formulations. 80 - Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett:
Non-malleable Codes from Additive Combinatorics. 81 - Eldar Fischer, Yonatan Goldhirsh, Oded Lachish:
Some properties are not even partially testable. 82 - Miklós Ajtai:
Lower Bounds for RAMs and Quantifier Elimination. 83 - Shachar Lovett:
Communication is bounded by root of rank. 84 - Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth:
Constant rate PCPs for circuit-SAT with sublinear query complexity. 85 - Omer Reingold, Thomas Steinke, Salil P. Vadhan:
Pseudorandomness for Regular Branching Programs via Fourier Analysis. 86 - Hamed Hatami, Shachar Lovett:
Estimating the distance from testable affine-invariant properties. 87 - Zachary Remscrim, Michael Sipser:
AC0 Pseudorandomness of Natural Operations. 88 - Abhishek Bhrushundi:
On testing bent functions. 89 - Elena Grigorescu, Karl Wimmer, Ning Xie:
Tight Lower Bounds for Testing Linear Isomorphism. 90 - Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi:
A super-polynomial lower bound for regular arithmetic formulas. 91 - Pavel Pudlák, Arnold Beckmann, Neil Thapen:
Parity Games and Propositional Proofs. 92 - Anna Gál, Jing-Tang Jang:
A Generalization of Spira's Theorem and Circuits with Small Segregators or Separators. 93 - Brendan Juba:
On Non-automatizability in PAC-Semantics. 94 - Uriel Feige, Rani Izsak:
Welfare Maximization and the Supermodular Degree. 95 - Dana Ron, Rocco A. Servedio:
Exponentially improved algorithms and lower bounds for testing signed majorities. 96 - Mikolás Janota, João Marques-Silva:
On Propositional QBF Expansions and Q-Resolution. 97 - Benny Applebaum, Yoni Moses:
Locally Computable UOWHF with Linear Shrinkage. 98 - Hamidreza Jahanjou, Eric Miles, Emanuele Viola:
Local reductions. 99 - Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan:
Lower bounds for depth 4 formulas computing iterated matrix multiplication. 100 - Colin Jia Zheng, Salil P. Vadhan:
A Uniform Min-Max Theorem with Applications in Cryptography. 101 - Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah:
Small Depth Proof Systems. 102 - Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha:
Generalized Wong sequences and their applications to Edmonds' problems. 103 - Parikshit Gopalan, Cheng Huang, Bob Jenkins, Sergey Yekhanin:
Explicit Maximally Recoverable Codes with Locality. 104 - Raghu Meka, Avi Wigderson:
Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique. 105 - Shay Moran, Amir Yehudayoff:
A note on average-case sorting. 106 - 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. 107 - Rahul Santhanam, Ryan Williams:
New Algorithms for QBF Satisfiability and Implications for Circuit Complexity. 108 - Oded Goldreich, Dana Ron:
On Sample-Based Testers. 109 - Xiaoming Sun, Marcos Villagra:
Exponential Quantum-Classical Gaps in Multiparty Nondeterministic Communication Complexity. 110 - Gregory Valiant, Paul Valiant:
Instance-by-instance optimal identity testing. 111 - Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf:
Exact Perfect Matching in Complete Graphs. 112 - Moritz Müller, Stefan Szeider:
Revisiting Space in Proof Complexity: Treewidth and Pathwidth. 113 - Parikshit Gopalan, Salil P. Vadhan, Yuan Zhou:
Locally Testable Codes and Cayley Graphs. 114 - Daniele Micciancio:
Locally Dense Codes. 115 - Albert Atserias, Moritz Müller, Sergi Oliva:
Lower Bounds for DNF-Refutations of a Relativized Weak Pigeonhole Principle. 116 - Igor Oliveira:
Algorithms versus Circuit Lower Bounds. 117 - Mahdi Cheraghchi, Venkatesan Guruswami:
Capacity of Non-Malleable Codes. 118 - Emanuele Viola:
Challenges in computational lower bounds. 119 - Zeyu Guo:
Randomness-efficient Curve Samplers. 120 - Mahdi Cheraghchi, Venkatesan Guruswami:
Non-Malleable Coding Against Bit-wise and Split-State Tampering. 121 - Irit Dinur, Venkatesan Guruswami:
PCPs via low-degree long code and hardness for constrained hypergraph coloring. 122 - Joshua A. Grochow, Youming Qiao:
Algorithms for group isomorphism via group extensions and cohomology. 123 - Thomas Watson:
The Complexity of Deciding Statistical Properties of Samplable Distributions. 124 - Venkatesan Guruswami, Euiwoong Lee:
Complexity of approximating CSP with Balance / Hard Constraints. 125 - Arman Fazeli, Shachar Lovett, Alexander Vardy:
Nontrivial t-designs over finite fields exist for all t. 126 - Paul Beame, Raphaël Clifford, Widad Machmouchi:
Element Distinctness, Frequency Moments, and Sliding Windows. 127 - Pavel Hrubes:
A note on semantic cutting planes. 128 - Adam R. Klivans, Pravesh Kothari, Igor Carboni Oliveira:
Constructing Hard Functions from Learning Algorithms. 129 - Mark Braverman, Ankit Garg:
Public vs private coin in bounded-round information. 130 - Nikhil Balaji, Samir Datta:
Collapsing Exact Arithmetic Hierarchies. 131 - Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka:
Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order. 132 - Cassio P. de Campos, Georgios Stamoulis, Dennis Weyland:
A Structured View on Weighted Counting with Relations to Quantum Computation and Applications. 133 - Or Meir:
Combinatorial PCPs with Short Proofs. 134 - Scott Aaronson:
BosonSampling Is Far From Uniform. 135 - Paul W. Goldberg, Aaron Roth:
Bounds for the Query Complexity of Approximate Equilibria. 136 - Mohammad Mahmoody, Hemanta K. Maji, Manoj Prabhakaran:
On the Power of Public-key Encryption in Secure Computation. 137 - Itai Benjamini, Gil Cohen, Igor Shinkar:
Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball. 138 - Peter Floderus, Andrzej Lingas, Mia Persson, Dzmitry Sledneu:
Detecting Monomials with k Distinct Variables. 139 - Atri Rudra, Mary Wootters:
Every list-decodable code for high noise has abundant near-optimal rate puncturings. 140 - Leonid Gurvits:
Boolean matrices with prescribed row/column sums and stable homogeneous polynomials: combinatorial and algorithmic applications. 141 - Abhishek Bhrushundi, Sourav Chakraborty, Raghav Kulkarni:
Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees. 142 - Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, David Zuckerman:
Robust Pseudorandom Generators. 143