Google
Google Scholar
MS Academic
CiteSeerX
CORE
Semantic ScholarElectronic Colloquium on Computational Complexity, Volume 20
Volume 20, 2013
- Bruno Bauwens, Anton Makhlin, Nikolay K. Vereshchagin, Marius Zimand:
Short lists with short programs in short time. 7 - Yang Liu, Shengyu Zhang:
Quantum and randomized communication complexity of XOR functions in the SMP model. 10 - Daniel Apon, Jonathan Katz, Alex J. Malozemoff:
One-Round Multi-Party Communication Complexity of Distinguishing Sums. 13 - Iordanis Kerenidis, Mathieu Laurière, David Xiao:
New lower bounds for privacy in communication protocols. 15 - Luke Friedman, Yixin Xu:
Exponential Lower Bounds for Refuting Random Formulas Using Ordered Binary Decision Diagrams. 18 - Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii:
Polynomial threshold functions and Boolean threshold circuits. 21 - 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 - Deeparnab Chakrabarty, C. Seshadhri:
A o(n) monotonicity tester for Boolean functions over the hypercube. 29 - 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 - 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 - Massimo Lauria, Pavel Pudlák, Vojtech Rödl, Neil Thapen:
The complexity of proving that a graph is Ramsey. 38 - 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 - 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 - Venkatesan Guruswami, Patrick Xia:
Polar Codes: Speed of polarization and polynomial gap to capacity. 50 - Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh:
Upper Bounds on Fourier Entropy. 52 - Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook:
Average Case Lower Bounds for Monotone Switching Networks. 54 - 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 - Deeparnab Chakrabarty, C. Seshadhri:
An optimal lower bound for monotonicity testing over hypergrids. 62 - Yijia Chen, Jörg Flum:
On Limitations of the Ehrenfeucht-Fraisse-method in Descriptive Complexity. 65 - 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 - Venkatesan Guruswami, Sushant Sachdeva, Rishi Saket:
Inapproximability of Minimum Vertex Cover on k-uniform k-partite Hypergraphs. 71 - 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 - 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 - 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 - Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi:
A super-polynomial lower bound for regular arithmetic formulas. 91 - Anna Gál, Jing-Tang Jang:
A Generalization of Spira's Theorem and Circuits with Small Segregators or Separators. 93 - Dana Ron, Rocco A. Servedio:
Exponentially improved algorithms and lower bounds for testing signed majorities. 96 - Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan:
Lower bounds for depth 4 formulas computing iterated matrix multiplication. 100 - 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 - 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 - Xiaoming Sun, Marcos Villagra:
Exponential Quantum-Classical Gaps in Multiparty Nondeterministic Communication Complexity. 110 - Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf:
Exact Perfect Matching in Complete Graphs. 112 - Albert Atserias, Moritz Müller, Sergi Oliva:
Lower Bounds for DNF-Refutations of a Relativized Weak Pigeonhole Principle. 116 - 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 - 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 - Adam R. Klivans, Pravesh Kothari, Igor Carboni Oliveira:
Constructing Hard Functions from Learning Algorithms. 129 - Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka:
Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order. 132 - Cassio Polpo de Campos, Georgios Stamoulis, Dennis Weyland:
A Structured View on Weighted Counting with Relations to Quantum Computation and Applications. 133 - 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