All reports in year 2011:

__
TR11-001
| 2nd January 2011
__

Scott Aaronson#### Impossibility of Succinct Quantum Proofs for Collision-Freeness

__
TR11-002
| 9th January 2011
__

Gil Cohen, Amir Shpilka, Avishay Tal#### On the Degree of Univariate Polynomials Over the Integers

__
TR11-003
| 10th January 2011
__

Yehuda Lindell#### Constant-Round Zero-Knowledge Proofs of Knowledge

Revisions: 1

__
TR11-004
| 10th January 2011
__

Oded Goldreich, Salil Vadhan#### On the complexity of computational problems regarding distributions (a survey)

Comments: 1

__
TR11-005
| 20th January 2011
__

Madhu Sudan#### Testing Linear Properties: Some general themes

Revisions: 1

__
TR11-006
| 20th January 2011
__

Sebastian Müller, Iddo Tzameret#### Average-Case Separation in Proof Complexity: Short Propositional Refutations for Random 3CNF Formulas

Revisions: 1

__
TR11-007
| 17th January 2011
__

Benny Applebaum#### Pseudorandom Generators with Long Stretch and Low locality from Random Local One-Way Functions

Revisions: 3

__
TR11-008
| 27th January 2011
__

Scott Aaronson, Andrew Drucker#### Advice Coins for Classical and Quantum Computation

__
TR11-009
| 21st January 2011
__

Samir Datta, Gautam Prakriya#### Planarity Testing Revisited

__
TR11-010
| 1st February 2011
__

Boris Alexeev, Michael Forbes, Jacob Tsimerman#### Tensor Rank: Some Lower and Upper Bounds

__
TR11-011
| 1st February 2011
__

Ming Lam Leung, Yang Li, Shengyu Zhang#### Tight bounds on the randomized communication complexity of symmetric XOR functions in one-way and SMP models

__
TR11-012
| 2nd February 2011
__

Andrej Bogdanov, Alon Rosen#### Input locality and hardness amplification

__
TR11-013
| 3rd February 2011
__

Ronitt Rubinfeld, Asaf Shapira#### Sublinear Time Algorithms

__
TR11-014
| 3rd February 2011
__

Antoine Taveneaux#### Towards an axiomatic system for Kolmogorov complexity

Revisions: 1

__
TR11-015
| 8th December 2010
__

Marcel R. Ackermann, Johannes Blömer, Christoph Scholz#### Hardness and Non-Approximability of Bregman Clustering Problems

__
TR11-016
| 7th February 2011
__

Sergei Artemenko, Ronen Shaltiel#### Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification

Revisions: 1

__
TR11-017
| 8th February 2011
__

Fengming Wang#### NEXP does not have non-uniform quasi-polynomial-size ACC circuits of o(loglog n) depth

__
TR11-018
| 8th February 2011
__

Jochen Messner, Thomas Thierauf#### A Kolmogorov Complexity Proof of the Lovász Local Lemma for Satisfiability

__
TR11-019
| 5th February 2011
__

Valentin Brimkov, Andrew Leach, Jimmy Wu, Michael Mastroianni#### On the Approximability of a Geometric Set Cover Problem

__
TR11-020
| 20th December 2010
__

Yijia Chen, Joerg Flum#### Listings and logics

__
TR11-021
| 13th February 2011
__

Chandan Saha, Ramprasad Saptharishi, Nitin Saxena#### A Case of Depth-3 Identity Testing, Sparse Factorization and Duality

__
TR11-022
| 14th February 2011
__

Malte Beecken, Johannes Mittmann, Nitin Saxena#### Algebraic Independence and Blackbox Identity Testing

__
TR11-023
| 16th February 2011
__

Oded Goldreich, Or Meir#### Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly

Revisions: 5
,
Comments: 2

__
TR11-024
| 25th February 2011
__

Rahul Jain#### New strong direct product results in communication complexity

__
TR11-025
| 19th February 2011
__

Yang Li#### Monotone Rank and Separations in Computational Complexity

Revisions: 1
,
Comments: 1

__
TR11-026
| 27th February 2011
__

Evgeny Demenkov, Alexander Kulikov#### An Elementary Proof of $3n-o(n)$ Lower Bound on the Circuit Complexity of Affine Dispersers

__
TR11-027
| 28th February 2011
__

Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar#### Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant

__
TR11-028
| 24th February 2011
__

Richard Beigel, Bin Fu#### A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing

__
TR11-029
| 6th March 2011
__

Hamed Hatami, Shachar Lovett#### Correlation testing for affine invariant properties on $\mathbb{F}_p^n$ in the high error regime

Revisions: 1

__
TR11-030
| 9th March 2011
__

Anna Gal, Andrew Mills#### Three Query Locally Decodable Codes with Higher Correctness Require Exponential Length

__
TR11-031
| 8th March 2011
__

Sam Buss, Ryan Williams#### Limits on Alternation-Trading Proofs for Time-Space Lower Bounds

__
TR11-032
| 11th March 2011
__

Fabian Wagner#### Graphs of Bounded Treewidth can be Canonized in AC$^1$

__
TR11-033
| 8th March 2011
__

Rahul Jain, Shengyu Zhang#### The influence lower bound via query elimination

__
TR11-034
| 20th January 2011
__

Pavol Duris, Marek Kosta#### Flip-Pushdown Automata with k Pushdown Reversals and E0L Systems are Incomparable

__
TR11-035
| 4th March 2011
__

Christoph Behle, Andreas Krebs, Stephanie Reifferscheid#### Typed Monoids -- An Eilenberg-like Theorem for non regular Languages

__
TR11-036
| 17th March 2011
__

Gilad Asharov, Yehuda Lindell#### A Full Proof of the BGW Protocol for Perfectly-Secure Multiparty Computation

Revisions: 5

__
TR11-037
| 18th March 2011
__

Anindya De, Thomas Watson#### Extractors and Lower Bounds for Locally Samplable Sources

Revisions: 3

__
TR11-038
| 10th March 2011
__

Jiapeng Zhang#### On the query complexity for Showing Dense Model

__
TR11-039
| 19th March 2011
__

Frederic Green, Daniel Kreymer, Emanuele Viola#### In Brute-Force Search of Correlation Bounds for Polynomials

__
TR11-040
| 22nd March 2011
__

Alexander A. Sherstov#### Strong Direct Product Theorems for Quantum Communication and Query Complexity

__
TR11-041
| 24th March 2011
__

Dana Ron, Gilad Tsur#### Testing Computability by Width-Two OBDDs

__
TR11-042
| 25th March 2011
__

Ankur Moitra#### Efficiently Coding for Interactive Communication

Revisions: 1

__
TR11-043
| 25th March 2011
__

Scott Aaronson#### A Linear-Optical Proof that the Permanent is #P-Hard

__
TR11-044
| 25th March 2011
__

Shubhangi Saraf, Sergey Yekhanin#### Noisy Interpolation of Sparse Polynomials, and Applications

__
TR11-045
| 1st April 2011
__

Eric Blais, Joshua Brody, Kevin Matulef#### Property Testing Lower Bounds via Communication Complexity

Revisions: 1

__
TR11-046
| 2nd April 2011
__

Shubhangi Saraf, Ilya Volkovich#### Black-Box Identity Testing of Depth-4 Multilinear Circuits

__
TR11-047
| 8th April 2011
__

Oded Goldreich#### Two Comments on Targeted Canonical Derandomizers

__
TR11-048
| 10th April 2011
__

Arkadev Chattopadhyay, Shachar Lovett#### Linear systems over abelian groups

__
TR11-049
| 9th April 2011
__

Noga Alon, Shachar Lovett#### Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions

__
TR11-050
| 11th April 2011
__

Claus-Peter Schnorr#### Accelerated Slide- and LLL-Reduction

Revisions: 7

__
TR11-051
| 8th April 2011
__

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

__
TR11-052
| 4th April 2011
__

Fabian Wagner#### On the Complexity of Group Isomorphism

Revisions: 4
,
Comments: 3

__
TR11-053
| 11th April 2011
__

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

__
TR11-054
| 13th April 2011
__

Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka#### Tight lower bounds for 2-query LCCs over finite fields

__
TR11-055
| 14th April 2011
__

Irit Dinur, Tali Kaufman#### Dense locally testable codes cannot have constant rate and distance

__
TR11-056
| 14th April 2011
__

Emanuele Viola#### Extractors for circuit sources

__
TR11-057
| 15th April 2011
__

Madhav Jha, Sofya Raskhodnikova#### Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy

Revisions: 2

__
TR11-058
| 15th April 2011
__

Michael Viderman#### Linear time decoding of regular expander codes

Revisions: 1

__
TR11-059
| 15th April 2011
__

Elad Haramaty, Amir Shpilka, Madhu Sudan#### Optimal testing of multivariate polynomials over small prime fields

__
TR11-060
| 15th April 2011
__

Brady Garvin, Derrick Stolee, Raghunath Tewari, N. V. Vinodchandran#### ReachFewL = ReachUL

__
TR11-061
| 18th April 2011
__

Neeraj Kayal#### Affine projections of polynomials

Revisions: 1

__
TR11-062
| 18th April 2011
__

Amit Chakrabarti, Graham Cormode, Andrew McGregor#### Robust Lower Bounds for Communication and Stream Computation

__
TR11-063
| 19th April 2011
__

Alexander A. Sherstov#### The Communication Complexity of Gap Hamming Distance

__
TR11-064
| 23rd April 2011
__

Mark Braverman#### Towards deterministic tree code constructions

__
TR11-065
| 25th April 2011
__

Boaz Barak, Prasad Raghavendra, David Steurer#### Rounding Semidefinite Programming Hierarchies via Global Correlation

__
TR11-066
| 25th April 2011
__

Venkatesan Guruswami, Ali Kemal Sinop#### Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives

Revisions: 1

__
TR11-067
| 25th April 2011
__

Noga Alon, Amir Shpilka, Chris Umans#### On Sunflowers and Matrix Multiplication

Comments: 1

__
TR11-068
| 27th April 2011
__

L. Elisa Celis, Omer Reingold, Gil Segev, Udi Wieder#### Balls and Bins: Smaller Hash Families and Faster Evaluation

__
TR11-069
| 18th April 2011
__

Marius Zimand#### On the optimal compression of sets in PSPACE

__
TR11-070
| 1st May 2011
__

Eli Ben-Sasson, Michael Viderman#### Composition of semi-LTCs by two-wise Tensor Products

__
TR11-071
| 27th April 2011
__

Serge Gaspers, Stefan Szeider#### The Parameterized Complexity of Local Consistency

Revisions: 1

__
TR11-072
| 1st May 2011
__

Danny Hermelin, Xi Wu#### Weak Compositions and Their Applications to Polynomial Lower-Bounds for Kernelization

Revisions: 1

__
TR11-073
| 3rd May 2011
__

Andrew Drucker#### Efficient Probabilistically Checkable Debates

__
TR11-074
| 27th April 2011
__

Ludwig Staiger#### Exact constructive dimension

Revisions: 1

__
TR11-075
| 6th May 2011
__

Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira#### Testing Odd-Cycle-Freeness in Boolean Functions

__
TR11-076
| 7th May 2011
__

Eric Miles, Emanuele Viola#### The Advanced Encryption Standard, Candidate Pseudorandom Functions, and Natural Proofs

Revisions: 1

__
TR11-077
| 8th May 2011
__

Albert Atserias, Elitza Maneva#### Graph Isomorphism, Sherali-Adams Relaxations and Expressibility in Counting Logics

__
TR11-078
| 9th May 2011
__

Dana Ron, Gilad Tsur#### On Approximating the Number of Relevant Variables in a Function

__
TR11-079
| 9th May 2011
__

Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan#### On Sums of Locally Testable Affine Invariant Properties

__
TR11-080
| 11th May 2011
__

mohammad iftekhar husain, steve ko, Atri Rudra, steve uurtamo#### Storage Enforcement with Kolmogorov Complexity and List Decoding

__
TR11-081
| 15th May 2011
__

Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar#### Erdos-Renyi Sequences and Deterministic construction of Expanding Cayley Graphs

__
TR11-082
| 20th May 2011
__

Miklos Ajtai#### Secure Computation with Information Leaking to an Adversary

__
TR11-083
| 22nd May 2011
__

Eric Allender, Fengming Wang#### On the power of algebraic branching programs of width two

__
TR11-084
| 23rd May 2011
__

Madhur Tulsiani, Julia Wolf#### Quadratic Goldreich-Levin Theorems

__
TR11-085
| 14th May 2011
__

Yijia Chen, Joerg Flum, Moritz Müller#### Hard instances of algorithms and proof systems

__
TR11-086
| 2nd June 2011
__

Masaki Yamamoto#### A tighter lower bound on the circuit size of the hardest Boolean functions

__
TR11-087
| 3rd June 2011
__

Michael Viderman#### A Combination of Testability and Decodability by Tensor Products

Revisions: 3

__
TR11-088
| 7th June 2011
__

Pavel Hrubes#### How much commutativity is needed to prove polynomial identities?

__
TR11-089
| 7th June 2011
__

Paul Valiant#### Distribution Free Evolvability of Polynomial Functions over all Convex Loss Functions

Revisions: 1

__
TR11-090
| 2nd June 2011
__

Mahdi Cheraghchi, Adam Klivans, Pravesh Kothari, Homin Lee#### Submodular Functions Are Noise Stable

Revisions: 2

__
TR11-091
| 20th May 2011
__

Edward Hirsch, Dmitry Itsykson, Valeria Nikolaenko, Alexander Smal#### Optimal heuristic algorithms for the image of an injective function

__
TR11-092
| 2nd June 2011
__

Doerr Benjamin, Winzen Carola#### Memory-Restricted Black-Box Complexity

__
TR11-093
| 8th June 2011
__

Pinyan Lu#### Complexity Dichotomies of Counting Problems

__
TR11-094
| 20th June 2011
__

Shachar Lovett#### Computing polynomials with few multiplications

__
TR11-095
| 22nd June 2011
__

Christoph Behle, Andreas Krebs, Klaus-Joern Lange, Pierre McKenzie#### Low uniform versions of NC1

Revisions: 1

__
TR11-096
| 2nd July 2011
__

Gil Cohen, Ran Raz, Gil Segev#### Non-Malleable Extractors with Short Seeds and Applications to Privacy Amplification

__
TR11-097
| 7th July 2011
__

Thomas Watson#### Lift-and-Project Integrality Gaps for the Traveling Salesperson Problem

Revisions: 1

__
TR11-098
| 11th July 2011
__

Marek Karpinski, Richard Schmied, Claus Viehmann#### Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs

__
TR11-099
| 11th July 2011
__

Anant Jindal, Gazal Kochar, Manjish Pal#### Maximum Matchings via Glauber Dynamics

Revisions: 1
,
Comments: 1

__
TR11-100
| 20th July 2011
__

Parikshit Gopalan, Cheng Huang, Huseyin Simitci, Sergey Yekhanin#### On the Locality of Codeword Symbols

__
TR11-101
| 26th July 2011
__

Angsheng Li, Yicheng Pan, Pan Peng#### Testing Conductance in General Graphs

__
TR11-102
| 31st July 2011
__

Miklos Ajtai#### Determinism Versus Nondeterminism with Arithmetic Tests and Computation

Revisions: 1

__
TR11-103
| 31st July 2011
__

Yang Li#### BQP and PPAD

__
TR11-104
| 3rd August 2011
__

Or Meir#### Combinatorial PCPs with efficient verifiers

Revisions: 3

__
TR11-105
| 22nd July 2011
__

Graham Cormode, Michael Mitzenmacher, Justin Thaler#### Streaming Graph Computations with a Helpful Advisor

Revisions: 1

__
TR11-106
| 6th August 2011
__

Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil Vadhan#### The Limits of Two-Party Differential Privacy

__
TR11-107
| 22nd July 2011
__

Pavol Duris#### On Computational Power of Partially Blind Automata

__
TR11-108
| 8th August 2011
__

Scott Aaronson#### Why Philosophers Should Care About Computational Complexity

Revisions: 2

__
TR11-109
| 9th August 2011
__

Zvika Brakerski, Vinod Vaikuntanathan#### Efficient Fully Homomorphic Encryption from (Standard) LWE

__
TR11-110
| 10th August 2011
__

Alessandro Chiesa, Michael Forbes#### Improved Soundness for QMA with Multiple Provers

Revisions: 1

__
TR11-111
| 10th August 2011
__

Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan#### Fully Homomorphic Encryption without Bootstrapping

__
TR11-112
| 10th August 2011
__

Dana Moshkovitz#### The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover

__
TR11-113
| 11th August 2011
__

Emanuele Viola#### Reducing 3XOR to listing triangles, an exposition

__
TR11-114
| 8th August 2011
__

Varun Kanade#### Computational Bottlenecks for Evolvability

__
TR11-115
| 8th August 2011
__

Varun Kanade, Thomas Steinke#### Learning Hurdles for Sleeping Experts

__
TR11-116
| 17th August 2011
__

Andris Ambainis, Xiaoming Sun#### New separation between $s(f)$ and $bs(f)$

__
TR11-117
| 3rd September 2011
__

Andrej Bogdanov, Periklis Papakonstantinou, Andrew Wan#### Pseudorandomness for read-once formulas

__
TR11-118
| 6th September 2011
__

Brett Hemenway, Rafail Ostrovsky, Martin Strauss, Mary Wootters#### Public Key Locally Decodable Codes with Short Keys

__
TR11-119
| 4th September 2011
__

Subhash Khot, Preyas Popat, Nisheeth Vishnoi#### $2^{\log^{1-\epsilon} n}$ Hardness for Closest Vector Problem with Preprocessing

__
TR11-120
| 6th September 2011
__

Thomas Watson#### Advice Lower Bounds for the Dense Model Theorem

Revisions: 1

__
TR11-121
| 12th September 2011
__

Oded Goldreich, Rani Izsak#### Monotone Circuits: One-Way Functions versus Pseudorandom Generators

__
TR11-122
| 14th September 2011
__

Gillat Kol, Ran Raz#### Competing Provers Protocols for Circuit Evaluation

__
TR11-123
| 15th September 2011
__

Mark Braverman#### Interactive information complexity

__
TR11-124
| 15th September 2011
__

Nader Bshouty, Hanna Mazzawi#### Algorithms for the Coin Weighing Problems with the Presence of Noise

__
TR11-125
| 16th September 2011
__

Andrew Drucker#### Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators

Revisions: 1
,
Comments: 1

__
TR11-126
| 17th September 2011
__

Benny Applebaum, Andrej Bogdanov, Alon Rosen#### A Dichotomy for Local Small-Bias Generators

__
TR11-127
| 18th September 2011
__

Ronen Shaltiel#### Dispersers for affine sources with sub-polynomial entropy

__
TR11-128
| 21st September 2011
__

Michael Elberfeld, Andreas Jakoby, Till Tantau#### Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth

__
TR11-129
| 22nd September 2011
__

Eli Ben-Sasson, Ariel Gabizon#### Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic

__
TR11-130
| 25th September 2011
__

Sergei Lozhkin, Alexander Shiganov#### On a Modification of Lupanov's Method with More Uniform Distribution of Fan-out

__
TR11-131
| 29th September 2011
__

Rahul Santhanam, Srikanth Srinivasan#### On the Limits of Sparsification

__
TR11-132
| 2nd September 2011
__

Ludwig Staiger#### Oscillation-free Chaitin $h$-random sequences

Revisions: 1

__
TR11-133
| 4th October 2011
__

Maurice Jansen, Rahul Santhanam#### Marginal Hitting Sets Imply Super-Polynomial Lower Bounds for Permanent

__
TR11-134
| 9th October 2011
__

Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff#### Separating multilinear branching programs and formulas

__
TR11-135
| 9th October 2011
__

Maurice Jansen, Rahul Santhanam#### Stronger Lower Bounds and Randomness-Hardness Tradeoffs using Associated Algebraic Complexity Classes

__
TR11-136
| 12th October 2011
__

eran gat , shafi goldwasser#### Probabilistic Search Algorithms with Unique Answers and Their Cryptographic Applications

Revisions: 1

__
TR11-137
| 14th October 2011
__

Vikraman Arvind, Yadu Vasudev#### Isomorphism Testing of Boolean Functions Computable by Constant Depth Circuits

__
TR11-138
| 24th October 2011
__

Guy Moshkovitz#### Complexity Lower Bounds through Balanced Graph Properties

__
TR11-139
| 26th October 2011
__

Zeev Dvir, Shachar Lovett#### Subspace Evasive Sets

__
TR11-140
| 31st October 2011
__

Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar, Yadu Vasudev#### Expanding Generator Sets for Solvable Permutation Groups

Revisions: 1

__
TR11-141
| 2nd November 2011
__

Salil Vadhan, Colin Jia Zheng#### Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions

Revisions: 3

__
TR11-142
| 2nd November 2011
__

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

Revisions: 1

__
TR11-143
| 2nd November 2011
__

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

__
TR11-144
| 2nd November 2011
__

Greg Kuperberg, Shachar Lovett, Ron Peled#### Probabilistic existence of rigid combinatorial structures

__
TR11-145
| 2nd November 2011
__

Alexander A. Sherstov#### The Multiparty Communication Complexity of Set Disjointness

__
TR11-146
| 1st November 2011
__

Bireswar Das, Manjish Pal, Vijay Visavaliya#### The Entropy Influence Conjecture Revisited

__
TR11-147
| 2nd November 2011
__

Michael Forbes, Amir Shpilka#### On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing

__
TR11-148
| 3rd November 2011
__

Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf#### Planarizing Gadgets for Perfect Matching do not Exist

__
TR11-149
| 4th November 2011
__

Paul Beame, Chris Beck, Russell Impagliazzo#### Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space

__
TR11-150
| 4th November 2011
__

Anna Gal, Kristoffer Arnsfelt Hansen, Michal Koucky, Pavel Pudlak, Emanuele Viola#### Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates

__
TR11-151
| 9th November 2011
__

Valentine Kabanets, Osamu Watanabe#### Is the Valiant-Vazirani Isolation Lemma Improvable?

Revisions: 2

__
TR11-152
| 12th November 2011
__

Emanuele Viola#### The communication complexity of addition

__
TR11-153
| 13th November 2011
__

Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam#### Reconstruction of Depth-4 Multilinear Circuits with Top fanin 2

__
TR11-154
| 17th November 2011
__

Klim Efremenko#### From Irreducible Representations to Locally Decodable Codes

__
TR11-155
| 22nd November 2011
__

Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen#### The NOF Multiparty Communication Complexity of Composed Functions

__
TR11-156
| 23rd November 2011
__

Marek Karpinski, Richard Schmied#### Improved Lower Bounds for the Shortest Superstring and Related Problems

Revisions: 1

__
TR11-157
| 25th November 2011
__

Eli Ben-Sasson, Shachar Lovett, Noga Ron-Zewi#### An additive combinatorics approach to the log-rank conjecture in communication complexity

Revisions: 1

__
TR11-158
| 25th November 2011
__

Matthew Anderson, Dieter van Melkebeek, Nicole Schweikardt, Luc Segoufin#### Locality from Circuit Lower Bounds

__
TR11-159
| 27th November 2011
__

Oded Goldreich, Ron Rothblum#### Enhancements of Trapdoor Permutations

Revisions: 1
,
Comments: 1

__
TR11-160
| 1st December 2011
__

Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff#### Restriction Access

__
TR11-161
| 4th December 2011
__

Xin Li#### Design Extractors, Non-Malleable Condensers and Privacy Amplification

__
TR11-162
| 7th December 2011
__

Pavel Pudlak#### A lower bound on the size of resolution proofs of the Ramsey theorem

__
TR11-163
| 2nd December 2011
__

Libor Barto, Marcin Kozik#### Robust Satisfiability of Constraint Satisfaction Problems

__
TR11-164
| 9th December 2011
__

Mark Braverman, Omri Weinstein#### A discrepancy lower bound for information complexity

__
TR11-165
| 8th December 2011
__

Elena Grigorescu, Chris Peikert#### List Decoding Barnes-Wall Lattices

Revisions: 2

__
TR11-166
| 4th December 2011
__

Xin Li#### Non-Malleable Extractors for Entropy Rate $<1/2$

Revisions: 1

__
TR11-167
| 6th December 2011
__

Nikolay 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''

Revisions: 1

__
TR11-168
| 9th December 2011
__

Joshua Grochow#### Lie algebra conjugacy

__
TR11-169
| 14th December 2011
__

Leonid Gurvits#### Unleashing the power of Schrijver's permanental inequality with the help of the Bethe Approximation

Revisions: 2

__
TR11-170
| 16th December 2011
__

Constantinos Daskalakis, S. Matthew Weinberg#### On Optimal Multi-Dimensional Mechanism Design

__
TR11-171
| 15th December 2011
__

Piotr Indyk, Reut Levi, Ronitt Rubinfeld#### Approximating and Testing $k$-Histogram Distributions in Sub-linear time

Revisions: 1

__
TR11-172
| 20th December 2011
__

Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg#### An Algorithmic Characterization of Multi-Dimensional Mechanisms

__
TR11-173
| 22nd December 2011
__

Christoph Behle, Andreas Krebs#### Regular Languages in MAJ[<] with three variables

__
TR11-174
| 30th December 2011
__

Pavel Hrubes, Iddo Tzameret#### Short Proofs for the Determinant Identities

Revisions: 1

Scott Aaronson

We show that any quantum algorithm to decide whether a function $f:\left[n\right] \rightarrow\left[ n\right] $ is a permutation or far from a permutation\ must make $\Omega\left( n^{1/3}/w\right) $ queries to $f$, even if the algorithm is given a $w$-qubit quantum witness in support of $f$ being a permutation. This implies ... more >>>

Gil Cohen, Amir Shpilka, Avishay Tal

We study the following problem raised by von zur Gathen and Roche:

What is the minimal degree of a nonconstant polynomial $f:\{0,\ldots,n\}\to\{0,\ldots,m\}$?

Clearly, when $m=n$ the function $f(x)=x$ has degree $1$. We prove that when $m=n-1$ (i.e. the point $\{n\}$ is not in the range), it must be the case ... more >>>

Yehuda Lindell

In this note, we show the existence of \emph{constant-round} computational zero-knowledge \emph{proofs of knowledge} for all $\cal NP$. The existence of constant-round zero-knowledge proofs was proven by Goldreich and Kahan (Journal of Cryptology, 1996), and the existence of constant-round zero-knowledge \emph{arguments} of knowledge was proven by Feige and Shamir (CRYPTO ... more >>>

Oded Goldreich, Salil Vadhan

We consider two basic computational problems

regarding discrete probability distributions:

(1) approximating the statistical difference (aka variation distance)

between two given distributions,

and (2) approximating the entropy of a given distribution.

Both problems are considered in two different settings.

In the first setting the approximation algorithm

more >>>

Madhu Sudan

The last two decades have seen enormous progress in the development of sublinear-time algorithms --- i.e., algorithms that examine/reveal properties of ``data'' in less time than it would take to read all of the data. A large, and important, subclass of such properties turn out to be ``linear''. In particular, ... more >>>

Sebastian Müller, Iddo Tzameret

Separating different propositional proof systems---that is, demonstrating that one proof system cannot efficiently simulate another proof system---is one of the main goals of proof complexity. Nevertheless, all known separation results between non-abstract proof systems are for specific families of hard tautologies: for what we know, in the average case all ... more >>>

Benny Applebaum

We continue the study of pseudorandom generators (PRG) $G:\{0,1\}^n \rightarrow \{0,1\}^m$ in NC0. While it is known that such generators are likely to exist for the case of small sub-linear stretch $m=n+n^{1-\epsilon}$, it remains unclear whether achieving larger stretch such as $m=2n$ or even $m=n+n^2$ is possible. The existence of ... more >>>

Scott Aaronson, Andrew Drucker

We study the power of classical and quantum algorithms equipped with nonuniform advice, in the form of a coin whose bias encodes useful information. This question takes on particular importance in the quantum case, due to a surprising result that we prove: a quantum finite automaton with just two states ... more >>>

Samir Datta, Gautam Prakriya

Planarity Testing is the problem of determining whether a given graph is planar while planar embedding is the corresponding construction problem.

The bounded space complexity of these problems has been determined to be Logspace by Allender and Mahajan with the aid of Reingold's result . Unfortunately, the algorithm is quite ...
more >>>

Boris Alexeev, Michael Forbes, Jacob Tsimerman

The results of Strassen and Raz show that good enough tensor rank lower bounds have implications for algebraic circuit/formula lower bounds.

We explore tensor rank lower and upper bounds, focusing on explicit tensors. For odd d, we construct field-independent explicit 0/1 tensors T:[n]^d->F with rank at least 2n^(floor(d/2))+n-Theta(d log n). ... more >>>

Ming Lam Leung, Yang Li, Shengyu Zhang

We study the communication complexity of symmetric XOR functions, namely functions $f: \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ that can be formulated as $f(x,y)=D(|x\oplus y|)$ for some predicate $D: \{0,1,...,n\} \rightarrow \{0,1\}$, where $|x\oplus y|$ is the Hamming weight of the bitwise XOR of $x$ and $y$. We give a public-coin ... more >>>

Andrej Bogdanov, Alon Rosen

We establish new hardness amplification results for one-way functions in which each input bit influences only a small number of output bits (a.k.a. input-local functions). Our transformations differ from previous ones in that they approximately preserve input locality and at the same time retain the input size of the original ... more >>>

Ronitt Rubinfeld, Asaf Shapira

Sublinear time algorithms represent a new paradigm

in computing, where an algorithm must give some sort

of an answer after inspecting only a very small portion

of the input. We discuss the types of answers that

one can hope to achieve in this setting.

Antoine Taveneaux

In \cite{shenpapier82}, it is shown that four basic functional properties are enough to characterize plain Kolmogorov complexity, hence obtaining an axiomatic characterization of this notion. In this paper, we try to extend this work, both by looking at alternative axiomatic systems for plain complexity and by considering potential axiomatic systems ... more >>>

Marcel R. Ackermann, Johannes Blömer, Christoph Scholz

We prove the computational hardness of three k-clustering problems using an (almost) arbitrary Bregman divergence as dissimilarity measure: (a) The Bregman k-center problem, where the objective is to find a set of centers that minimizes the maximum dissimilarity of any input point towards its closest center, and (b) the Bregman ... more >>>

Sergei Artemenko, Ronen Shaltiel

Hardness amplification results show that for every function $f$ there exists a function $Amp(f)$ such that the following holds: if every circuit of size $s$ computes $f$ correctly on at most a $1-\delta$ fraction of inputs, then every circuit of size $s'$ computes $Amp(f)$ correctly on at most a $1/2+\eps$ ... more >>>

Fengming Wang

$\mbox{ACC}_m$ circuits are circuits consisting of unbounded fan-in AND, OR and MOD_m gates and unary NOT gates, where m is a fixed integer. We show that there exists a language in non-deterministic exponential time which can not be computed by any non-uniform family of $\mbox{ACC}_m$ circuits of quasi-polynomial size and ... more >>>

Jochen Messner, Thomas Thierauf

Recently, Moser and Tardos [MT10] came up with a constructive proof of the Lovász Local Lemma. In this paper, we give another constructive proof of the lemma, based on Kolmogorov complexity. Actually, we even improve the Local Lemma slightly.

Valentin Brimkov, Andrew Leach, Jimmy Wu, Michael Mastroianni

Given a finite set of straight line segments $S$ in $R^{2}$ and some $k\in N$, is there a subset $V$ of points on segments in $S$ with $\vert V \vert \leq k$ such that each segment of $S$ contains at least one point in $V$? This is a special case ... more >>>

Yijia Chen, Joerg Flum

There are standard logics DTC, TC, and LFP capturing the complexity classes L, NL, and P on ordered structures, respectively. In [Chen and Flum, 2010] we have shown that ${\rm LFP}_{\rm inv}$, the ``order-invariant least fixed-point logic LFP,'' captures P (on all finite structures) if and only if there is ... more >>>

Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

Finding an efficient solution to the general problem of polynomial identity testing (PIT) is a challenging task. In this work, we study the complexity of two special but natural cases of identity testing - first is a case of depth-$3$ PIT, the other of depth-$4$ PIT.

Our first problem is ... more >>>

Malte Beecken, Johannes Mittmann, Nitin Saxena

Algebraic independence is an advanced notion in commutative algebra that generalizes independence of linear polynomials to higher degree. Polynomials $\{f_1,\ldots, f_m\} \subset \mathbb{F}[x_1,\ldots, x_n]$ are called algebraically independent if there is no non-zero polynomial $F$ such that $F(f_1, \ldots, f_m) = 0$. The transcendence degree, $\mbox{trdeg}\{f_1,\ldots, f_m\}$, is the maximal ... more >>>

Oded Goldreich, Or Meir

We initiate a study of input-oblivious proof systems, and present a few preliminary results regarding such systems.

Our results offer a perspective on the intersection of the non-uniform complexity class P/poly with uniform complexity classes such as NP and IP.

In particular, we provide a uniform complexity formulation of the ...
more >>>

Rahul Jain

We show two new direct product results in two different models of communication complexity. Our first result is in the model of one-way public-coin model. Let $f \subseteq X \times Y \times Z $ be a relation and $\epsilon >0$ be a constant. Let $R^{1,pub}_{\epsilon}(f)$ represent the communication complexity of ... more >>>

Yang Li

In the paper, we introduce the concept of monotone rank, and using it as a powerful tool, we obtain several important and strong separation results in computational complexity.

\begin{itemize}

\item We show a super-exponential separation between monotone and non-monotone computation in the non-commutative model, and thus give the answer to ... more >>>

Evgeny Demenkov, Alexander Kulikov

A Boolean function $f \colon \mathbb{F}^n_2 \rightarrow \mathbb{F}_2$ is called an affine disperser for sources of dimension $d$, if $f$ is not constant on any affine subspace of $\mathbb{F}^n_2$ of dimension at least $d$. Recently Ben-Sasson and Kopparty gave an explicit construction of an affine disperser for $d=o(n)$. The main ... more >>>

Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar

We prove that, assuming the Unique Games Conjecture (UGC), every problem in the class of ordering constraint satisfaction problems (OCSP) where each constraint has constant arity is approximation

resistant. In other words, we show that if $\rho$ is the expected fraction of constraints satisfied by a random ordering, then obtaining ...
more >>>

Richard Beigel, Bin Fu

The bin packing problem is to find the minimum

number of bins of size one to pack a list of items with sizes

$a_1,\ldots , a_n$ in $(0,1]$. Using uniform sampling, which selects

a random element from the input list each time, we develop a

randomized $O({n(\log n)(\log\log n)\over ...
more >>>

Hamed Hatami, Shachar Lovett

Recently there has been much interest in Gowers uniformity norms from the perspective of theoretical computer science. This is mainly due to the fact that these norms provide a method for testing whether the maximum correlation of a function $f:\mathbb{F}_p^n \rightarrow \mathbb{F}_p$ with polynomials of degree at most $d \le ... more >>>

Anna Gal, Andrew Mills

Locally decodable codes

are error correcting codes with the extra property that, in order

to retrieve the correct value of just one position of the input with

high probability, it is

sufficient to read a small number of

positions of the corresponding,

possibly corrupted ...
more >>>

Sam Buss, Ryan Williams

This paper characterizes alternation trading based proofs that satisfiability is not in the time and space bounded class $\DTISP(n^c, n^\epsilon)$, for various values $c<2$ and $\epsilon<1$. We characterize exactly what can be proved in the $\epsilon=0$ case with currently known methods, and prove the conjecture of Williams that $c=2\cos(\pi/7)$ is ... more >>>

Fabian Wagner

In recent results the complexity of isomorphism testing on

graphs of bounded treewidth is improved to TC$^1$ [GV06] and further to LogCFL [DTW10].

The computation of canonical forms or a canonical labeling provides more information than

isomorphism testing.

Whether canonization is in NC or even TC$^1$ was stated ...
more >>>

Rahul Jain, Shengyu Zhang

We give a simpler proof, via query elimination, of a result due to O'Donnell, Saks, Schramm and Servedio, which shows a lower bound on the zero-error randomized query complexity of a function $f$ in terms of the maximum influence of any variable of $f$. Our lower bound also applies to ... more >>>

Pavol Duris, Marek Kosta

We prove that any propagating E0L system cannot generate the language containing all words of the form w#w. This result, together with some known ones, enable us to conclude that the flip-pushdown automata with k pushdown reversals (i.e. the pushdown automata with the ability to flip its pushdown) and E0L ... more >>>

Christoph Behle, Andreas Krebs, Stephanie Reifferscheid

Based on different concepts to obtain a finer notion of language recognition via finite monoids we develop an algebraic structure called typed monoid.

This leads to an algebraic description of regular and non regular languages.

We obtain for each language a unique minimal recognizing typed monoid, the typed syntactic monoid.

more >>>

Gilad Asharov, Yehuda Lindell

In the setting of secure multiparty computation, a set of $n$ parties with private inputs wish to jointly compute some functionality of their inputs. One of the most fundamental results of information-theoretically secure computation was presented by Ben-Or, Goldwasser and Wigderson (BGW) in 1988. They demonstrated that any $n$-party functionality ... more >>>

Anindya De, Thomas Watson

We consider the problem of extracting randomness from sources that are efficiently samplable, in the sense that each output bit of the sampler only depends on some small number $d$ of the random input bits. As our main result, we construct a deterministic extractor that, given any $d$-local source with ... more >>>

Jiapeng Zhang

A theorem of Green, Tao, and Ziegler can be stated as follows: if $R$ is a pseudorandom distribution, and $D$ is a dense distribution of $R,$ then $D$ can be modeled as a distribution $M$ which is dense in uniform distribution such that $D$ and $M$ are indistinguishable. The reduction ... more >>>

Frederic Green, Daniel Kreymer, Emanuele Viola

We report on some initial results of a brute-force search for determining the maximum correlation between degree-$d$ polynomials modulo $p$ and the $n$-bit mod $q$ function. For various settings of the parameters $n,d,p,$ and $q$, our results indicate that symmetric polynomials yield the maximum correlation. This contrasts with the previously-analyzed ... more >>>

Alexander A. Sherstov

A strong direct product theorem (SDPT) states that solving $n$ instances of a problem requires $\Omega(n)$ times the resources for a single instance, even to achieve success probability $2^{-\Omega(n)}.$ We prove that quantum communication complexity obeys an SDPT whenever the communication lower bound for a single instance is proved by ... more >>>

Dana Ron, Gilad Tsur

Property testing is concerned with deciding whether an object

(e.g. a graph or a function) has a certain property or is ``far''

(for a prespecified distance measure) from every object with

that property. In this work we consider the property of being

computable by a read-once ...
more >>>

Ankur Moitra

In 1992, Schulman proved a coding theorem for interactive communication and demonstrated that interactive communication protocols can be made robust to noise with only a constant slow-down (for a sufficiently small error rate) through a black-box reduction. However, this scheme is not computationally {\em efficient}: the running time to construct ... more >>>

Scott Aaronson

One of the crown jewels of complexity theory is Valiant's 1979 theorem that computing the permanent of an n*n matrix is #P-hard. Here we show that, by using the model of linear-optical quantum computing---and in particular, a universality theorem due to Knill, Laflamme, and Milburn---one can give a different and ... more >>>

Shubhangi Saraf, Sergey Yekhanin

Let $f\in F_q[x]$ be a polynomial of degree $d\leq q/2.$ It is well-known that $f$ can be uniquely recovered from its values at some $2d$ points even after some small fraction of the values are corrupted. In this paper we establish a similar result for sparse polynomials. We show that ... more >>>

Eric Blais, Joshua Brody, Kevin Matulef

We develop a new technique for proving lower bounds in property testing, by showing a strong connection between testing and communication complexity. We give a simple scheme for reducing communication problems to testing problems, thus allowing us to use known lower bounds in communication complexity to prove lower bounds in ... more >>>

Shubhangi Saraf, Ilya Volkovich

We study the problem of identity testing for multilinear $\Spsp(k)$ circuits, i.e. multilinear depth-$4$ circuits with fan-in $k$ at the top $+$ gate. We give the first polynomial-time deterministic

identity testing algorithm for such circuits. Our results also hold in the black-box setting.

The running time of our algorithm is ... more >>>

Oded Goldreich

We revisit the notion of a {\em targeted canonical derandomizer},

introduced in our recent ECCC Report (TR10-135) as a uniform notion of

a pseudorandom generator that suffices for yielding BPP=P.

The original notion was derived (as a variant of the standard notion

of a canonical derandomizer) by providing both ...
more >>>

Arkadev Chattopadhyay, Shachar Lovett

We consider a system of linear constraints over any finite Abelian group $G$ of the following form: $\ell_i(x_1,\ldots,x_n) \equiv \ell_{i,1}x_1+\cdots+\ell_{i,n}x_n \in A_i$ for $i=1,\ldots,t$ and each $A_i \subset G$, $\ell_{i,j}$ is an element of $G$ and $x_i$'s are Boolean variables. Our main result shows that the subset of the Boolean ... more >>>

Noga Alon, Shachar Lovett

A family of permutations in $S_n$ is $k$-wise independent if a uniform permutation chosen from the family maps any distinct $k$ elements to any distinct $k$ elements equally likely. Efficient constructions of $k$-wise independent permutations are known for $k=2$ and $k=3$, but are unknown for $k \ge 4$. In fact, ... more >>>

Claus-Peter Schnorr

Given an LLL-basis $B$ of dimension $n= hk$ we accelerate slide-reduction with blocksize $k$ to run under a reasonable assjmption in \

$\frac1{6} \, n^2 h \,\log_{1+\varepsilon} \, \alpha $ \

local SVP-computations in dimension $k$, where $\alpha \ge \frac 43$

measures the quality of the ...
more >>>

Thomas Vidick

Given two sets $A,B\subseteq\R^n$, a measure of their dependence, or correlation, is given by the expected squared inner product between random $x\in A $ and $y\in B$. We prove an inequality showing that no two sets of large enough Gaussian measure (at least $e^{-\delta n}$ for some constant $\delta >0$) ... more >>>

Fabian Wagner

The group isomorphism problem consists in deciding whether two groups $G$ and $H$

given by their multiplication tables are isomorphic.

An algorithm for group isomorphism attributed to Tarjan runs in time $n^{\log n + O(1)}$, c.f. [Mil78].

Miller and Monk showed in [Mil79] that group isomorphism can be many-one ... more >>>

Krzysztof Fleszar, Christian Glaßer, Fabian Lipp, Christian Reitwießner, Maximilian Witek

Instances of optimization problems with multiple objectives can have several optimal solutions whose cost vectors are incomparable. This ambiguity leads to several reasonable notions for solving multiobjective problems. Each such notion defines a class of multivalued functions. We systematically investigate the computational complexity of these classes.

Some solution notions S ... more >>>

Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka

A Locally Correctable Code (LCC) is an error correcting code that has a probabilistic

self-correcting algorithm that, with high probability, can correct any coordinate of the

codeword by looking at only a few other coordinates, even if a fraction $\delta$ of the

coordinates are corrupted. LCC's are a stronger form ...
more >>>

Irit Dinur, Tali Kaufman

A q-query locally testable code (LTC) is an error correcting code that can be tested by a randomized algorithm that reads at most q symbols from the given word.

An important question is whether there exist LTCs that have the ccc property: {c}onstant relative rate, {c}onstant relative distance, and that ...
more >>>

Emanuele Viola

We obtain the first deterministic extractors for sources generated (or sampled) by small circuits of bounded depth. Our main results are:

(1) We extract $k (k/nd)^{O(1)}$ bits with exponentially small error from $n$-bit sources of min-entropy $k$ that are generated by functions $f : \{0,1\}^\ell \to \{0,1\}^n$ where each output ... more >>>

Madhav Jha, Sofya Raskhodnikova

A function $f : D \to R$ has Lipschitz constant $c$ if $d_R(f(x),f(y)) \leq c\cdot d_D(x,y)$ for all $x,y$ in $D$, where $d_R$ and $d_D$ denote the distance functions on the range and domain of $f$, respectively. We say a function is Lipschitz if it has Lipschitz constant 1. (Note ... more >>>

Michael Viderman

Sipser and Spielman (IEEE IT, 1996) showed that any $(c,d)$-regular expander code with expansion parameter $> \frac{3}{4}$ is decodable in \emph{linear time} from a constant fraction of errors. Feldman et al. (IEEE IT, 2007)

proved that expansion parameter $> \frac{2}{3} + \frac{1}{3c}$ is sufficient to correct a constant fraction of ...
more >>>

Elad Haramaty, Amir Shpilka, Madhu Sudan

We consider the problem of testing if a given function $f : \F_q^n \rightarrow \F_q$ is close to a $n$-variate degree $d$ polynomial over the finite field $\F_q$ of $q$ elements. The natural, low-query, test for this property would be to pick the smallest dimension $t = t_{q,d}\approx d/q$ such ... more >>>

Brady Garvin, Derrick Stolee, Raghunath Tewari, N. V. Vinodchandran

We show that two complexity classes introduced about two decades ago are equal. ReachUL is the class of problems decided by nondeterministic log-space machines which on every input have at most one computation path from the start configuration to any other configuration. ReachFewL, a natural generalization of ReachUL, is the ... more >>>

Neeraj Kayal

An $m$-variate polynomial $f$ is said to be an affine projection of some $n$-variate polynomial $g$ if there exists an $n \times m$ matrix $A$ and an $n$-dimensional vector $b$ such that $f(x) = g(A x + b)$. In other words, if $f$ can be obtained by replacing each variable ... more >>>

Amit Chakrabarti, Graham Cormode, Andrew McGregor

We study the communication complexity of evaluating functions when the input data is randomly allocated (according to some known distribution) amongst two or more players, possibly with information overlap. This naturally extends previously studied variable partition models such as the best-case and worst-case partition models. We aim to understand whether ... more >>>

Alexander A. Sherstov

In the gap Hamming distance problem, two parties must

determine whether their respective strings $x,y\in\{0,1\}^n$

are at Hamming distance less than $n/2-\sqrt n$ or greater

than $n/2+\sqrt n.$ In a recent tour de force, Chakrabarti and

Regev (STOC '11) proved the long-conjectured $\Omega(n)$ bound

on the randomized communication ...
more >>>

Mark Braverman

We present a deterministic operator on tree codes -- we call tree code product -- that allows one to deterministically combine two tree codes into a larger tree code. Moreover, if the original tree codes are efficiently encodable and decodable, then so is their product. This allows us to give ... more >>>

Boaz Barak, Prasad Raghavendra, David Steurer

We show a new way to round vector solutions of semidefinite programming (SDP) hierarchies into integral solutions, based on a connection between these hierarchies and the spectrum of the input graph. We demonstrate the utility of our method by providing a new SDP-hierarchy based algorithm for constraint satisfaction problems with ... more >>>

Venkatesan Guruswami, Ali Kemal Sinop

We present an approximation scheme for optimizing certain Quadratic Integer Programming problems with positive semidefinite objective functions and global linear constraints. This framework includes well known graph problems such as Minimum graph bisection, Edge expansion, Uniform sparsest cut, and Small Set expansion, as well as the Unique Games problem. These ... more >>>

Noga Alon, Amir Shpilka, Chris Umans

We present several variants of the sunflower conjecture of Erd\H{o}s and Rado and discuss the relations among them.

We then show that two of these conjectures (if true) imply negative answers to questions of Coppersmith and Winograd and Cohn et al. regarding possible approaches for obtaining fast matrix multiplication algorithms. ... more >>>

L. Elisa Celis, Omer Reingold, Gil Segev, Udi Wieder

A fundamental fact in the analysis of randomized algorithm is that when $n$ balls are hashed into $n$ bins independently and uniformly at random, with high probability each bin contains at most $O(\log n / \log \log n)$ balls. In various applications, however, the assumption that a truly random hash ... more >>>

Marius Zimand

We show that if DTIME[2^{O(n)}] is not included in DSPACE}[2^{o(n)}], then, for every set B in PSPACE, all strings x in B of length n can be represented by a string compressed(x) of length at most log (|B^{=n}|) + O(log n), such that a polynomial-time algorithm, given compressed(x), can distinguish ... more >>>

Eli Ben-Sasson, Michael Viderman

In this paper we obtain a composition theorem that allows us to construct locally testable codes (LTCs) by repeated two-wise tensor products. This is the First composition theorem showing that repeating the two-wise tensor operation any constant number of times still results in a locally testable code, improving upon previous ... more >>>

Serge Gaspers, Stefan Szeider

We investigate the parameterized complexity of deciding whether a constraint network is $k$-consistent. We show that, parameterized by $k$, the problem is complete for the complexity class co-W[2]. As secondary parameters we consider the maximum domain size $d$ and the maximum number $\ell$ of constraints in which a variable occurs. ... more >>>

Danny Hermelin, Xi Wu

We introduce a new form of composition called \emph{weak composition} that allows us to obtain polynomial kernelization lower-bounds for several natural parameterized problems. Let $d \ge 2$ be some constant and let $L_1, L_2 \subseteq \{0,1\}^* \times \N$ be two parameterized problems where the unparameterized version of $L_1$ is \NP-hard. ... more >>>

Andrew Drucker

Probabilistically checkable debate systems (PCDSs) are debates between two competing provers, in which a polynomial-time verifier inspects a constant number of bits of the debate. It was shown by Condon, Feigenbaum, Lund, and Shor that every language in PSPACE has a PCDS in which the debate length is polynomially bounded. ... more >>>

Ludwig Staiger

The present paper generalises results by Lutz and Ryabko. We prove a

martingale characterisation of exact Hausdorff dimension. On this base we

introduce the notion of exact constructive dimension of (sets of) infinite

strings.

Furthermore, we generalise Ryabko's result on the Hausdorff dimension of the

...
more >>>

Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira

Call a function $f: \mathbb{F}_2^n \to \{0,1\}$ odd-cycle-free if there are no $x_1, \dots, x_k \in \mathbb{F}_2^n$ with $k$ an odd integer such that $f(x_1) = \cdots = f(x_k) = 1$ and $x_1 + \cdots + x_k = 0$. We show that one can distinguish odd-cycle-free functions from those $\epsilon$-far ... more >>>

Eric Miles, Emanuele Viola

We put forth several simple candidate pseudorandom functions f_k : {0,1}^n -> {0,1} with security (a.k.a. hardness) 2^n that are inspired by the AES block-cipher by Daemen and Rijmen (2000). The functions are computable more efficiently, and use a shorter key (a.k.a. seed) than previous

constructions. In particular, we ...
more >>>

Albert Atserias, Elitza Maneva

Two graphs with adjacency matrices $\mathbf{A}$ and $\mathbf{B}$ are isomorphic if there exists a permutation matrix $\mathbf{P}$ for which the identity $\mathbf{P}^{\mathrm{T}} \mathbf{A} \mathbf{P} = \mathbf{B}$ holds. Multiplying through by $\mathbf{P}$ and relaxing the permutation matrix to a doubly stochastic matrix leads to the notion of fractional isomorphism. We show ... more >>>

Dana Ron, Gilad Tsur

In this work we consider the problem of approximating the number of relevant variables in a function given query access to the function. Since obtaining a multiplicative factor approximation is hard in general, we consider several relaxations of the problem. In particular, we consider relaxations in which we have a ... more >>>

Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan

Affine-invariant properties are an abstract class of properties that generalize some

central algebraic ones, such as linearity and low-degree-ness, that have been

studied extensively in the context of property testing. Affine invariant properties

consider functions mapping a big field $\mathbb{F}_{q^n}$ to the subfield $\mathbb{F}_q$ and include all

properties that form ...
more >>>

mohammad iftekhar husain, steve ko, Atri Rudra, steve uurtamo

We consider the following problem that arises in outsourced storage: a user stores her data $x$ on a remote server but wants to audit the server at some later point to make sure it actually did store $x$. The goal is to design a (randomized) verification protocol that has the ... more >>>

Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar

Given a finite group $G$ by its multiplication table as input, we give a deterministic polynomial-time construction of a directed Cayley graph on $G$ with $O(\log |G|)$ generators, which has a rapid mixing property and a constant spectral expansion.\\

We prove a similar result in the undirected case, and ... more >>>

Miklos Ajtai

Assume that Alice is running a program $P$ on a RAM, and an adversary

Bob would like to get some information about the input or output of the

program. At each time, during the execution of $P$, Bob is able to see

the addresses of the memory cells involved in ...
more >>>

Eric Allender, Fengming Wang

We show that there are families of polynomials having small depth-two arithmetic circuits that cannot be expressed by algebraic branching programs of width two. This clarifies the complexity of the problem of computing the product of a sequence of two-by-two matrices, which arises in several

settings.

Madhur Tulsiani, Julia Wolf

Decomposition theorems in classical Fourier analysis enable us to express a bounded function in terms of few linear phases with large Fourier coefficients plus a part that is pseudorandom with respect to linear phases. The Goldreich-Levin algorithm can be viewed as an algorithmic analogue of such a decomposition as it ... more >>>

Yijia Chen, Joerg Flum, Moritz Müller

Assuming that the class TAUT of tautologies of propositional logic has no almost optimal algorithm, we show that every algorithm $\mathbb A$ deciding TAUT has a polynomial time computable sequence witnessing that $\mathbb A$ is not almost optimal. The result extends to every $\Pi_t^p$-complete problem with $t\ge 1$; however, we ... more >>>

Masaki Yamamoto

In [IPL2005],

Frandsen and Miltersen improved bounds on the circuit size $L(n)$ of the hardest Boolean function on $n$ input bits:

for some constant $c>0$:

\[

\left(1+\frac{\log n}{n}-\frac{c}{n}\right)

\frac{2^n}{n}

\leq

L(n)

\leq

\left(1+3\frac{\log n}{n}+\frac{c}{n}\right)

\frac{2^n}{n}.

\]

In this note,

we announce a modest ...
more >>>

Michael Viderman

Ben-Sasson and Sudan (RSA 2006) showed that repeated tensor products of linear codes with a very large distance are locally testable. Due to the requirement of a very large distance the associated tensor products could be applied only over sufficiently large fields. Then Meir (SICOMP 2009) used this result (as ... more >>>

Pavel Hrubes

Let $f$ be a non-commutative polynomial such that $f=0$ if we assume that the variables in $f$ commute. Let $Q(f)$ be the smallest $k$ such that there exist polynomials $g_1,g_1', g_2, g_2',\dots, g_k, g_k' $ with \[f\in I([g_1,g_1'], [g_2, g_2'],\dots, [g_k, g_k'] )\,,\]

where $[g,h]=gh-hg$. Then $Q(f)\leq {n\choose 2}$, where ...
more >>>

Paul Valiant

We formulate a notion of evolvability for functions with domain and range that are real-valued vectors, a compelling way of expressing many natural biological processes. We show that linear and fixed degree polynomial functions are evolvable in the following dually robust sense: There is a single evolution algorithm that for ... more >>>

Mahdi Cheraghchi, Adam Klivans, Pravesh Kothari, Homin Lee

We show that all non-negative submodular functions have high noise-stability. As a consequence, we obtain a polynomial-time learning algorithm for this class with respect to any product distribution on $\{-1,1\}^n$ (for any constant accuracy parameter $\epsilon$ ). Our algorithm also succeeds in the agnostic setting. Previous work on learning submodular ... more >>>

Edward Hirsch, Dmitry Itsykson, Valeria Nikolaenko, Alexander Smal

The existence of optimal algorithms is not known for any decision problem in NP$\setminus$P. We consider the problem of testing the membership in the image of an injective function. We construct optimal heuristic algorithms for this problem in both randomized and deterministic settings (a heuristic algorithm can err on a ... more >>>

Doerr Benjamin, Winzen Carola

We show that the black-box complexity with memory restriction one of the $n$-dimensional $\onemax$ function class is at most $2n$. This disproves the $\Theta(n \log n)$ conjecture of Droste, Jansen, and Wegener (Theory of Computing Systems 39 (2006) 525--544).

more >>>Pinyan Lu

In order to study the complexity of counting problems, several interesting frameworks have been proposed, such as Constraint Satisfaction Problems (#CSP) and Graph Homomorphisms. Recently, we proposed and explored a novel alternative framework, called Holant Problems. It is a refinement with a more explicit role for constraint functions. Both graph ... more >>>

Shachar Lovett

A folklore result in arithmetic complexity shows that the number of multiplications required to compute some $n$-variate polynomial of degree $d$ is $\sqrt{{n+d \choose n}}$. We complement this by an almost matching upper bound, showing that any $n$-variate polynomial of degree $d$ over any field can be computed with only ... more >>>

Christoph Behle, Andreas Krebs, Klaus-Joern Lange, Pierre McKenzie

In the setting known as DLOGTIME-uniformity,

the fundamental complexity classes

$AC^0\subset ACC^0\subseteq TC^0\subseteq NC^1$ have several

robust characterizations.

In this paper we refine uniformity further and examine the impact

of these refinements on $NC^1$ and its subclasses.

When applied to the logarithmic circuit depth characterization of $NC^1$,

some refinements leave ...
more >>>

Gil Cohen, Ran Raz, Gil Segev

Motivated by the classical problem of privacy amplification, Dodis and Wichs (STOC '09) introduced the notion of a non-malleable extractor, significantly strengthening the notion of a strong extractor. A non-malleable extractor is a function $nmExt : \{0,1\}^n \times \{0,1\}^d \rightarrow \{0,1\}^m$ that takes two inputs: a weak source $W$ and ... more >>>

Thomas Watson

We study the lift-and-project procedures of Lovasz-Schrijver and Sherali-Adams applied to the standard linear programming relaxation of the traveling salesperson problem with triangle inequality. For the asymmetric TSP tour problem, Charikar, Goemans, and Karloff (FOCS 2004) proved that the integrality gap of the standard relaxation is at least 2. We ... more >>>

Marek Karpinski, Richard Schmied, Claus Viehmann

We establish almost tight upper and lower approximation bounds for the Vertex Cover problem on dense k-partite hypergraphs.

more >>>Anant Jindal, Gazal Kochar, Manjish Pal

In this paper we study the classic problem of computing a maximum cardinality matching in general graphs $G = (V, E)$. This problem has been studied extensively more than four decades. The best known algorithm for this problem till date runs in $O(m \sqrt{n})$ time due to Micali and Vazirani ... more >>>

Parikshit Gopalan, Cheng Huang, Huseyin Simitci, Sergey Yekhanin

Consider a linear $[n,k,d]_q$ code $\mc{C}.$ We say that that $i$-th coordinate of $\mc{C}$ has locality $r,$ if the value at this coordinate can be recovered from accessing some other $r$ coordinates of $\mc{C}.$ Data storage applications require codes with small

redundancy, low locality for information coordinates, large distance, and ...
more >>>

Angsheng Li, Yicheng Pan, Pan Peng

In this paper, we study the problem of testing the conductance of a

given graph in the general graph model. Given distance parameter

$\varepsilon$ and any constant $\sigma>0$, there exists a tester

whose running time is $\mathcal{O}(\frac{m^{(1+\sigma)/2}\cdot\log

n\cdot\log\frac{1}{\varepsilon}}{\varepsilon\cdot\Phi^2})$, where

$n$ is the number of vertices and $m$ is the number ...
more >>>

Miklos Ajtai

For each natural number $d$ we consider a finite structure $M_{d}$ whose

universe is the set of all $0,1$-sequence of length $n=2^{d}$, each

representing a natural number in the set $\lbrace 0,1,...,2^{n}-1\rbrace

$ in binary form.

The operations included in the structure are the

constants $0,1,2^{n}-1,n$, multiplication and addition ...
more >>>

Yang Li

We initiate the study of the relationship between two complexity classes, BQP

(Bounded-Error Quantum Polynomial-Time) and PPAD (Polynomial Parity Argument,

Directed). We first give a conjecture that PPAD is contained in BQP, and show

a necessary and sufficient condition for the conjecture to hold. Then we prove

that the conjecture ...
more >>>

Or Meir

The PCP theorem asserts the existence of proofs that can be verified by a verifier that reads only a very small part of the proof. The theorem was originally proved by Arora and Safra (J. ACM 45(1)) and Arora et al. (J. ACM 45(3)) using sophisticated algebraic tools. More than ... more >>>

Graham Cormode, Michael Mitzenmacher, Justin Thaler

Motivated by the trend to outsource work to commercial cloud computing services, we consider a variation of the streaming paradigm where a streaming algorithm can be assisted by a powerful helper that can provide annotations to the data stream. We extend previous work on such annotation models by considering a ... more >>>

Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil Vadhan

We study differential privacy in a distributed setting where two parties would like to perform analysis of their joint data while preserving privacy for both datasets. Our results imply almost tight lower bounds on the accuracy of such data analyses, both for specific natural functions (such as Hamming distance) and ... more >>>

Pavol Duris

In this paper we deal with 1-way multihead finite automata, in which the symbol under only one head (called read head) controls its move and other heads cannot distinguish the input symbols, they can only distinguish the end-marker from the other input symbols and they are called the blind head. ... more >>>

Scott Aaronson

One might think that, once we know something is computable, how efficiently it can be computed is a practical question with little further philosophical importance. In this essay, I offer a detailed case that one would be wrong. In particular, I argue that computational complexity theory---the field that studies the ... more >>>

Zvika Brakerski, Vinod Vaikuntanathan

We present a fully homomorphic encryption scheme that is based solely on the (standard) learning with errors (LWE) assumption. Applying known results on LWE, the security of our scheme is based on the worst-case hardness of ``short vector problems'' on arbitrary lattices.

Our construction improves on previous works in two ... more >>>

Alessandro Chiesa, Michael Forbes

We present three contributions to the understanding of QMA with multiple provers:

1) We give a tight soundness analysis of the protocol of [Blier and Tapp, ICQNM '09], yielding a soundness gap $\Omega(N^{-2})$, which is the best-known soundness gap for two-prover QMA protocols with logarithmic proof size. Maybe ...
more >>>

Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan

We present a radically new approach to fully homomorphic encryption (FHE) that dramatically improves performance and bases security on weaker assumptions. A central conceptual contribution in our work is a new way of constructing leveled fully homomorphic encryption schemes (capable of evaluating arbitrary polynomial-size circuits), {\em without Gentry's bootstrapping procedure}.

... more >>>Dana Moshkovitz

In this paper we put forward a conjecture: an instantiation of the Sliding Scale Conjecture of Bellare, Goldwasser, Lund and Russell to projection games. We refer to this conjecture as the Projection Games Conjecture.

We further suggest the research agenda of establishing new hardness of approximation results based on the ... more >>>

Emanuele Viola

The 3SUM problem asks if there are three integers $a,b,c$ summing to $0$ in a given set of $n$ integers of magnitude poly($n$). Patrascu (STOC '10) reduces solving 3SUM in time $n^{2-\Omega(1)}$ to listing $m$ triangles in a graph with $m$ edges in time $m^{4/3-\Omega(1)}$.

In this note we present ...
more >>>

Varun Kanade

Valiant (2007) proposed a computational model for evolution and suggested that evolvability be studied in the framework of computational learning theory. Feldman (2008) showed that Valiant’s evolution model is equivalent to the correlational statistical query (CSQ) learning model, which is a restricted setting of the statistical query (SQ) model. Evolvability ... more >>>

Varun Kanade, Thomas Steinke

We study the online decision problem where the set of available actions varies over time, also called the sleeping experts problem. We consider the setting where the performance comparison is made with respect to the best ordering of actions in hindsight. In this paper, both the payoff function and the ... more >>>

Andris Ambainis, Xiaoming Sun

In this note we give a new separation between sensitivity and block sensitivity of Boolean functions: $bs(f)=\frac{2}{3}s(f)^2-\frac{1}{3}s(f)$.

more >>>Andrej Bogdanov, Periklis Papakonstantinou, Andrew Wan

We give an explicit construction of a pseudorandom generator for read-once formulas whose inputs can be read in arbitrary order. For formulas in $n$ inputs and arbitrary gates of fan-in at most $d = O(n/\log n)$, the pseudorandom generator uses $(1 - \Omega(1))n$ bits of randomness and produces an output ... more >>>

Brett Hemenway, Rafail Ostrovsky, Martin Strauss, Mary Wootters

This work considers locally decodable codes in the computationally bounded channel model. The computationally bounded channel model, introduced by Lipton in 1994, views the channel as an adversary which is restricted to polynomial-time computation. Assuming the existence of IND-CPA secure public-key encryption, we present a construction of public-key locally decodable ... more >>>

Subhash Khot, Preyas Popat, Nisheeth Vishnoi

We prove that for an arbitrarily small constant $\eps>0,$ assuming NP$\not \subseteq$DTIME$(2^{{\log^{O(1/\epsilon)} n}})$, the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor better than $2^{\log ^{1-\epsilon}n}.$ This improves upon the previous hardness factor of $(\log n)^\delta$ for some $\delta ... more >>>

Thomas Watson

We prove a lower bound on the amount of nonuniform advice needed by black-box reductions for the Dense Model Theorem of Green, Tao, and Ziegler, and of Reingold, Trevisan, Tulsiani, and Vadhan. The latter theorem roughly says that for every distribution $D$ that is $\delta$-dense in a distribution that is ... more >>>

Oded Goldreich, Rani Izsak

We study the computability of one-way functions and pseudorandom generators

by monotone circuits, showing a substantial gap between the two:

On one hand, there exist one-way functions that are computable

by (uniform) polynomial-size monotone functions, provided (of course)

that one-way functions exist at all.

On the other hand, ...
more >>>

Gillat Kol, Ran Raz

Let $C$ be a (fan-in $2$) Boolean circuit of size $s$ and depth $d$, and let $x$ be an input for $C$. Assume that a verifier that knows $C$ but doesn't know $x$ can access the low degree extension of $x$ at one random point. Two competing provers try to ... more >>>

Mark Braverman

The primary goal of this paper is to define and study the interactive information complexity of functions. Let $f(x,y)$ be a function, and suppose Alice is given $x$ and Bob is given $y$. Informally, the interactive information complexity $IC(f)$ of $f$ is the least amount of information Alice and Bob ... more >>>

Nader Bshouty, Hanna Mazzawi

The coin weighing problem is the following: Given $n$ coins for which $m$ of them are counterfeit with the same weight. The problem is to detect the counterfeit coins with minimal number of weighings. This problem has many applications in compressed sensing, multiple access adder channels, etc. The problem was ... more >>>

Andrew Drucker

We study the circuit complexity of Boolean operators, i.e., collections of Boolean functions defined over a common input. Our focus is the well-studied model in which arbitrary Boolean functions are allowed as gates, and in which a circuit's complexity is measured by its depth and number of wires. We show ... more >>>

Benny Applebaum, Andrej Bogdanov, Alon Rosen

We consider pseudorandom generators in which each output bit depends on a constant number of input bits. Such generators have appealingly simple structure: they can be described by a sparse input-output dependency graph and a small predicate that is applied at each output. Following the works of Cryan and Miltersen ... more >>>

Ronen Shaltiel

We construct an explicit disperser for affine sources over $\F_2^n$ with entropy $k=2^{\log^{0.9} n}=n^{o(1)}$. This is a polynomial time computable function $D:\F_2^n \ar \B$ such that for every affine space $V$ of $\F_2^n$ that has dimension at least $k$, $D(V)=\set{0,1}$. This improves the best previous construction of Ben-Sasson and Kopparty ... more >>>

Michael Elberfeld, Andreas Jakoby, Till Tantau

An algorithmic meta theorem for a logic and a class $C$ of structures states that all problems expressible in this logic can be solved efficiently for inputs from $C$. The prime example is Courcelle's Theorem, which states that monadic second-order (MSO) definable problems are linear-time solvable on graphs of bounded ... more >>>

Eli Ben-Sasson, Ariel Gabizon

Let $F$ be the field of $q$ elements, where $q=p^{\ell}$ for prime $p$. Informally speaking, a polynomial source is a distribution over $F^n$ sampled by low degree multivariate polynomials. In this paper, we construct extractors for polynomial sources over fields of constant size $q$ assuming $p \ll q$.

More generally, ... more >>>

Sergei Lozhkin, Alexander Shiganov

In this paper we suggest a modification of classical Lupanov's method [Lupanov1958]

that allows building circuits over the basis $\{\&,\vee,\neg\}$ for Boolean functions of $n$ variables with size at most

$$

\frac{2^n}{n}\left(1+\frac{3\log n + O(1)}{n}\right),

$$

and with more uniform distribution of outgoing arcs by circuit gates.

For almost all ... more >>>

Rahul Santhanam, Srikanth Srinivasan

Impagliazzo, Paturi and Zane (JCSS 2001) proved a sparsification lemma for $k$-CNFs:

every k-CNF is a sub-exponential size disjunction of $k$-CNFs with a linear

number of clauses. This lemma has subsequently played a key role in the study

of the exact complexity of the satisfiability problem. A natural question is

more >>>

Ludwig Staiger

The present paper generalises results by Tadaki [12] and Calude et al. [1] on oscillation-free partially random infinite strings. Moreover, it shows that oscillation-free partial Chaitin randomness can be separated from scillation-free partial strong Martin-L\"of randomness by $\Pi_{1}^{0}$-definable sets of infinite strings.

more >>>Maurice Jansen, Rahul Santhanam

Suppose $f$ is a univariate polynomial of degree $r=r(n)$ that is computed by a size $n$ arithmetic circuit.

It is a basic fact of algebra that a nonzero univariate polynomial of degree $r$ can vanish on at most $r$ points. This implies that for checking whether $f$ is identically zero, ...
more >>>

Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff

This work deals with the power of linear algebra in the context of multilinear computation. By linear algebra we mean algebraic branching programs (ABPs) which are known to be computationally equivalent to two basic tools in linear algebra: iterated matrix multiplication and the determinant. We compare the computational power of ... more >>>

Maurice Jansen, Rahul Santhanam

We associate to each Boolean language complexity class $\mathcal{C}$ the algebraic class $a\cdot\mathcal{C}$ consisting of families of polynomials $\{f_n\}$ for which the evaluation problem over the integers is in $\mathcal{C}$. We prove the following lower bound and randomness-to-hardness results:

1. If polynomial identity testing (PIT) is in $NSUBEXP$ then $a\cdot ... more >>>

eran gat , shafi goldwasser

In this paper we introduce a new type of probabilistic search algorithm, which we call the

{\it Bellagio} algorithm: a probabilistic algorithm which is guaranteed to run in expected polynomial time,

and to produce a correct and {\it unique} solution with high probability.

We argue the applicability of such algorithms ...
more >>>

Vikraman Arvind, Yadu Vasudev

Given two $n$-variable boolean functions $f$ and $g$, we study the problem of computing an $\varepsilon$-approximate isomorphism between them. I.e.\ a permutation $\pi$ of the $n$ variables such that $f(x_1,x_2,\ldots,x_n)$ and $g(x_{\pi(1)},x_{\pi(2)},\ldots,x_{\pi(n)})$ differ on at most an $\varepsilon$ fraction of all boolean inputs $\{0,1\}^n$. We give a randomized $2^{O(\sqrt{n}\log(n)^{O(1)})}$ algorithm ... more >>>

Guy Moshkovitz

In this paper we present a combinatorial approach for proving complexity lower bounds. We mainly focus on the following instantiation of it. Consider a pair of properties of $m$-edge regular hypergraphs. Suppose they are ``indistinguishable'' with respect to hypergraphs with $m-t$ edges, in the sense that every such hypergraph has ... more >>>

Zeev Dvir, Shachar Lovett

In this work we describe an explicit, simple, construction of large subsets of F^n, where F is a finite field, that have small intersection with every k-dimensional affine subspace. Interest in the explicit construction of such sets, termed subspace-evasive sets, started in the work of Pudlak and Rodl (2004) ... more >>>

Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar, Yadu Vasudev

Let $G=\langle S\rangle$ be a solvable permutation group given as input by generating set $S$. I.e.\ $G$ is a solvable subgroup of the symmetric group $S_n$. We give a deterministic polynomial-time algorithm that computes an expanding generator set for $G$. More precisely, given a constant $\lambda <1$ we can compute ... more >>>

Salil Vadhan, Colin Jia Zheng

We provide a characterization of pseudoentropy in terms of hardness of sampling: Let $(X,B)$ be jointly distributed random variables such that $B$ takes values in a polynomial-sized set. We show that $B$ is computationally indistinguishable from a random variable of higher Shannon entropy given $X$ if and only if there ... more >>>

Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer

The long code is a central tool in hardness of approximation, especially in

questions related to the unique games conjecture. We construct a new code that

is exponentially more ecient, but can still be used in many of these applications.

Using the new code we obtain exponential improvements over several ...
more >>>

Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

We present a single, common tool to strictly subsume all known cases of polynomial time blackbox polynomial identity testing (PIT) that have been hitherto solved using diverse tools and techniques. In particular, we show that polynomial time hitting-set generators for identity testing of the two seemingly different and well studied ... more >>>

Greg Kuperberg, Shachar Lovett, Ron Peled

We show the existence of rigid combinatorial objects which previously were not known to exist. Specifically, for a wide range of the underlying parameters, we show the existence of non-trivial orthogonal arrays, $t$-designs, and $t$-wise permutations. In all cases, the sizes of the objects are optimal up to polynomial overhead. ... more >>>

Alexander A. Sherstov

We study the set disjointness problem in the number-on-the-forehead model.

(i) We prove that $k$-party set disjointness has randomized and nondeterministic

communication complexity $\Omega(n/4^k)^{1/4}$ and Merlin-Arthur complexity $\Omega(n/4^k)^{1/8}.$

These bounds are close to tight. Previous lower bounds (2007-2008) for $k\geq3$ parties

were weaker than $n^{1/(k+1)}/2^{k^2}$ in all ...
more >>>

Bireswar Das, Manjish Pal, Vijay Visavaliya

In this paper, we prove that most of the boolean functions, $f : \{-1,1\}^n \rightarrow \{-1,1\}$

satisfy the Fourier Entropy Influence (FEI) Conjecture due to Friedgut and Kalai (Proc. AMS'96)\cite{FG96}. The conjecture says that the Entropy of a boolean function is at most a constant times the Influence of ...
more >>>

Michael Forbes, Amir Shpilka

We study the problem of obtaining efficient, deterministic, black-box polynomial identity testing algorithms for depth-3 set-multilinear circuits (over arbitrary fields). This class of circuits has an efficient, deterministic, white-box polynomial identity testing algorithm (due to Raz and Shpilka), but has no known such black-box algorithm. We recast this problem as ... more >>>

Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf

To compare the complexity of the perfect matching problem for general graphs with that for planar graphs, one might try to come up with a reduction from the perfect matching problem to the planar perfect matching problem.

The obvious way to construct such a reduction is via a {\em planarizing ...
more >>>

Paul Beame, Chris Beck, Russell Impagliazzo

We give the first time-space tradeoff lower bounds for Resolution proofs that apply to superlinear space. In particular, we show that there are formulas of size $N$ that have Resolution refutations of space and size each roughly $N^{\log_2 N}$ (and like all formulas have Resolution refutations of space $N$) for ... more >>>

Anna Gal, Kristoffer Arnsfelt Hansen, Michal Koucky, Pavel Pudlak, Emanuele Viola

We bound the minimum number $w$ of wires needed to compute any (asymptotically good) error-correcting code

$C:\{0,1\}^{\Omega(n)} \to \{0,1\}^n$ with minimum distance $\Omega(n)$,

using unbounded fan-in circuits of depth $d$ with arbitrary gates. Our main results are:

(1) If $d=2$ then $w = \Theta(n ({\log n/ \log \log n})^2)$.

(2) ... more >>>

Valentine Kabanets, Osamu Watanabe

The Valiant-Vazirani Isolation Lemma [TCS, vol. 47, pp. 85--93, 1986] provides an efficient procedure for isolating a satisfying assignment of a given satisfiable circuit: given a Boolean circuit $C$ on $n$ input variables, the procedure outputs a new circuit $C'$ on the same $n$ input variables with the property that ... more >>>

Emanuele Viola

Suppose each of $k \le n^{o(1)}$ players holds an $n$-bit number $x_i$ in its hand. The players wish to determine if $\sum_{i \le k} x_i = s$. We give a public-coin protocol with error $1\%$ and communication $O(k \lg k)$. The communication bound is independent of $n$, and for $k ... more >>>

Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam

We present a randomized algorithm for reconstructing multilinear depth-4 arithmetic circuits with fan-in 2 at the top + gate. The algorithm is given blackbox access to a multilinear polynomial f in F[x_1,..,x_n] computable by a multilinear Sum-Product-Sum-Product(SPSP) circuit of size s and outputs an equivalent multilinear SPSP circuit, runs ... more >>>

Klim Efremenko

Locally Decodable Code (LDC) is a code that encodes a message in a way that one can decode any particular symbol of the message by reading only a constant number of locations, even if a constant fraction of the encoded message is adversarially

corrupted.

In this paper we ... more >>>

Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen

We study the $k$-party `number on the forehead' communication complexity of composed functions $f \circ \vec{g}$, where $f:\{0,1\}^n \to \{\pm 1\}$, $\vec{g} = (g_1,\ldots,g_n)$, $g_i : \{0,1\}^k \to \{0,1\}$ and for $(x_1,\ldots,x_k) \in (\{0,1\}^n)^k$, $f \circ \vec{g}(x_1,\ldots,x_k) = f(\ldots,g_i(x_{1,i},\ldots,x_{k,i}), \ldots)$. When $\vec{g} = (g,g,\ldots,g)$ we denote $f \circ \vec{g}$ by ... more >>>

Marek Karpinski, Richard Schmied

We study the approximation hardness of the Shortest Superstring, the Maximal Compression and

the Maximum Asymmetric Traveling Salesperson (MAX-ATSP) problem.

We introduce a new reduction method that produces strongly restricted instances of

the Shortest Superstring problem, in which the maximal orbit size is eight

(with no ...
more >>>

Eli Ben-Sasson, Shachar Lovett, Noga Ron-Zewi

For a {0,1}-valued matrix $M$ let CC($M$) denote the deterministic communication complexity of the boolean function associated with $M$. The log-rank conjecture of Lovasz and Saks [FOCS 1988] states that CC($M$) is at most $\log^c({\mbox{rank}}(M))$ for some absolute constant $c$ where rank($M$) denotes the rank of $M$ over the field ... more >>>

Matthew Anderson, Dieter van Melkebeek, Nicole Schweikardt, Luc Segoufin

We study the locality of an extension of first-order logic that captures graph queries computable in AC$^0$, i.e., by families of polynomial-size constant-depth circuits. The extension considers first-order formulas over relational structures which may use arbitrary numerical predicates in such a way that their truth value is independent of the ... more >>>

Oded Goldreich, Ron Rothblum

We take a closer look at several enhancements of the notion of trapdoor permutations. Specifically, we consider the notions of enhanced trapdoor permutation (Goldreich 2004) and doubly enhanced trapdoor permutation (Goldreich 2008) as well as intermediate notions (Rothblum 2010). These enhancements arose in the study of Oblivious Transfer and NIZK, ... more >>>

Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff

We introduce a notion of non-black-box access to computational devices (such as circuits, formulas, decision trees, and so forth) that we call \emph{restriction access}. Restrictions are partial assignments to input variables. Each restriction simplifies the device, and yields a new device for the restricted function on the unassigned variables. On ... more >>>

Xin Li

We introduce a new combinatorial object, called a \emph{design extractor}, that has both the properties of a design and an extractor. We give efficient constructions of such objects and show that they can be used in several applications.

\begin{enumerate}

\item {Improving the output length of known non-malleable extractors.} Non-malleable extractors ...
more >>>

Pavel Pudlak

We prove an exponential lower bound on the lengths of resolution proofs of propositions expressing the finite Ramsey theorem for pairs.

more >>>Libor Barto, Marcin Kozik

An algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying at least $(1-g(\varepsilon))$-fraction of the constraints given a $(1-\varepsilon)$-satisfiable instance, where $g(\varepsilon) \rightarrow 0$ as $\varepsilon \rightarrow 0$, $g(0)=0$.

Guruswami and Zhou conjectured a characterization of constraint languages for which the corresponding constraint satisfaction ...
more >>>

Mark Braverman, Omri Weinstein

This paper provides the first general technique for proving information lower bounds on two-party

unbounded-rounds communication problems. We show that the discrepancy lower bound, which

applies to randomized communication complexity, also applies to information complexity. More

precisely, if the discrepancy of a two-party function $f$ with respect ...
more >>>

Elena Grigorescu, Chris Peikert

The question of list decoding error-correcting codes over finite fields (under the Hamming metric) has been widely studied in recent years. Motivated by the similar discrete structure of linear codes and point lattices in $R^{N}$, and their many shared applications across complexity theory, cryptography, and coding theory, we initiate the ... more >>>

Xin Li

Dodis and Wichs \cite{DW09} introduced the notion of a non-malleable extractor to study the problem of privacy amplification with an active adversary. A non-malleable extractor is a much stronger version of a strong extractor. Given a weakly-random string $x$ and a uniformly random seed $y$ as the inputs, the non-malleable ... more >>>

Nikolay Vereshchagin

Assume that $NP\ne RP$. Gutfreund, Shaltiel, and Ta-Shma in [Computational Complexity 16(4):412-441 (2007)] have proved that for every randomized polynomial time decision algorithm $D$ for SAT there is a polynomial time samplable distribution such that $D$ errs with probability at least $1/6-\epsilon$ on a random formula chosen with respect to ... more >>>

Joshua Grochow

We study the problem of matrix Lie algebra conjugacy. Lie algebras arise centrally in areas as diverse as differential equations, particle physics, group theory, and the Mulmuley--Sohoni Geometric Complexity Theory program. A matrix Lie algebra is a set $\mathcal{L}$ of matrices such that $A,B \in \mathcal{L}$ implies$AB - BA \in ... more >>>

Leonid Gurvits

Let $A \in \Omega_n$ be doubly-stochastic $n \times n$ matrix. Alexander Schrijver proved in 1998 the following remarkable inequality

\begin{equation} \label{le}

per(\widetilde{A}) \geq \prod_{1 \leq i,j \leq n} (1- A(i,j)); \widetilde{A}(i,j) =: A(i,j)(1-A(i,j)), 1 \leq i,j \leq n

\end{equation}

We prove in this paper the following generalization (or just clever ...
more >>>

Constantinos Daskalakis, S. Matthew Weinberg

We efficiently solve the optimal multi-dimensional mechanism design problem for independent bidders with arbitrary demand constraints when either the number of bidders is a constant or the number of items is a constant. In the first setting, we need that each bidder's values for the items are sampled from a ... more >>>

Piotr Indyk, Reut Levi, Ronitt Rubinfeld

A discrete distribution $p$, over $[n]$, is a $k$-histogram if its probability distribution function can be

represented as a piece-wise constant function with $k$ pieces. Such a function

is

represented by a list of $k$ intervals and $k$ corresponding values. We consider

the following problem: given a collection of samples ...
more >>>

Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg

We obtain a characterization of feasible, Bayesian, multi-item multi-bidder mechanisms with independent, additive bidders as distributions over hierarchical mechanisms. Combined with cyclic-monotonicity our results provide a complete characterization of feasible, Bayesian Incentive Compatible mechanisms for this setting.

Our characterization is enabled by a novel, constructive proof of Border's theorem [Border ... more >>>

Christoph Behle, Andreas Krebs

We consider first order logic over words and show FO+MOD[<] is contained in MAJ[<] with three variables.

It is known that for the classes FO[<], FO+MOD[<], FO+GROUP[<] three variables suffice. In the case of MOD[<] even two variables are sufficient.

As a consequence we know that if TC^ 0 neq ... more >>>

Pavel Hrubes, Iddo Tzameret

We study arithmetic proof systems $\mathbb{P}_c(\mathbb{F})$ and $\mathbb{P}_f(\mathbb{F})$ operating with arithmetic circuits and arithmetic formulas, respectively, that prove polynomial identities over a field $\mathbb{F}$. We establish a series of structural theorems about these proof systems, the main one stating that $\mathbb{P}_c(\mathbb{F})$ proofs can be balanced: if a polynomial identity of ... more >>>