Volume 18, 2011
- Scott Aaronson:
Impossibility of Succinct Quantum Proofs for Collision-Freeness.
1
- Gil Cohen, Amir Shpilka, Avishay Tal:
On the Degree of Univariate Polynomials Over the Integers.
2
- Yehuda Lindell:
Constant-Round Zero-Knowledge Proofs of Knowledge.
3
- Oded Goldreich, Salil P. Vadhan:
On the complexity of computational problems regarding distributions (a survey).
4
- Madhu Sudan:
Testing Linear Properties: Some general themes.
5
- Sebastian Müller, Iddo Tzameret:
Average-Case Separation in Proof Complexity: Short Propositional Refutations for Random 3CNF Formulas.
6
- Benny Applebaum:
Pseudorandom Generators with Long Stretch and Low locality from Random Local One-Way Functions.
7
- Scott Aaronson, Andrew Drucker:
Advice Coins for Classical and Quantum Computation.
8
- Samir Datta, Gautam Prakriya:
Planarity Testing Revisited.
9
- Boris Alexeev, Michael A. Forbes, Jacob Tsimerman:
Tensor Rank: Some Lower and Upper Bounds.
10
- Ming Lam Leung, Yang Li, Shengyu Zhang:
Tight bounds on the randomized communication complexity of symmetric XOR functions in one-way and SMP models.
11
- Andrej Bogdanov, Alon Rosen:
Input locality and hardness amplification.
12
- Ronitt Rubinfeld, Asaf Shapira:
Sublinear Time Algorithms.
13
- Antoine Taveneaux:
Towards an axiomatic system for Kolmogorov complexity.
14
- Marcel R. Ackermann, Johannes Blömer, Christoph Scholz:
Hardness and Non-Approximability of Bregman Clustering Problems.
15
- Sergei Artemenko, Ronen Shaltiel:
Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification.
16
- Fengming Wang:
NEXP does not have non-uniform quasi-polynomial-size ACC circuits of o(loglog n) depth.
17
- Jochen Messner, Thomas Thierauf:
A Kolmogorov Complexity Proof of the Lovász Local Lemma for Satisfiability.
18
- Valentin E. Brimkov, Andrew Leach, Jimmy Wu, Michael Mastroianni:
On the Approximability of a Geometric Set Cover Problem.
19
- Yijia Chen, Jörg Flum:
Listings and logics.
20
- Chandan Saha, Ramprasad Saptharishi, Nitin Saxena:
A Case of Depth-3 Identity Testing, Sparse Factorization and Duality.
21
- Malte Beecken, Johannes Mittmann, Nitin Saxena:
Algebraic Independence and Blackbox Identity Testing.
22
- Oded Goldreich, Or Meir:
Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly.
23
- Rahul Jain:
New strong direct product results in communication complexity.
24
- Yang Li:
Monotone Rank and Separations in Computational Complexity.
25
- Evgeny Demenkov, Alexander S. Kulikov:
An Elementary Proof of 3n-o(n) Lower Bound on the Circuit Complexity of Affine Dispersers.
26
- Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar:
Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant.
27
- Richard Beigel, Bin Fu:
A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing.
28
- Hamed Hatami, Shachar Lovett:
Correlation testing for affine invariant properties on Fpn in the high error regime.
29
- Anna Gál, Andrew Mills:
Three Query Locally Decodable Codes with Higher Correctness Require Exponential Length.
30
- Sam Buss, Ryan Williams:
Limits on Alternation-Trading Proofs for Time-Space Lower Bounds.
31
- Fabian Wagner:
Graphs of Bounded Treewidth can be Canonized in AC1.
32
- Rahul Jain, Shengyu Zhang:
The influence lower bound via query elimination.
33
- Pavol Duris, Marek Kosta:
Flip-Pushdown Automata with k Pushdown Reversals and E0L Systems are Incomparable.
34
- Christoph Behle, Andreas Krebs, Stephanie Reifferscheid:
Typed Monoids - An Eilenberg-like Theorem for non regular Languages.
35
- Gilad Asharov, Yehuda Lindell:
A Full Proof of the BGW Protocol for Perfectly-Secure Multiparty Computation.
36
- Anindya De, Thomas Watson:
Extractors and Lower Bounds for Locally Samplable Sources.
37
- Jiapeng Zhang:
On the query complexity for Showing Dense Model.
38
- Frederic Green, Daniel Kreymer, Emanuele Viola:
In Brute-Force Search of Correlation Bounds for Polynomials.
39
- Alexander A. Sherstov:
Strong Direct Product Theorems for Quantum Communication and Query Complexity.
40
- Dana Ron, Gilad Tsur:
Testing Computability by Width-Two OBDDs.
41
- Ankur Moitra:
Efficiently Coding for Interactive Communication.
42
- Scott Aaronson:
A Linear-Optical Proof that the Permanent is #P-Hard.
43
- Shubhangi Saraf, Sergey Yekhanin:
Noisy Interpolation of Sparse Polynomials, and Applications.
44
- Eric Blais, Joshua Brody, Kevin Matulef:
Property Testing Lower Bounds via Communication Complexity.
45
- Shubhangi Saraf, Ilya Volkovich:
Black-Box Identity Testing of Depth-4 Multilinear Circuits.
46
- Oded Goldreich:
Two Comments on Targeted Canonical Derandomizers.
47
- Arkadev Chattopadhyay, Shachar Lovett:
Linear systems over abelian groups.
48
- Noga Alon, Shachar Lovett:
Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions.
49
- Claus-Peter Schnorr:
Accelerated Slide- and LLL-Reduction.
50
- Thomas Vidick:
A concentration inequality for the overlap of a vector on a large set, With application to the communication complexity of the Gap-Hamming-Distance problem.
51
- Fabian Wagner:
On the Complexity of Group Isomorphism.
52
- Krzysztof Fleszar, Christian Glaßer, Fabian Lipp, Christian Reitwießner, Maximilian Witek:
The Complexity of Solving Multiobjective Optimization Problems and its Relation to Multivalued Functions.
53
- Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka:
Tight lower bounds for 2-query LCCs over finite fields.
54
- Irit Dinur, Tali Kaufman:
Dense locally testable codes cannot have constant rate and distance.
55
- Emanuele Viola:
Extractors for circuit sources.
56
- Madhav Jha, Sofya Raskhodnikova:
Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy.
57
- Michael Viderman:
Linear time decoding of regular expander codes.
58
- Elad Haramaty, Amir Shpilka, Madhu Sudan:
Optimal testing of multivariate polynomials over small prime fields.
59
- Brady Garvin, Derrick Stolee, Raghunath Tewari, N. V. Vinodchandran:
ReachFewL = ReachUL.
60
- Neeraj Kayal:
Affine projections of polynomials.
61
- Amit Chakrabarti, Graham Cormode, Andrew McGregor:
Robust Lower Bounds for Communication and Stream Computation.
62
- Alexander A. Sherstov:
The Communication Complexity of Gap Hamming Distance.
63
- Mark Braverman:
Towards deterministic tree code constructions.
64
- Boaz Barak, Prasad Raghavendra, David Steurer:
Rounding Semidefinite Programming Hierarchies via Global Correlation.
65
- Venkatesan Guruswami, Ali Kemal Sinop:
Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives.
66
- Noga Alon, Amir Shpilka, Christopher Umans:
On Sunflowers and Matrix Multiplication.
67
- L. Elisa Celis, Omer Reingold, Gil Segev, Udi Wieder:
Balls and Bins: Smaller Hash Families and Faster Evaluation.
68
- Marius Zimand:
On the optimal compression of sets in PSPACE.
69
- Eli Ben-Sasson, Michael Viderman:
Composition of semi-LTCs by two-wise Tensor Products.
70
- Serge Gaspers, Stefan Szeider:
The Parameterized Complexity of Local Consistency.
71
- Danny Hermelin, Xi Wu:
Weak Compositions and Their Applications to Polynomial Lower-Bounds for Kernelization.
72
- Andrew Drucker:
Efficient Probabilistically Checkable Debates.
73
- Ludwig Staiger:
Exact constructive dimension.
74
- Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira:
Testing Odd-Cycle-Freeness in Boolean Functions.
75
- Eric Miles, Emanuele Viola:
The Advanced Encryption Standard, Candidate Pseudorandom Functions, and Natural Proofs.
76
- Albert Atserias, Elitza N. Maneva:
Graph Isomorphism, Sherali-Adams Relaxations and Expressibility in Counting Logics.
77
- Dana Ron, Gilad Tsur:
On Approximating the Number of Relevant Variables in a Function.
78
- Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan:
On Sums of Locally Testable Affine Invariant Properties.
79
- Mohammad Iftekhar Husain, Steven Y. Ko, Atri Rudra, Steve Uurtamo:
Storage Enforcement with Kolmogorov Complexity and List Decoding.
80
- Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar:
Erdos-Renyi Sequences and Deterministic construction of Expanding Cayley Graphs.
81
- Miklós Ajtai:
Secure Computation with Information Leaking to an Adversary.
82
- Eric Allender, Fengming Wang:
On the power of algebraic branching programs of width two.
83
- Madhur Tulsiani, Julia Wolf:
Quadratic Goldreich-Levin Theorems.
84
- Yijia Chen, Jörg Flum, Moritz Müller:
Hard instances of algorithms and proof systems.
85
- Masaki Yamamoto:
A tighter lower bound on the circuit size of the hardest Boolean functions.
86
- Michael Viderman:
A Combination of Testability and Decodability by Tensor Products.
87
- Pavel Hrubes:
How much commutativity is needed to prove polynomial identities?
88
- Paul Valiant:
Distribution Free Evolvability of Polynomial Functions over all Convex Loss Functions.
89
- Mahdi Cheraghchi, Adam Klivans, Pravesh Kothari, Homin K. Lee:
Submodular Functions Are Noise Stable.
90
- Edward A. Hirsch, Dmitry Itsykson, Valeria Nikolaenko, Alexander Smal:
Optimal heuristic algorithms for the image of an injective function.
91
- Benjamin Doerr, Carola Winzen:
Memory-Restricted Black-Box Complexity.
92
- Pinyan Lu:
Complexity Dichotomies of Counting Problems.
93
- Shachar Lovett:
Computing polynomials with few multiplications.
94
- Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie:
Low uniform versions of NC1.
95
- Gil Cohen, Ran Raz, Gil Segev:
Non-Malleable Extractors with Short Seeds and Applications to Privacy Amplification.
96
- Thomas Watson:
Lift-and-Project Integrality Gaps for the Traveling Salesperson Problem.
97
- Marek Karpinski, Richard Schmied, Claus Viehmann:
Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs.
98
- Anant Jindal, Gazal Kochar, Manjish Pal:
Maximum Matchings via Glauber Dynamics.
99
- Parikshit Gopalan, Cheng Huang, Huseyin Simitci, Sergey Yekhanin:
On the Locality of Codeword Symbols.
100
- Angsheng Li, Yicheng Pan, Pan Peng:
Testing Conductance in General Graphs.
101
- Miklós Ajtai:
Determinism Versus Nondeterminism with Arithmetic Tests and Computation.
102
- Yang Li:
BQP and PPAD.
103
- Or Meir:
Combinatorial PCPs with efficient verifiers.
104
- Graham Cormode, Michael Mitzenmacher, Justin Thaler:
Streaming Graph Computations with a Helpful Advisor.
105
- Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil P. Vadhan:
The Limits of Two-Party Differential Privacy.
106
- Pavol Duris:
On Computational Power of Partially Blind Automata.
107
- Scott Aaronson:
Why Philosophers Should Care About Computational Complexity.
108
- Zvika Brakerski, Vinod Vaikuntanathan:
Efficient Fully Homomorphic Encryption from (Standard) LWE.
109
- Alessandro Chiesa, Michael A. Forbes:
Improved Soundness for QMA with Multiple Provers.
110
- Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan:
Fully Homomorphic Encryption without Bootstrapping.
111
- Dana Moshkovitz:
The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover.
112
- Emanuele Viola:
Reducing 3XOR to listing triangles, an exposition.
113
- Varun Kanade:
Computational Bottlenecks for Evolvability.
114
- Varun Kanade, Thomas Steinke:
Learning Hurdles for Sleeping Experts.
115
- Andris Ambainis, Xiaoming Sun:
New separation between s(f) and bs(f).
116
- Andrej Bogdanov, Periklis A. Papakonstantinou, Andrew Wan:
Pseudorandomness for read-once formulas.
117
- Brett Hemenway, Rafail Ostrovsky, Martin Strauss, Mary Wootters:
Public Key Locally Decodable Codes with Short Keys.
118
- Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi:
2log1-έn Hardness for Closest Vector Problem with Preprocessing.
119
- Thomas Watson:
Advice Lower Bounds for the Dense Model Theorem.
120
- Oded Goldreich, Rani Izsak:
Monotone Circuits: One-Way Functions versus Pseudorandom Generators.
121
- Gillat Kol, Ran Raz:
Competing Provers Protocols for Circuit Evaluation.
122
- Mark Braverman:
Interactive information complexity.
123
- Nader H. Bshouty, Hanna Mazzawi:
Algorithms for the Coin Weighing Problems with the Presence of Noise.
124
- Andrew Drucker:
Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators.
125
- Benny Applebaum, Andrej Bogdanov, Alon Rosen:
A Dichotomy for Local Small-Bias Generators.
126
- Ronen Shaltiel:
Dispersers for affine sources with sub-polynomial entropy.
127
- Michael Elberfeld, Andreas Jakoby, Till Tantau:
Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth.
128
- Eli Ben-Sasson, Ariel Gabizon:
Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic.
129
- Sergei A. Lozhkin, Alexander E. Shiganov:
On a Modification of Lupanov's Method with More Uniform Distribution of Fan-out.
130
- Rahul Santhanam, Srikanth Srinivasan:
On the Limits of Sparsification.
131
- Ludwig Staiger:
Oscillation-free Chaitin h-random sequences.
132
- Maurice J. Jansen, Rahul Santhanam:
Marginal Hitting Sets Imply Super-Polynomial Lower Bounds for Permanent.
133
- Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff:
Separating multilinear branching programs and formulas.
134
- Maurice J. Jansen, Rahul Santhanam:
Stronger Lower Bounds and Randomness-Hardness Tradeoffs using Associated Algebraic Complexity Classes.
135
- Eran Gat, Shafi Goldwasser:
Probabilistic Search Algorithms with Unique Answers and Their Cryptographic Applications.
136
- Vikraman Arvind, Yadu Vasudev:
Isomorphism Testing of Boolean Functions Computable by Constant Depth Circuits.
137
- Guy Moshkovitz:
Complexity Lower Bounds through Balanced Graph Properties.
138
- Zeev Dvir, Shachar Lovett:
Subspace Evasive Sets.
139
- Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar, Yadu Vasudev:
Expanding Generator Sets for Solvable Permutation Groups.
140
- Salil P. Vadhan, Colin Jia Zheng:
Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions.
141
- Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer:
Making the long code shorter, with applications to the Unique Games Conjecture.
142
- Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena:
Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits.
143
- Greg Kuperberg, Shachar Lovett, Ron Peled:
Probabilistic existence of rigid combinatorial structures.
144
- Alexander A. Sherstov:
The Multiparty Communication Complexity of Set Disjointness.
145
- Bireswar Das, Manjish Pal, Vijay Visavaliya:
The Entropy Influence Conjecture Revisited.
146
- Michael A. Forbes, Amir Shpilka:
On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing.
147
- Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf:
Planarizing Gadgets for Perfect Matching do not Exist.
148
- Paul Beame, Chris Beck, Russell Impagliazzo:
Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space.
149
- Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, Emanuele Viola:
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates.
150
- Valentine Kabanets, Osamu Watanabe:
Is the Valiant-Vazirani Isolation Lemma Improvable?
151
- Emanuele Viola:
The communication complexity of addition.
152
- Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam:
Reconstruction of Depth-4 Multilinear Circuits with Top fanin 2.
153
- Klim Efremenko:
From Irreducible Representations to Locally Decodable Codes.
154
- Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen:
The NOF Multiparty Communication Complexity of Composed Functions.
155
- Marek Karpinski, Richard Schmied:
Improved Lower Bounds for the Shortest Superstring and Related Problems.
156
- Eli Ben-Sasson, Shachar Lovett, Noga Zewi:
An additive combinatorics approach to the log-rank conjecture in communication complexity.
157
- Matthew Anderson, Dieter van Melkebeek, Nicole Schweikardt, Luc Segoufin:
Locality from Circuit Lower Bounds.
158
- Oded Goldreich, Ron Rothblum:
Enhancements of Trapdoor Permutations.
159
- Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff:
Restriction Access.
160
- Xin Li:
Design Extractors, Non-Malleable Condensers and Privacy Amplification.
161
- Pavel Pudlák:
A lower bound on the size of resolution proofs of the Ramsey theorem.
162
- Libor Barto, Marcin Kozik:
Robust Satisfiability of Constraint Satisfaction Problems.
163
- Mark Braverman, Omri Weinstein:
A discrepancy lower bound for information complexity.
164
- Elena Grigorescu, Chris Peikert:
List Decoding Barnes-Wall Lattices.
165
- Xin Li:
Non-Malleable Extractors for Entropy Rate <1/2.
166
- Nikolay K. Vereshchagin:
Improving on Gutfreund, Shaltiel, and Ta-Shma's paper "If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances".
167
- Joshua A. Grochow:
Lie algebra conjugacy.
168
- Leonid Gurvits:
Unleashing the power of Schrijver's permanental inequality with the help of the Bethe Approximation.
169
- Constantinos Daskalakis, S. Matthew Weinberg:
On Optimal Multi-Dimensional Mechanism Design.
170
- Piotr Indyk, Reut Levi, Ronitt Rubinfeld:
Approximating and Testing k-Histogram Distributions in Sub-linear time.
171
- Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg:
An Algorithmic Characterization of Multi-Dimensional Mechanisms.
172
- Christoph Behle, Andreas Krebs:
Regular Languages in MAJ[>] with three variables.
173
- Pavel Hrubes, Iddo Tzameret:
Short Proofs for the Determinant Identities.
174
Last update Thu May 23 18:43:02 2013
CET by the DBLP Team — 
Data released under the ODC-BY 1.0 license — See also our legal information page
