All reports in year 2012:

__
TR12-001
| 1st January 2012
__

Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett#### Testing Low Complexity Affine-Invariant Properties

__
TR12-002
| 4th January 2012
__

Akinori Kawachi, Benjamin Rossman, Osamu Watanabe#### Query Complexity and Error Tolerance of Witness Finding Algorithms

Revisions: 3

__
TR12-003
| 13th December 2011
__

Pratik Worah#### Rank Bounds for a Hierarchy of Lov\'{a}sz and Schrijver

__
TR12-004
| 10th January 2012
__

Marcos Villagra, Masaki Nakanishi, Shigeru Yamashita, Yasuhiko Nakashima#### Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication

Revisions: 3

__
TR12-005
| 13th January 2012
__

Periklis Papakonstantinou, Guang Yang#### A remark on one-wayness versus pseudorandomness

__
TR12-006
| 21st January 2012
__

Gregory Valiant#### Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas with Noise

Revisions: 2

__
TR12-007
| 28th January 2012
__

Ruiwen Chen, Valentine Kabanets#### Lower Bounds against Weakly Uniform Circuits

Revisions: 1

__
TR12-008
| 30th January 2012
__

Marek Karpinski, Richard Schmied#### On Approximation Lower Bounds for TSP with Bounded Metrics

Revisions: 1

__
TR12-009
| 28th November 2011
__

Prabhu Manyem, Julien Ugon#### Computational Complexity, NP Completeness and Optimization Duality: A Survey

__
TR12-010
| 5th February 2012
__

Shafi Goldwasser, Guy Rothblum#### How to Compute in the Presence of Leakage

__
TR12-011
| 7th February 2012
__

Nader Bshouty#### Testers and their Applications

__
TR12-012
| 9th February 2012
__

Oded Goldreich#### On the Effect of the Proximity Parameter on Property Testers

__
TR12-013
| 15th February 2012
__

Tomas Feder, Carlos Subi#### Packing Edge-Disjoint Triangles in Given Graphs

__
TR12-014
| 20th February 2012
__

Johannes Mittmann, Nitin Saxena, Peter Scheiblechner#### Algebraic Independence in Positive Characteristic -- A p-Adic Calculus

__
TR12-015
| 22nd February 2012
__

Albert Atserias, Anuj Dawar#### Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers

Revisions: 2

__
TR12-016
| 24th February 2012
__

Anindya De, Elchanan Mossel#### Explicit Optimal hardness via Gaussian stability results

Revisions: 3

__
TR12-017
| 1st March 2012
__

Venkatesan Guruswami, Srivatsan Narayanan#### Combinatorial limitations of a strong form of list decoding

Revisions: 1

__
TR12-018
| 24th February 2012
__

Joerg Flum, Moritz Müller#### Some definitorial suggestions for parameterized proof complexity

__
TR12-019
| 2nd March 2012
__

Eric Miles, Emanuele Viola#### On the complexity of constructing pseudorandom functions (especially when they don't exist)

__
TR12-020
| 3rd March 2012
__

Daniele Micciancio#### Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction

Revisions: 1

__
TR12-021
| 14th March 2012
__

Oded Goldreich, Igor Shinkar#### Two-Sided Error Proximity Oblivious Testing

Revisions: 4

__
TR12-022
| 14th March 2012
__

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler#### Annotations in Data Streams

Revisions: 1

__
TR12-023
| 19th March 2012
__

Sophie Laplante, Virginie Lerays, Jérémie Roland#### Classical and quantum partition bound and detector inefficiency

__
TR12-024
| 25th March 2012
__

Scott Aaronson, Paul Christiano#### Quantum Money from Hidden Subspaces

__
TR12-025
| 23rd March 2012
__

Kord Eickmeyer, Kristoffer Arnsfelt Hansen, Elad Verbin#### Approximating the minmax value of 3-player games within a constant is as hard as detecting planted cliques

__
TR12-026
| 27th March 2012
__

Thomas Watson#### Time Hierarchies for Sampling Distributions

Revisions: 2

__
TR12-027
| 29th March 2012
__

Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis Papakonstantinou, Bangsheng Tang#### Time-space tradeoffs for width-parameterized SAT:Algorithms and lower bounds

Revisions: 2

__
TR12-028
| 30th March 2012
__

Eric Allender, George Davie, Luke Friedman, Samuel Hopkins, Iddo Tzameret#### Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic

Revisions: 1

__
TR12-029
| 3rd April 2012
__

Shachar Lovett#### An exposition of Sanders quasi-polynomial Freiman-Ruzsa theorem

__
TR12-030
| 4th April 2012
__

Deeparnab Chakrabarty, C. Seshadhri#### Optimal bounds for monotonicity and Lipschitz testing over the hypercube

Revisions: 2

__
TR12-031
| 4th April 2012
__

Tom Gur, Omer Tamuz#### Testing Booleanity and the Uncertainty Principle

Revisions: 1

__
TR12-032
| 4th April 2012
__

Sebastian Kuhnert, Johannes Köbler, Osamu Watanabe#### Interval graph representation with given interval and intersection lengths

__
TR12-033
| 5th April 2012
__

Ankit Gupta, Neeraj Kayal, Youming Qiao#### Random Arithmetic Formulas can be Reconstructed Efficiently

__
TR12-034
| 5th April 2012
__

Abhishek Bhowmick, Zeev Dvir, Shachar Lovett#### New Lower Bounds for Matching Vector Codes

Revisions: 5

__
TR12-035
| 5th April 2012
__

Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler#### Finding Cycles and Trees in Sublinear Time

Revisions: 1
,
Comments: 1

__
TR12-036
| 12th April 2012
__

Venkatesan Guruswami, Chaoping Xing#### Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding

__
TR12-037
| 10th April 2012
__

Alexander A. Sherstov#### Making Polynomials Robust to Noise

__
TR12-038
| 6th April 2012
__

Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jérémie Roland, David Xiao#### Lower bounds on information complexity via zero-communication protocols and applications

__
TR12-039
| 17th April 2012
__

Stasys Jukna#### Clique Problem, Cutting Plane Proofs, and Communication Complexity

__
TR12-040
| 17th April 2012
__

Sangxia Huang#### Approximation Resistance on Satisfiable Instances for Predicates Strictly Dominating Parity

__
TR12-041
| 17th April 2012
__

Stasys Jukna#### Limitations of Incremental Dynamic Programs

Revisions: 1

__
TR12-042
| 17th April 2012
__

Chris Beck, Russell Impagliazzo, Shachar Lovett#### Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits

__
TR12-043
| 16th April 2012
__

Zvika Brakerski, Yael Tauman Kalai#### Efficient Interactive Coding Against Adversarial Noise

Revisions: 1

__
TR12-044
| 22nd April 2012
__

Swastik Kopparty#### List-Decoding Multiplicity Codes

__
TR12-045
| 22nd April 2012
__

Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer#### On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs

Revisions: 3

__
TR12-046
| 24th April 2012
__

Madhu Sudan, Noga Ron-Zewi#### A new upper bound on the query complexity for testing generalized Reed-Muller codes

Revisions: 1

__
TR12-047
| 24th April 2012
__

Emanuele Viola#### Extractors for Turing-machine sources

__
TR12-048
| 25th April 2012
__

Alan Guo, Madhu Sudan#### Some closure features of locally testable affine-invariant properties

__
TR12-049
| 27th April 2012
__

Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan#### Sparse affine-invariant linear codes are locally testable

__
TR12-050
| 25th April 2012
__

Avraham Ben-Aroya, Gil Cohen#### Gradual Small-Bias Sample Spaces

Revisions: 3

__
TR12-051
| 25th April 2012
__

Dmitry Gavinsky, Shachar Lovett, Michael Saks, Srikanth Srinivasan#### A Tail Bound for Read-k Families of Functions

__
TR12-052
| 27th April 2012
__

Mohammad Mahmoody, David Xiao#### Languages with Efficient Zero-Knowledge PCPs are in SZK

__
TR12-053
| 30th April 2012
__

Ankur Moitra#### A Singly-Exponential Time Algorithm for Computing Nonnegative Rank

__
TR12-054
| 2nd May 2012
__

Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff#### Reductions to the set of random strings:the resource-bounded case

Revisions: 1

__
TR12-055
| 4th May 2012
__

Reut Levi, Dana Ron, Ronitt Rubinfeld#### Testing Similar Means

__
TR12-056
| 1st May 2012
__

Rocco Servedio, Li-Yang Tan, Justin Thaler#### Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions

Revisions: 1

__
TR12-057
| 7th May 2012
__

Russell Impagliazzo, Raghu Meka, David Zuckerman#### Pseudorandomness from Shrinkage

Revisions: 2

__
TR12-058
| 5th May 2012
__

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz#### How to Garble Arithmetic Circuits

Revisions: 1

__
TR12-059
| 14th May 2012
__

Rahul Santhanam, Ryan Williams#### Uniform Circuits, Lower Bounds, and QBF Algorithms

__
TR12-060
| 16th May 2012
__

Parikshit Gopalan, Raghu Meka, Omer Reingold#### DNF Sparsification and a Faster Deterministic Counting

Revisions: 2

__
TR12-061
| 16th May 2012
__

Pavel Hrubes, Amir Yehudayoff#### Formulas are exponentially stronger than monotone circuits in non-commutative setting

__
TR12-062
| 17th May 2012
__

Ilan Komargodski, Ran Raz#### Average-Case Lower Bounds for Formula Size

Revisions: 2

__
TR12-063
| 17th May 2012
__

Raghav Kulkarni, Miklos Santha#### Query complexity of matroids

__
TR12-064
| 10th May 2012
__

Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, Ying Xiao#### Statistical Algorithms and a Lower Bound for Planted Clique

Revisions: 2

__
TR12-065
| 16th May 2012
__

Mohammad Mahmoody, Hemanta Maji, Manoj Prabhakaran#### Limits of Random Oracles in Secure Computation

Revisions: 2

__
TR12-066
| 22nd April 2012
__

Jinyu Huang#### Parallel Complexity for Matroid Intersection and Matroid Parity Problems

Revisions: 1

__
TR12-067
| 6th May 2012
__

Xiaohui Bei, Ning Chen, Shengyu Zhang#### On the Complexity of Trial and Error

Revisions: 1

__
TR12-068
| 25th May 2012
__

Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena#### Deterministic Polynomial Factoring and Association Schemes

__
TR12-069
| 23rd March 2012
__

Lakhdar Saïs, Mohand-Saïd Hacid, francois hantry#### On the complexity of computing minimal unsatisfiable LTL formulas

__
TR12-070
| 26th May 2012
__

Thomas Watson#### The Complexity of Estimating Min-Entropy

Revisions: 1

__
TR12-071
| 29th May 2012
__

Kazuhisa Seto, Suguru Tamaki#### A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis

__
TR12-072
| 5th June 2012
__

Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco Servedio#### Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces

__
TR12-073
| 11th June 2012
__

Venkatesan Guruswami, Carol Wang#### Linear-algebraic list decoding for variants of Reed-Solomon codes

__
TR12-074
| 12th June 2012
__

Venkatesan Guruswami, Yuan Zhou#### Approximating Bounded Occurrence Ordering CSPs

__
TR12-075
| 12th June 2012
__

Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova#### Limitations of Local Filters of Lipschitz and Monotone Functions

__
TR12-076
| 12th June 2012
__

Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova#### Testing Lipschitz Functions on Hypergrid Domains

__
TR12-077
| 10th June 2012
__

Chiranjit Chakraborty, Rahul Santhanam#### Instance Compression for the Polynomial Hierarchy and Beyond

Comments: 2

__
TR12-078
| 14th June 2012
__

Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Yadu Vasudev#### Approximate Graph Isomorphism

__
TR12-079
| 14th June 2012
__

Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer#### Verifying Proofs in Constant Depth

__
TR12-080
| 18th June 2012
__

Baris Aydinlioglu, Dieter van Melkebeek#### Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Games

__
TR12-081
| 26th June 2012
__

Neeraj Kayal#### An exponential lower bound for the sum of powers of bounded degree polynomials

Revisions: 1

__
TR12-082
| 28th June 2012
__

Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker#### Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes

__
TR12-083
| 29th June 2012
__

Thomas Steinke#### Pseudorandomness for Permutation Branching Programs Without the Group Theory

__
TR12-084
| 3rd July 2012
__

Rahul Santhanam#### Ironic Complicity: Satisfiability Algorithms and Circuit Lower Bounds

__
TR12-085
| 5th July 2012
__

Tsuyoshi Ito, Thomas Vidick#### A multi-prover interactive proof for NEXP sound against entangled provers

__
TR12-086
| 4th July 2012
__

Shlomi Dolev, Nova Fandina, Dan Gutfreund#### Succinct Permanent is NEXP-hard with Many Hard Instances

__
TR12-087
| 4th July 2012
__

Peyman Afshani, Manindra Agrawal, Doerr Benjamin, Winzen Carola, Kasper Green Larsen, Kurt Mehlhorn#### The Deterministic and Randomized Query Complexity of a Simple Guessing Game

Revisions: 1

__
TR12-088
| 7th July 2012
__

Irit Dinur, Gillat Kol#### Covering CSPs

__
TR12-089
| 7th July 2012
__

Meena Boppana#### Lattice Variant of the Sensitivity Conjecture

__
TR12-090
| 2nd July 2012
__

Michael Blondin, Andreas Krebs, Pierre McKenzie#### The Complexity of Intersecting Finite Automata Having Few Final States

__
TR12-091
| 16th July 2012
__

Abuzer Yakaryilmaz#### One-counter verifiers for decidable languages

__
TR12-092
| 6th July 2012
__

Pavol Duris#### A Note On the Hierarchy of One-way Data-Independent Multi-Head Finite Automata.

__
TR12-093
| 1st July 2012
__

Charanjit Jutla, Vijay Kumar, Atri Rudra#### On the Circuit Complexity of Composite Galois Field Transformations

__
TR12-094
| 19th July 2012
__

Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva#### Testing Permanent Oracles -- Revisited

__
TR12-095
| 23rd July 2012
__

Avraham Ben-Aroya, Igor Shinkar#### A Note on Subspace Evasive Sets

__
TR12-096
| 17th July 2012
__

Albert Atserias, Sergi Oliva#### Bounded-width QBF is PSPACE-complete

Revisions: 3

__
TR12-097
| 26th July 2012
__

Andrej Bogdanov, Siyao Guo#### Sparse extractor families for all the entropy

__
TR12-098
| 3rd August 2012
__

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi#### An exponential lower bound for homogeneous depth four arithmetic circuits with bounded bottom fanin

Revisions: 3

__
TR12-099
| 5th August 2012
__

Nikos Leonardos#### An improved lower bound for the randomized decision tree complexity of recursive majority

Revisions: 1

__
TR12-100
| 23rd July 2012
__

Tomas Jirotka#### NP Search Problems

__
TR12-101
| 10th August 2012
__

Oded Goldreich, Shafi Goldwasser, Dana Ron#### On the possibilities and limitations of pseudodeterministic algorithms

__
TR12-102
| 16th August 2012
__

Swastik Kopparty, Srikanth Srinivasan#### Certifying Polynomials for $\mathrm{AC}^0[\oplus]$ circuits, with applications

__
TR12-103
| 16th August 2012
__

Arnab Bhattacharyya, Yuichi Yoshida#### Testing Assignments of Boolean CSPs

__
TR12-104
| 8th August 2012
__

Matthew Franklin, Ran Gelles, Rafail Ostrovsky, Leonard Schulman#### Optimal Coding for Streaming Authentication and Interactive Communication

Revisions: 1

__
TR12-105
| 17th August 2012
__

Madhur Tulsiani, Pratik Worah#### $LS_+$ Lower Bounds from Pairwise Independence

__
TR12-106
| 27th August 2012
__

Alan Guo, Madhu Sudan#### New affine-invariant codes from lifting

Comments: 1

__
TR12-107
| 30th August 2012
__

Brendan Juba, Ryan Williams#### Massive Online Teaching to Bounded Learners

__
TR12-108
| 4th September 2012
__

Arkadev Chattopadhyay, Rahul Santhanam#### Lower Bounds on Interactive Compressibility by Constant-Depth Circuits

__
TR12-109
| 31st August 2012
__

Subhash Khot, Muli Safra, Madhur Tulsiani#### Towards An Optimal Query Efficient PCP?

__
TR12-110
| 4th September 2012
__

Siu On Chan#### Approximation Resistance from Pairwise Independent Subgroups

__
TR12-111
| 5th September 2012
__

Venkatesan Guruswami, Ali Kemal Sinop#### Faster SDP hierarchy solvers for local rounding algorithms

__
TR12-112
| 7th September 2012
__

Andrew Drucker#### New Limits to Classical and Quantum Instance Compression

Revisions: 3

__
TR12-113
| 7th September 2012
__

Manindra Agrawal, Chandan Saha, Nitin Saxena#### Quasi-polynomial Hitting-set for Set-depth-$\Delta$ Formulas

__
TR12-114
| 15th July 2012
__

Mikhail Anokhin#### Constructing a Pseudo-Free Family of Finite Computational Groups under the General Integer Factoring Intractability Assumption

Revisions: 5

__
TR12-115
| 11th September 2012
__

Michael Forbes, Amir Shpilka#### Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs

Revisions: 1

__
TR12-116
| 13th September 2012
__

Luca Trevisan#### A Derandomized Switching Lemma and an Improved Derandomization of AC0

Revisions: 1

__
TR12-117
| 17th September 2012
__

Loïck Magnin, Jérémie Roland#### Explicit relation between all lower bound techniques for quantum query complexity

__
TR12-118
| 18th September 2012
__

Avi Wigderson, Amir Yehudayoff#### Population Recovery and Partial Identification

__
TR12-119
| 24th September 2012
__

Ilario Bonacina, Nicola Galesi#### Pseudo-partitions, Transversality and Locality: A Combinatorial Characterization for the Space Measure in Algebraic Proof Systems

__
TR12-120
| 24th September 2012
__

Boaz Barak#### Proof vs. Truth in Computational Complexity

Revisions: 1

__
TR12-121
| 25th September 2012
__

Pavel Hrubes#### A note on the real $\tau$-conjecture and the distribution of roots

Revisions: 2

__
TR12-122
| 17th September 2012
__

Giorgio Ausiello, Francesco Cristiano, Luigi Laura#### Syntactic Isomorphism of CNF Boolean Formulas is Graph Isomorphism Complete

__
TR12-123
| 28th September 2012
__

Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan#### Better pseudorandom generators from milder pseudorandom restrictions

__
TR12-124
| 29th September 2012
__

Massimo Lauria#### A rank lower bound for cutting planes proofs of Ramsey Theorem

__
TR12-125
| 2nd October 2012
__

Zahra Jafargholi, Hamidreza Jahanjou, Eric Miles, Jaideep Ramachandran, Emanuele Viola#### From RAM to SAT

Revisions: 1

__
TR12-126
| 23rd September 2012
__

Shiva Kintali, Sinziana Munteanu#### Computing Bounded Path Decompositions in Logspace

__
TR12-127
| 3rd October 2012
__

Eshan Chattopadhyay, Adam Klivans, Pravesh Kothari#### An Explicit VC-Theorem for Low-Degree Polynomials

__
TR12-128
| 21st September 2012
__

Nathanaël François, Frederic Magniez#### Streaming Complexity of Checking Priority Queues

Revisions: 1

__
TR12-129
| 9th October 2012
__

Iftach Haitner, Eran Omri, Hila Zarosim#### On the Power of Random Oracles

Revisions: 3

__
TR12-130
| 3rd October 2012
__

Abuzer Yakaryilmaz#### Public-qubits versus private-coins

__
TR12-131
| 18th October 2012
__

Mark Braverman, Ankur Moitra#### An Information Complexity Approach to Extended Formulations

Revisions: 1

__
TR12-132
| 21st October 2012
__

Yuval Filmus, Massimo Lauria, Jakob Nordström, Noga Ron-Zewi, Neil Thapen#### Space Complexity in Polynomial Calculus

__
TR12-133
| 21st October 2012
__

Noga Alon, Gil Cohen#### On Rigid Matrices and Subspace Polynomials

Revisions: 1

__
TR12-134
| 22nd October 2012
__

Alexander Razborov, Emanuele Viola#### Real Advantage

Revisions: 1

__
TR12-135
| 26th October 2012
__

Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, Julia Wolf#### Sampling-based proofs of almost-periodicity results and algorithmic applications

Revisions: 2

__
TR12-136
| 26th October 2012
__

Dan Boneh, Mark Zhandry#### Quantum-Secure Message Authentication Codes

Revisions: 2

__
TR12-137
| 1st November 2012
__

Johan Håstad#### On the correlation of parity and small-depth circuits

Revisions: 1

__
TR12-138
| 2nd November 2012
__

Zeev Dvir, Shubhangi Saraf, Avi Wigderson#### Improved rank bounds for design matrices and a new proof of Kelly's theorem

__
TR12-139
| 2nd November 2012
__

Albert Ai, Zeev Dvir, Shubhangi Saraf, Avi Wigderson#### Sylvester-Gallai type theorems for approximate collinearity

__
TR12-140
| 27th October 2012
__

Mark Zhandry#### How to Construct Quantum Random Functions

Revisions: 2

__
TR12-141
| 22nd October 2012
__

Dmitry Itsykson, Dmitry Sokolov#### Lower bounds for myopic DPLL algorithms with a cut heuristic

__
TR12-142
| 3rd November 2012
__

Markus Bläser#### Noncommutativity makes determinants hard

__
TR12-143
| 5th November 2012
__

Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff#### Direct Products in Communication Complexity

Revisions: 2

__
TR12-144
| 6th November 2012
__

Rocco Servedio, Emanuele Viola#### On a special case of rigidity

__
TR12-145
| 31st October 2012
__

Cenny Wenner#### Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four

__
TR12-146
| 7th November 2012
__

Venkatesan Guruswami, Chaoping Xing#### List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound

__
TR12-147
| 7th November 2012
__

Xin Li#### New Independent Source Extractors with Exponential Improvement

__
TR12-148
| 7th November 2012
__

Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf#### A new family of locally correctable codes based on degree-lifted algebraic geometry codes

Revisions: 1

__
TR12-149
| 8th November 2012
__

Alan Guo, Swastik Kopparty, Madhu Sudan#### New affine-invariant codes from lifting

Comments: 1

__
TR12-150
| 1st November 2012
__

Michael Elberfeld, Christoph Stockhusen, Till Tantau#### On the Space Complexity of Parameterized Problems

Revisions: 1

__
TR12-151
| 6th November 2012
__

Subhash Khot, Madhur Tulsiani, Pratik Worah#### The Complexity of Somewhat Approximation Resistant Predicates

Revisions: 1

__
TR12-152
| 7th November 2012
__

Anindya De, Ilias Diakonikolas, Rocco Servedio#### Inverse Problems in Approximate Uniform Generation

__
TR12-153
| 9th November 2012
__

Joshua Brody, Amit Chakrabarti, Ranganath Kondapally#### Certifying Equality With Limited Interaction

Revisions: 1

__
TR12-154
| 31st October 2012
__

Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah#### On the Power of Conditional Samples in Distribution Testing

Revisions: 1

__
TR12-155
| 15th November 2012
__

Clement Canonne, Dana Ron, Rocco Servedio#### Testing probability distributions using conditional samples

Revisions: 1

__
TR12-156
| 12th November 2012
__

Andrej Bogdanov, Chin Ho Lee#### Limits of provable security for homomorphic encryption

Revisions: 1

__
TR12-157
| 12th November 2012
__

Andrej Bogdanov, Chin Ho Lee#### On the depth complexity of homomorphic encryption schemes

Revisions: 2

__
TR12-158
| 14th November 2012
__

Aditya Bhaskara, Devendra Desai, Srikanth Srinivasan#### Optimal Hitting Sets for Combinatorial Shapes

__
TR12-159
| 20th November 2012
__

Eli Ben-Sasson, Michael Viderman#### A Combinatorial Characterization of smooth LTCs and Applications

__
TR12-160
| 20th November 2012
__

Frederic Green, Daniel Kreymer, Emanuele Viola#### Block-symmetric polynomials correlate with parity better than symmetric

__
TR12-161
| 20th November 2012
__

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria#### A Characterization of Tree-Like Resolution Size

__
TR12-162
| 26th October 2012
__

Hans-Joachim Boeckenhauer, Juraj Hromkovic, Dennis Komm, Sacha Krug, Jasmin Smula, Andreas Sprock#### The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity

Revisions: 1

__
TR12-163
| 24th November 2012
__

Avishay Tal#### Properties and Applications of Boolean Function Composition

__
TR12-164
| 17th November 2012
__

Rafail Ostrovsky, Ivan Visconti#### Simultaneous Resettability from Collision Resistance

__
TR12-165
| 19th November 2012
__

Martin Albrecht, Pooya Farshim, Jean-Charles Faugère, Gottfried Herold, Ludovic Perret#### Polly Cracker, Revisited

__
TR12-166
| 25th November 2012
__

Elad Haramaty, Madhu Sudan#### Deterministic Compression with Uncertain Priors

__
TR12-167
| 16th November 2012
__

Periklis Papakonstantinou, Charles Rackoff, Yevgeniy Vahlis#### How powerful are the DDH hard groups?

__
TR12-168
| 26th November 2012
__

Michael Viderman#### Strong LTCs with inverse polylogarithmic rate and soundness

__
TR12-169
| 22nd November 2012
__

Noga Alon, Santosh Vempala#### The Approximate Rank of a Matrix and its Algorithmic Applications

Revisions: 2

__
TR12-170
| 30th November 2012
__

Scott Aaronson, Travis Hance#### Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent

__
TR12-171
| 3rd December 2012
__

Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein#### From Information to Exact Communication

__
TR12-172
| 8th December 2012
__

Mahdi Cheraghchi, Anna Gal, Andrew Mills#### Correctness and Corruption of Locally Decodable Codes

__
TR12-173
| 8th December 2012
__

Kfir Barhum, Thomas Holenstein#### A Cookbook for Black-Box Separations and a Recipe for UOWHFs

__
TR12-174
| 12th December 2012
__

Anat Ganor, Ilan Komargodski, Ran Raz#### The Spectrum of Small DeMorgan Formulas

Revisions: 1

__
TR12-175
| 13th December 2012
__

James Cook, Omid Etesami, Rachel Miller, Luca Trevisan#### On the One-Way Function Candidate Proposed by Goldreich

Revisions: 1

__
TR12-176
| 14th December 2012
__

Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu#### Optimal Cuts and Partitions in Tree Metrics in Polynomial Time

__
TR12-177
| 19th December 2012
__

Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein#### Information lower bounds via self-reducibility

__
TR12-178
| 18th December 2012
__

Paul Beame, Raphael Clifford, Widad Machmouchi#### Sliding Windows With Limited Storage

Revisions: 1

__
TR12-179
| 13th December 2012
__

Joshua Brody, Harry Buhrman, Michal Koucky, Bruno Loff, Florian Speelman#### Towards a Reverse Newman's Theorem in Interactive Information Complexity

Revisions: 2

__
TR12-180
| 21st December 2012
__

Chaim Even-Zohar, Shachar Lovett#### The Freiman-Ruzsa Theorem in Finite Fields

__
TR12-181
| 20th December 2012
__

Anindya De, Ilias Diakonikolas, Rocco Servedio#### The Inverse Shapley Value Problem

__
TR12-182
| 24th December 2012
__

Itay Berman, Iftach Haitner, Ilan Komargodski, Moni Naor#### Hardness Preserving Reductions via Cuckoo Hashing

Revisions: 2

__
TR12-183
| 25th December 2012
__

András Salamon#### Streaming bounds from difference ramification

Revisions: 1
,
Comments: 1

__
TR12-184
| 26th December 2012
__

Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett#### Every locally characterized affine-invariant property is testable.

Revisions: 1

__
TR12-185
| 29th December 2012
__

Siu Man Chan, Aaron Potechin#### Tight Bounds for Monotone Switching Networks via Fourier Analysis

__
TR12-186
| 27th December 2012
__

Andreas Krebs, Nutan Limaye#### DLOGTIME-Proof Systems

Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett

Invariance with respect to linear or affine transformations of the domain is arguably the most common symmetry exhibited by natural algebraic properties. In this work, we show that any low complexity affine-invariant property of multivariate functions over finite fields is testable with a constant number of queries. This immediately reproves, ... more >>>

Akinori Kawachi, Benjamin Rossman, Osamu Watanabe

We propose an abstract framework for studying search-to-decision reductions for NP. Specifically, we study the following witness finding problem: for a hidden nonempty set $W\subseteq\{0,1\}^n$, the goal is to output a witness in $W$ with constant probability by making randomized queries of the form ``is $Q\cap W$ nonempty?''\ where $Q\subseteq\{0,1\}^n$. ... more >>>

Pratik Worah

Lov\'{a}sz and Schrijver introduced several lift and project methods for $0$-$1$ integer programs, now collectively known as Lov\'{a}sz-Schrijver ($LS$) hierarchies. Several lower bounds have since been proven for the rank of various linear programming relaxations in the $LS$ and $LS_+$ hierarchies. In this paper we investigate rank bounds in the ... more >>>

Marcos Villagra, Masaki Nakanishi, Shigeru Yamashita, Yasuhiko Nakashima

In this paper we study quantum nondeterminism in multiparty communication. There are three (possibly) different types of nondeterminism in quantum computation: i) strong, ii) weak with classical proofs, and iii) weak with quantum proofs. Here we focus on the first one. A strong quantum nondeterministic protocol accepts a correct input ... more >>>

Periklis Papakonstantinou, Guang Yang

Every pseudorandom generator is in particular a one-way function. If we only consider part of the output of the

pseudorandom generator is this still one-way? Here is a general setting formalizing this question. Suppose

$G:\{0,1\}^n\rightarrow \{0,1\}^{\ell(n)}$ is a pseudorandom generator with stretch $\ell(n)> n$. Let $M_R\in\{0,1\}^{m(n)\times \ell(n)}$ be a linear ...
more >>>

Gregory Valiant

Given a set of $n$ random $d$-dimensional boolean vectors with the promise that two of them are $\rho$-correlated with each other, how quickly can one find the two correlated vectors? We present a surprising and simple algorithm which, for any constant $\epsilon>0$ runs in (expected) time $d n^{\frac{3 \omega}{4}+\epsilon} poly(\frac{1}{\rho})< ... more >>>

Ruiwen Chen, Valentine Kabanets

A family of Boolean circuits $\{C_n\}_{n\geq 0}$ is called \emph{$\gamma(n)$-weakly uniform} if

there is a polynomial-time algorithm for deciding the direct-connection language of every $C_n$,

given \emph{advice} of size $\gamma(n)$. This is a relaxation of the usual notion of uniformity, which allows one

to interpolate between complete uniformity (when $\gamma(n)=0$) ...
more >>>

Marek Karpinski, Richard Schmied

We develop a new method for proving explicit approximation lower bounds for TSP problems with bounded metrics improving on the best up to now known bounds. They almost match the best known bounds for unbounded metric TSP problems. In particular, we prove the best known lower bound for TSP with ... more >>>

Prabhu Manyem, Julien Ugon

We survey research that studies the connection between the computational complexity

of optimization problems on the one hand, and the duality gap between the primal and

dual optimization problems on the other. To our knowledge, this is the first survey that

connects the two very important areas. We further look ...
more >>>

Shafi Goldwasser, Guy Rothblum

We address the following problem: how to execute any algorithm P, for an unbounded number of executions, in the presence of an adversary who observes partial information on the internal state of the computation during executions. The security guarantee is that the adversary learns nothing, beyond P's input/output behavior.

This ... more >>>

Nader Bshouty

We develop a new notion called {\it tester of a class $\cM$ of

functions} $f:\cA\to \cC$ that maps the elements $\bfa\in \cA$ in

the domain $\cA$ of the function to a finite number (the size of

the tester) of elements $\bfb_1,\ldots,\bfb_t$ in a smaller

sub-domain $\cB\subset \cA$ where the property ...
more >>>

Oded Goldreich

This note refers to the effect of the proximity parameter on the operation of (standard) property testers. Its bottom-line is that, except in pathological cases, the effect of the proximity parameter is restricted to determining the query complexity of the tester. The point is that, in non-pathological cases, the mapping ... more >>>

Tomas Feder, Carlos Subi

Given a graph $G$, we consider the problem of finding the largest set

of edge-disjoint triangles contained in $G$. We show that even the

simpler case of decomposing the edges of

a sparse split graph $G$ into edge-disjoint triangles

is NP-complete. We show next that the case of a general ...
more >>>

Johannes Mittmann, Nitin Saxena, Peter Scheiblechner

A set of multivariate polynomials, over a field of zero or large characteristic, can be tested for algebraic independence by the well-known Jacobian criterion. For fields of other characteristic $p>0$, there is no analogous characterization known. In this paper we give the first such criterion. Essentially, it boils down to ... more >>>

Albert Atserias, Anuj Dawar

Kolaitis and Kopparty have shown that for any first-order formula with

parity quantifiers over the language of graphs there is a family of

multi-variate polynomials of constant-degree that agree with the

formula on all but a $2^{-\Omega(n)}$-fraction of the graphs with $n$

vertices. The proof yields a bound on the ...
more >>>

Anindya De, Elchanan Mossel

The results of Raghavendra (2008) show that assuming Khot's Unique Games Conjecture (2002), for every constraint satisfaction problem there exists a generic semi-definite program that achieves the optimal approximation factor. This result is existential as it does not provide an explicit optimal rounding procedure nor does it allow to calculate ... more >>>

Venkatesan Guruswami, Srivatsan Narayanan

We prove the following results concerning the combinatorics of list decoding, motivated by the exponential gap between the known upper bound (of $O(1/\gamma)$) and lower bound (of $\Omega_p(\log (1/\gamma))$) for the list-size needed to decode up to radius $p$ with rate $\gamma$ away from capacity, i.e., $1-h(p)-\gamma$ (here $p\in (0,1/2)$ ... more >>>

Joerg Flum, Moritz Müller

We introduce a (new) notion of parameterized proof system. For parameterized versions of standard proof systems such as Extended Frege and Substitution Frege we compare their complexity with respect to parameterized simulations.

more >>>Eric Miles, Emanuele Viola

We study the complexity of black-box constructions of

pseudorandom functions (PRF) from one-way functions (OWF)

that are secure against non-uniform adversaries. We show

that if OWF do not exist, then given as an oracle any

(inefficient) hard-to-invert function, one can compute a

PRF in polynomial time with only $k(n)$ oracle ...
more >>>

Daniele Micciancio

We prove that the Shortest Vector Problem (SVP) on point lattices is NP-hard to approximate for any constant factor under polynomial time reverse unfaithful random reductions. These are probabilistic reductions with one-sided error that produce false negatives with small probability, but are guaranteed not to produce false positives regardless of ... more >>>

Oded Goldreich, Igor Shinkar

Loosely speaking, a proximity-oblivious (property) tester is a randomized algorithm that makes a constant number of queries to a tested object and distinguishes objects that have a predetermined property from those that lack it. Specifically, for some threshold probability $c$, objects having the property are accepted with probability at least ... more >>>

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler

The central goal of data stream algorithms is to process massive streams of data using sublinear storage space. Motivated by work in the database community on outsourcing database and data stream processing, we ask whether the space usage of such algorithms can be further reduced by enlisting a more powerful ... more >>>

Sophie Laplante, Virginie Lerays, Jérémie Roland

In communication complexity, two players each have an input and they wish to compute some function of the joint inputs. This has been the object of much study and a wide variety of lower bound methods have been introduced to address the problem of showing lower bounds on communication. Recently, ... more >>>

Scott Aaronson, Paul Christiano

Forty years ago, Wiesner pointed out that quantum mechanics raises the striking possibility of money that cannot be counterfeited according to the laws of physics. We propose the first quantum money scheme that is (1) public-key, meaning that anyone can verify a banknote as genuine, not only the bank that ... more >>>

Kord Eickmeyer, Kristoffer Arnsfelt Hansen, Elad Verbin

We consider the problem of approximating the minmax value of a multiplayer game in strategic form. We argue that in 3-player games with 0-1 payoffs, approximating the minmax value within an additive constant smaller than $\xi/2$, where $\xi = \frac{3-\sqrt5}{2} \approx 0.382$, is not possible by a polynomial time algorithm. ... more >>>

Thomas Watson

We prove that for every constant $k\ge 2$, every polynomial time bound $t$, and every polynomially small $\epsilon$, there exists a family of distributions on $k$ elements that can be sampled exactly in polynomial time but cannot be sampled within statistical distance $1-1/k-\epsilon$ in time $t$. Our proof involves reducing ... more >>>

Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis Papakonstantinou, Bangsheng Tang

A decade has passed since Alekhnovich and Razborov presented an algorithm that solves SAT on instances $\phi$ of size $n$ having tree-width $TW(\phi)$, using time (and space) bounded by $2^{O(TW(\phi))}n^{O(1)}$. Although there have been several papers over the ensuing years building on the work of Alekhnovich and Razborov there has ... more >>>

Eric Allender, George Davie, Luke Friedman, Samuel Hopkins, Iddo Tzameret

Can complexity classes be characterized in terms of efficient reducibility to the (undecidable) set of Kolmogorov-random strings? Although this might seem improbable, a series of papers has recently provided evidence that this may be the case. In particular, it is known that there is a class of problems $C$ defined ... more >>>

Shachar Lovett

The polynomial Freiman-Ruzsa conjecture is one of the important conjectures in additive combinatorics. It asserts than one can switch between combinatorial and algebraic notions of approximate subgroups with only a polynomial loss in the underlying parameters. This conjecture has also already found several applications in theoretical computer science. Recently, Tom ... more >>>

Deeparnab Chakrabarty, C. Seshadhri

The problem of monotonicity testing of the boolean hypercube is a classic well-studied, yet unsolved

question in property testing. We are given query access to $f:\{0,1\}^n \mapsto R$

(for some ordered range $R$). The boolean hypercube ${\cal B}^n$ has a natural partial order, denoted by $\prec$ (defined by the product ...
more >>>

Tom Gur, Omer Tamuz

Let $f:\{-1,1\}^n \to \mathbb{R}$ be a real function on the hypercube, given

by its discrete Fourier expansion, or, equivalently, represented as

a multilinear polynomial. We say that it is Boolean if its image is

in $\{-1,1\}$.

We show that every function on the hypercube with a ... more >>>

Sebastian Kuhnert, Johannes Köbler, Osamu Watanabe

We consider the problem of finding interval representations of graphs that additionally respect given interval lengths and/or pairwise intersection lengths, which are represented as weight functions on the vertices and edges, respectively. Pe'er and Shamir proved that the problem is NP-complete if only the former are given [SIAM J. Discr. ... more >>>

Ankit Gupta, Neeraj Kayal, Youming Qiao

Informally stated, we present here a randomized algorithm that given blackbox access to the polynomial $f$ computed by an unknown/hidden arithmetic formula $\phi$ reconstructs, on the average, an equivalent or smaller formula $\hat{\phi}$ in time polynomial in the size of its output $\hat{\phi}$.

Specifically, we consider arithmetic formulas wherein the ... more >>>

Abhishek Bhowmick, Zeev Dvir, Shachar Lovett

We prove new lower bounds on the encoding length of Matching Vector (MV) codes. These recently discovered families of Locally Decodable Codes (LDCs) originate in the works of Yekhanin [Yek] and Efremenko [Efr] and are the only known families of LDCs with a constant number of queries and sub-exponential encoding ... more >>>

Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler

(This is a revised version of work that was posted on arXiv in July 2010.)

We present sublinear-time (randomized) algorithms for finding simple cycles of length at least $k\geq3$ and tree-minors in bounded-degree graphs.

The complexity of these algorithms is related to the distance

of the graph from being ...
more >>>

Venkatesan Guruswami, Chaoping Xing

We give a new construction of algebraic codes which are efficiently list decodable from a fraction $1-R-\epsilon$ of adversarial errors where $R$ is the rate of the code, for any desired positive constant $\epsilon$. The worst-case list size output by the algorithm is $O(1/\epsilon)$, matching the existential bound for random ... more >>>

Alexander A. Sherstov

A basic question in any computational model is how to reliably compute a given function when the inputs or intermediate computations are subject to noise at a constant rate. Ideally, one would like to use at most a constant factor more resources compared to the noise-free case. This question has ... more >>>

Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jérémie Roland, David Xiao

We show that almost all known lower bound methods for communication complexity are also lower bounds for the information complexity. In particular, we define a relaxed version of the partition bound of Jain and Klauck and prove that it lower bounds the information complexity of any function. Our relaxed partition ... more >>>

Stasys Jukna

Motivated by its relation to the length of cutting plane proofs for the Maximum Biclique problem, here we consider the following communication game on a given graph G, known to both players. Let K be the maximal number of vertices in a complete bipartite subgraph of G (which is not ... more >>>

Sangxia Huang

In this paper, we study the approximability of Max CSP($P$) where $P$ is a Boolean predicate. We prove that assuming Khot's $d$-to-1 Conjecture, if the set of accepting inputs of $P$ strictly contains all inputs with even (or odd) parity, then it is NP-hard to approximate Max CSP($P$) better than ... more >>>

Stasys Jukna

We consider so-called ``incremental'' dynamic programming (DP) algorithms, and are interested in the number of subproblems produced by them. The standard DP algorithm for the n-dimensional Knapsack problem is incremental, and produces nK subproblems, where K is the capacity of the knapsack. We show that any incremental algorithm for this ... more >>>

Chris Beck, Russell Impagliazzo, Shachar Lovett

There has been considerable interest lately in the complexity of distributions. Recently, Lovett and Viola (CCC 2011) showed that the statistical distance between a uniform distribution over a good code, and any distribution which can be efficiently sampled by a small bounded-depth AC0 circuit, is inverse-polynomially close to one. That ... more >>>

Zvika Brakerski, Yael Tauman Kalai

In this work, we study the fundamental problem of constructing interactive protocols that are robust to noise, a problem that was originally considered in the seminal works of Schulman (FOCS '92, STOC '93), and has recently regained popularity. Robust interactive communication is the interactive analogue of error correcting codes: Given ... more >>>

Swastik Kopparty

We study the list-decodability of multiplicity codes. These codes, which are based on evaluations of high-degree polynomials and their derivatives, have rate approaching $1$ while simultaneously allowing for sublinear-time error-correction. In this paper, we show that multiplicity codes also admit powerful list-decoding and local list-decoding algorithms correcting a large fraction ... more >>>

Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer

Probabilistically-Checkable Proofs (PCPs) form the algorithmic core that enables succinct verification of long proofs/computations in many cryptographic constructions, such as succinct arguments and proof-carrying data.

Despite the wonderful asymptotic savings they bring, PCPs are also the infamous computational bottleneck preventing these cryptographic constructions from being used in practice. This reflects ... more >>>

Madhu Sudan, Noga Ron-Zewi

Over a finite field $\F_q$ the $(n,d,q)$-Reed-Muller code is the code given by evaluations of $n$-variate polynomials of total degree at most $d$ on all points (of $\F_q^n$). The task of testing if a function $f:\F_q^n \to \F_q$ is close to a codeword of an $(n,d,q)$-Reed-Muller code has been of ... more >>>

Emanuele Viola

We obtain the first deterministic randomness extractors

for $n$-bit sources with min-entropy $\ge n^{1-\alpha}$

generated (or sampled) by single-tape Turing machines

running in time $n^{2-16 \alpha}$, for all sufficiently

small $\alpha > 0$. We also show that such machines

cannot sample a uniform $n$-bit input to the Inner

Product function ...
more >>>

Alan Guo, Madhu Sudan

We prove that the class of locally testable affine-invariant properties is closed under sums, intersections and "lifts". The sum and intersection are two natural operations on linear spaces of functions, where the sum of two properties is simply their sum as a vector space. The "lift" is a less natural ... more >>>

Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan

We show that sparse affine-invariant linear properties over arbitrary finite fields are locally testable with a constant number of queries. Given a finite field ${\mathbb{F}}_q$ and an extension field ${\mathbb{F}}_{q^n}$, a property is a set of functions mapping ${\mathbb{F}}_{q^n}$ to ${\mathbb{F}}_q$. The property is said to be affine-invariant if it ... more >>>

Avraham Ben-Aroya, Gil Cohen

A $(k,\epsilon)$-biased sample space is a distribution over $\{0,1\}^n$ that $\epsilon$-fools every nonempty linear test of size at most $k$. Since they were introduced by Naor and Naor [SIAM J. Computing, 1993], these sample spaces have become a central notion in theoretical computer science with a variety of applications.

When ... more >>>

Dmitry Gavinsky, Shachar Lovett, Michael Saks, Srikanth Srinivasan

We prove a Chernoff-like large deviation bound on the sum of non-independent random variables that have the following dependence structure. The variables $Y_1,\ldots,Y_r$ are arbitrary Boolean functions of independent random variables $X_1,\ldots,X_m$, modulo a restriction that every $X_i$ influences at most $k$ of the variables $Y_1,\ldots,Y_r$.

more >>>Mohammad Mahmoody, David Xiao

A Zero-Knowledge PCP (ZK-PCP) is a randomized PCP such that the view of any (perhaps cheating) efficient verifier can be efficiently simulated up to small statistical distance. Kilian, Petrank, and Tardos (STOC '97) constructed ZK-PCPs for all languages in $NEXP$. Ishai, Mahmoody, and Sahai (TCC '12), motivated by cryptographic applications, ... more >>>

Ankur Moitra

Here, we give an algorithm for deciding if the nonnegative rank of a matrix $M$ of dimension $m \times n$ is at most $r$ which runs in time $(nm)^{O(r^2)}$. This is the first exact algorithm that runs in time singly-exponential in $r$. This algorithm (and earlier algorithms) are built on ... more >>>

Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff

This paper is motivated by a conjecture that BPP can be characterized in terms of polynomial-time nonadaptive reductions to the set of Kolmogorov-random strings. In this paper we show that an approach laid out by [Allender et al] to settle this conjecture cannot succeed without significant alteration, but that it ... more >>>

Reut Levi, Dana Ron, Ronitt Rubinfeld

We consider the problem of testing a basic property of collections of distributions: having similar means. Namely, the algorithm should accept collections of distributions in which all distributions have means that do not differ by more than some given parameter, and should reject collections that are relatively far from having ... more >>>

Rocco Servedio, Li-Yang Tan, Justin Thaler

We study the challenging problem of learning decision lists attribute-efficiently, giving both positive and negative results.

Our main positive result is a new tradeoff between the running time and mistake bound for learning length-$k$ decision lists over $n$ Boolean variables. When the allowed running time is relatively high, our new ... more >>>

Russell Impagliazzo, Raghu Meka, David Zuckerman

One powerful theme in complexity theory and pseudorandomness in the past few decades has been the use of lower bounds to give pseudorandom generators (PRGs). However, the general results using this hardness vs. randomness paradigm suffer a quantitative loss in parameters, and hence do not give nontrivial implications for models ... more >>>

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz

Yao's garbled circuit construction transforms a boolean circuit $C:\{0,1\}^n\to\{0,1\}^m$

into a ``garbled circuit'' $\hat{C}$ along with $n$ pairs of $k$-bit keys, one for each

input bit, such that $\hat{C}$ together with the $n$ keys

corresponding to an input $x$ reveal $C(x)$ and no additional information about $x$.

The garbled circuit ...
more >>>

Rahul Santhanam, Ryan Williams

We explore the relationships between circuit complexity, the complexity of generating circuits, and circuit-analysis algorithms. Our results can be roughly divided into three parts:

1. Lower Bounds Against Medium-Uniform Circuits. Informally, a circuit class is ``medium uniform'' if it can be generated by an algorithmic process that is somewhat complex ... more >>>

Parikshit Gopalan, Raghu Meka, Omer Reingold

Given a DNF formula $f$ on $n$ variables, the two natural size measures are the number of terms or size $s(f)$, and the maximum width of a term $w(f)$. It is folklore that short DNF formulas can be made narrow. We prove a converse, showing that narrow formulas can be ... more >>>

Pavel Hrubes, Amir Yehudayoff

We give an example of a non-commutative monotone polynomial f which can be computed by a polynomial-size non-commutative formula, but every monotone non-commutative circuit computing f must have an exponential size. In the non-commutative setting this gives, a fortiori, an exponential separation between monotone and general formulas, monotone and general ... more >>>

Ilan Komargodski, Ran Raz

We give an explicit function $h:\{0,1\}^n\to\{0,1\}$ such that any deMorgan formula of size $O(n^{2.499})$ agrees with $h$ on at most $\frac{1}{2} + \epsilon$ fraction of the inputs, where $\epsilon$ is exponentially small (i.e. $\epsilon = 2^{-n^{\Omega(1)}}$). Previous lower bounds for formula size were obtained for exact computation.

The same ... more >>>

Raghav Kulkarni, Miklos Santha

Let $\mathcal{M}$ be a bridgeless matroid on ground set $\{1,\ldots, n\}$ and $f_{\mathcal{M}}: \{0,1\}^n \to \{0, 1\}$ be the indicator function of its independent sets. A folklore fact is that $f_\mathcal{M}$ is ``evasive," i.e., $D(f_\mathcal{M}) = n$ where $D(f)$ denotes the deterministic decision tree complexity of $f.$ Here we prove ... more >>>

Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, Ying Xiao

We develop a framework for proving lower bounds on computational problems over distributions, including optimization and unsupervised learning. Our framework is based on defining a restricted class of algorithms, called statistical algorithms, that instead of accessing samples from the input distribution can only obtain an estimate of the expectation ... more >>>

Mohammad Mahmoody, Hemanta Maji, Manoj Prabhakaran

The seminal result of Impagliazzo and Rudich (STOC 1989) gave a black-box separation between one-way functions and public-key encryption: informally, a public-key encryption scheme cannot be constructed using one-way functions as the sole source of computational hardness. In addition, this implied a black-box separation between one-way functions and protocols for ... more >>>

Jinyu Huang

Let two linear matroids have the same rank in matroid intersection.

A maximum linear matroid intersection (maximum linear matroid parity

set) is called a basic matroid intersection (basic matroid parity

set), if its size is the rank of the matroid. We present that

enumerating all basic matroid intersections (basic matroid ...
more >>>

Xiaohui Bei, Ning Chen, Shengyu Zhang

Motivated by certain applications from physics, biochemistry, economics, and computer science in which the objects under investigation are unknown or not directly accessible because of various limitations, we propose a trial-and-error model to examine search problems with unknown inputs. Given a search problem with a hidden input, we are asked ... more >>>

Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena

The problem of finding a nontrivial factor of a polynomial $f(x)$ over a finite field $\mathbb{F}_q$ has many known efficient, but randomized, algorithms. The deterministic complexity of this problem is a famous open question even assuming the generalized Riemann hypothesis (GRH). In this work we improve the state of the ... more >>>

Lakhdar Saïs, Mohand-Saïd Hacid, francois hantry

We show that (1) the Minimal False QCNF search problem (MF-search) and

the Minimal Unsatisfiable LTL formula search problem (MU-search) are FPSPACE complete because of the very expressive power of QBF/LTL, (2) we extend the PSPACE-hardness of the MF decision problem to the MU decision problem. As a consequence, we ...
more >>>

Thomas Watson

Goldreich, Sahai, and Vadhan (CRYPTO 1999) proved that the promise problem for estimating the Shannon entropy of a distribution sampled by a given circuit is NISZK-complete. We consider the analogous problem for estimating the min-entropy and prove that it is SBP-complete, even when restricted to 3-local samplers. For logarithmic-space samplers, ... more >>>

Kazuhisa Seto, Suguru Tamaki

We present a moderately exponential time algorithm for the satisfiability of Boolean formulas over the full binary basis.

For formulas of size at most $cn$, our algorithm runs in time $2^{(1-\mu_c)n}$ for some constant $\mu_c>0$.

As a byproduct of the running time analysis of our algorithm,

we get strong ...
more >>>

Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco Servedio

The \emph{Chow parameters} of a Boolean function $f: \{-1,1\}^n \to \{-1,1\}$ are its $n+1$ degree-0 and degree-1 Fourier coefficients. It has been known since 1961 \cite{Chow:61, Tannenbaum:61} that the (exact values of the) Chow parameters of any linear threshold function $f$ uniquely specify $f$ within the space of all Boolean ... more >>>

Venkatesan Guruswami, Carol Wang

Folded Reed-Solomon codes are an explicit family of codes that achieve the optimal trade-off between rate and list error-correction capability. Specifically, for any $\epsilon > 0$, Guruswami and Rudra presented an $n^{O(1/\epsilon)}$ time algorithm to list decode appropriate folded RS codes of rate $R$ from a fraction $1-R-\epsilon$ of ... more >>>

Venkatesan Guruswami, Yuan Zhou

A theorem of Håstad shows that for every constraint satisfaction problem (CSP) over a fixed size domain, instances where each variable appears in at most $O(1)$ constraints admit a non-trivial approximation algorithm, in the sense that one can beat (by an additive constant) the approximation ratio achieved by the naive ... more >>>

Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova

We study local filters for two properties of functions $f:\B^d\to \mathbb{R}$: the Lipschitz property and monotonicity. A local filter with additive error $a$ is a randomized algorithm that is given black-box access to a function $f$ and a query point $x$ in the domain of $f$. Its output is a ... more >>>

Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova

A function $f(x_1, ... , x_d)$, where each input is an integer from 1 to $n$ and output is a real number, is Lipschitz if changing one of the inputs by 1 changes the output by at most 1. In other words, Lipschitz functions are not very sensitive to small ... more >>>

Chiranjit Chakraborty, Rahul Santhanam

We define instance compressibility for parametric problems in PH and PSPACE. We observe that

the problem \Sigma_{i}CircuitSAT of deciding satisfiability of a quantified Boolean circuit with i-1 alternations of quantifiers starting with an existential uantifier is complete for parametric problems in \Sigma_{i}^{p} with respect to W-reductions, and that analogously ... more >>>

Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Yadu Vasudev

We study optimization versions of Graph Isomorphism. Given two graphs $G_1,G_2$, we are interested in finding a bijection $\pi$ from $V(G_1)$ to $V(G_2)$ that maximizes the number of matches (edges mapped to edges or non-edges mapped to non-edges). We give an $n^{O(\log n)}$ time approximation scheme that for any constant ... more >>>

Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer

In this paper we initiate the study of proof systems where verification of proofs proceeds by NC0 circuits. We investigate the question which languages admit proof systems in this very restricted model. Formulated alternatively, we ask which languages can be enumerated by NC0 functions. Our results show that the answer ... more >>>

Baris Aydinlioglu, Dieter van Melkebeek

In several settings derandomization is known to follow from circuit lower bounds that themselves are equivalent to the existence of pseudorandom generators. This leaves open the question whether derandomization implies the circuit lower bounds that are known to imply it, i.e., whether the ability to derandomize in *any* way implies ... more >>>

Neeraj Kayal

In this work we consider representations of multivariate polynomials in $F[x]$ of the form $ f(x) = Q_1(x)^{e_1} + Q_2(x)^{e_2} + ... + Q_s(x)^{e_s},$ where the $e_i$'s are positive integers and the $Q_i$'s are arbitary multivariate polynomials of bounded degree. We give an explicit $n$-variate polynomial $f$ of degree $n$ ... more >>>

Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker

We prove that a random linear code over $\mathbb{F}_q$, with probability arbitrarily close to $1$, is list decodable at radius $1-1/q-\epsilon$ with list size $L=O(1/\epsilon^2)$ and rate $R=\Omega_q(\epsilon^2/(\log^3(1/\epsilon)))$. Up to the polylogarithmic factor in $1/\epsilon$ and constant factors depending on $q$, this matches the lower bound $L=\Omega_q(1/\epsilon^2)$ for the list ... more >>>

Thomas Steinke

We exhibit an explicit pseudorandom generator that stretches an $O \left( \left( w^4 \log w + \log (1/\varepsilon) \right) \cdot \log n \right)$-bit random seed to $n$ pseudorandom bits that cannot be distinguished from truly random bits by a permutation branching program of width $w$ with probability more than $\varepsilon$. ... more >>>

Rahul Santhanam

I discuss recent progress in developing and exploiting connections between

SAT algorithms and circuit lower bounds. The centrepiece of the article is

Williams' proof that $NEXP \not \subseteq ACC^0$, which proceeds via a new

algorithm for $ACC^0$-SAT beating brute-force search. His result exploits

a formal connection from non-trivial SAT algorithms ...
more >>>

Tsuyoshi Ito, Thomas Vidick

We prove a strong limitation on the ability of entangled provers to collude in a multiplayer game. Our main result is the first nontrivial lower bound on the class MIP* of languages having multi-prover interactive proofs with entangled provers; namely MIP* contains NEXP, the class of languages decidable in non-deterministic ... more >>>

Shlomi Dolev, Nova Fandina, Dan Gutfreund

Finding a problem that is both hard to solve and hard to solve on many instances is a long standing issue

in theoretical computer science.

In this work, we prove that the Succinct Permanent $\bmod \; p$ is $NEXP$

time hard in the worst case (via randomized polynomial time ...
more >>>

Peyman Afshani, Manindra Agrawal, Doerr Benjamin, Winzen Carola, Kasper Green Larsen, Kurt Mehlhorn

We study the $\leadingones$ game, a Mastermind-type guessing game first

regarded as a test case in the complexity theory of randomized search

heuristics. The first player, Carole, secretly chooses a string $z \in \{0,1\}^n$ and a

permutation $\pi$ of $[n]$.

The goal of the second player, Paul, is to ...
more >>>

Irit Dinur, Gillat Kol

We study the covering complexity of constraint satisfaction problems (CSPs). The covering number of a CSP instance C, denoted $\nu(C)$, is the smallest number of assignments to the variables, such that each constraint is satisfied by at least one of the assignments. This covering notion describes situations in which we ... more >>>

Meena Boppana

The Sensitivity Conjecture, posed in 1994, states that the fundamental measures known as the sensitivity and block sensitivity of a Boolean function $f$, $s(f)$ and $bs(f)$ respectively, are polynomially related. It is known that $bs(f)$ is polynomially related to important measures in computer science including the decision-tree depth, polynomial degree, ... more >>>

Michael Blondin, Andreas Krebs, Pierre McKenzie

The problem of determining whether several finite automata accept a word in common is closely related to the well-studied membership problem in transformation monoids. We raise the issue of limiting the number of final states in the automata intersection problem. For automata with two final states, we show the problem ... more >>>

Abuzer Yakaryilmaz

Condon and Lipton (FOCS 1989) showed that the class of languages having a space-bounded interactive proof system (IPS) is a proper subset of decidable languages, where the verifier is a probabilistic Turing machine. In this paper, we show that if we use architecturally restricted verifiers instead of restricting the working ... more >>>

Pavol Duris

In this paper we deal with one-way multi-head data-independent finite automata. A $k$-head finite automaton $A$ is data-independent, if the position of every head $i$ after step $t$ in the computation on an input $w$ is a function that depends only on the length of the input $w$, on $i$ ... more >>>

Charanjit Jutla, Vijay Kumar, Atri Rudra

We study the circuit complexity of linear transformations between Galois fields GF(2^{mn}) and their isomorphic composite fields GF((2^{m})^n). For such a transformation, we show a lower bound of \Omega(mn) on the number of gates required in any circuit consisting of constant-fan-in XOR gates, except for a class of transformations between ... more >>>

Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva

Suppose we are given an oracle that claims to approximate the permanent for most matrices $X$, where $X$ is chosen from the Gaussian ensemble (the matrix entries are i.i.d. univariate complex Gaussians). Can we test that the oracle satisfies this claim? This paper gives a polynomial-time algorithm for the task.

... more >>>Avraham Ben-Aroya, Igor Shinkar

A subspace-evasive set over a field ${\mathbb F}$ is a subset of ${\mathbb F}^n$ that has small intersection with any low-dimensional affine subspace of ${\mathbb F}^n$. Interest in subspace evasive sets began in the work of Pudlák and Rödl (Quaderni di Matematica 2004). More recently, Guruswami (CCC 2011) showed that ... more >>>

Albert Atserias, Sergi Oliva

Tree-width is a well-studied parameter of structures that measures their similarity to a tree. Many important NP-complete problems, such as Boolean satisfiability (SAT), are tractable on bounded tree-width instances. In this paper we focus on the canonical PSPACE-complete problem QBF, the fully-quantified version of SAT. It was shown by Pan ... more >>>

Andrej Bogdanov, Siyao Guo

We consider the problem of extracting entropy by sparse transformations, namely functions with a small number of overall input-output dependencies. In contrast to previous works, we seek extractors for essentially all the entropy without any assumption on the underlying distribution beyond a min-entropy requirement. We give two simple constructions of ... more >>>

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

Agrawal and Vinay (FOCS 2008) have recently shown that an exponential lower bound for depth four homogeneous circuits with bottom layer of $\times$ gates having sublinear fanin translates to an exponential lower bound for a general arithmetic circuit computing the permanent. Motivated by this, we examine the complexity of computing ... more >>>

Nikos Leonardos

We prove that the randomized decision tree complexity of the recursive majority-of-three is $\Omega(2.6^d)$, where $d$ is the depth of the recursion. The proof is by a bottom up induction, which is same in spirit as the one in the proof of Saks and Wigderson in their FOCS 1986 paper ... more >>>

Tomas Jirotka

The thesis summarizes known results in the field of NP search problems. We discuss the complexity of integer factoring in detail, and we propose new results which place the problem in known classes and aim to separate it from PLS in some sense. Furthermore, we define several new search problems.

more >>>Oded Goldreich, Shafi Goldwasser, Dana Ron

We study the possibilities and limitations

of pseudodeterministic algorithms,

a notion put forward by Gat and Goldwasser (2011).

These are probabilistic algorithms that solve search problems

such that on each input, with high probability, they output

the same solution, which may be thought of as a canonical solution.

We consider ...
more >>>

Swastik Kopparty, Srikanth Srinivasan

In this paper, we introduce and develop the method of certifying polynomials for proving $\mathrm{AC}^0[\oplus]$ circuit lower bounds.

We use this method to show that Approximate Majority cannot be computed by $\mathrm{AC}^0[\oplus]$ circuits of size $n^{1+o(1)}$. This implies a separation between the power of $\mathrm{AC}^0[\oplus]$ circuits of near-linear size and ... more >>>

Arnab Bhattacharyya, Yuichi Yoshida

Given an instance $\mathcal{I}$ of a CSP, a tester for $\mathcal{I}$ distinguishes assignments satisfying $\mathcal{I}$ from those which are far from any assignment satisfying $\mathcal{I}$. The efficiency of a tester is measured by its query complexity, the number of variable assignments queried by the algorithm. In this paper, we characterize ... more >>>

Matthew Franklin, Ran Gelles, Rafail Ostrovsky, Leonard Schulman

Error correction and message authentication are well studied in the literature, and various efficient solutions have been suggested and analyzed. This is however not the case for data streams in which the message is very long, possibly infinite, and not known in advance to the sender. Trivial solutions for error-correcting ... more >>>

Madhur Tulsiani, Pratik Worah

We consider the complexity of LS$_+$ refutations of unsatisfiable instances of Constraint Satisfaction Problems (CSPs) when the underlying predicate supports a pairwise independent distribution on its satisfying assignments. This is the most general condition on the predicates under which the corresponding MAX-CSP problem is known to be approximation resistant.

We ... more >>>

Alan Guo, Madhu Sudan

In this work we explore error-correcting codes derived from

the ``lifting'' of ``affine-invariant'' codes.

Affine-invariant codes are simply linear codes whose coordinates

are a vector space over a field and which are invariant under

affine-transformations of the coordinate space. Lifting takes codes

defined over a vector space of small dimension ...
more >>>

Brendan Juba, Ryan Williams

We consider a model of teaching in which the learners are consistent and have bounded state, but are otherwise arbitrary. The teacher is non-interactive and ``massively open'': the teacher broadcasts a sequence of examples of an arbitrary target concept, intended for every possible on-line learning algorithm to learn from. We ... more >>>

Arkadev Chattopadhyay, Rahul Santhanam

We formulate a new connection between instance compressibility \cite{Harnik-Naor10}), where the compressor uses circuits from a class $\C$, and correlation with

circuits in $\C$. We use this connection to prove the first lower bounds

on general probabilistic multi-round instance compression. We show that there

is no

probabilistic multi-round ...
more >>>

Subhash Khot, Muli Safra, Madhur Tulsiani

We construct a PCP based on the hyper-graph linearity test with 3 free queries. It has near-perfect completeness and soundness strictly less than 1/8. Such a PCP was known before only assuming the Unique Games Conjecture, albeit with soundness arbitrarily close to 1/16.

At a technical level, our ...
more >>>

Siu On Chan

We show optimal (up to constant factor) NP-hardness for Max-k-CSP over any domain,

whenever k is larger than the domain size. This follows from our main result concerning predicates

over abelian groups. We show that a predicate is approximation resistant if it contains a subgroup that

is ...
more >>>

Venkatesan Guruswami, Ali Kemal Sinop

Convex relaxations based on different hierarchies of

linear/semi-definite programs have been used recently to devise

approximation algorithms for various optimization problems. The

approximation guarantee of these algorithms improves with the number

of {\em rounds} $r$ in the hierarchy, though the complexity of solving

(or even writing down the solution for) ...
more >>>

Andrew Drucker

Given an instance of a hard decision problem, a limited goal is to $compress$ that instance into a smaller, equivalent instance of a second problem. As one example, consider the problem where, given Boolean formulas $\psi^1, \ldots, \psi^t$, we must determine if at least one $\psi^j$ is satisfiable. An $OR-compression ... more >>>

Manindra Agrawal, Chandan Saha, Nitin Saxena

We call a depth-$4$ formula $C$ $\textit{ set-depth-4}$ if there exists a (unknown) partition $X_1\sqcup\cdots\sqcup X_d$ of the variable indices $[n]$ that the top product layer respects, i.e. $C(\mathbf{x})=\sum_{i=1}^k {\prod_{j=1}^{d} {f_{i,j}(\mathbf{x}_{X_j})}}$ $ ,$ where $f_{i,j}$ is a $\textit{sparse}$ polynomial in $\mathbb{F}[\mathbf{x}_{X_j}]$. Extending this definition to any depth - we call ... more >>>

Mikhail Anokhin

We construct a provably pseudo-free family of finite computational groups under the general integer factoring intractability assumption. Moreover, this family has exponential size. But each element of a group in our pseudo-free family is represented by many bit strings.

more >>>Michael Forbes, Amir Shpilka

We study the problem of obtaining efficient, deterministic, black-box polynomial identity testing (PIT) algorithms for read-once oblivious algebraic branching programs (ABPs). This class has an efficient, deterministic, white-box polynomial identity testing algorithm (due to Raz and Shpilka), but prior to this work had no known such black-box algorithm. Here we ... more >>>

Luca Trevisan

We describe a new pseudorandom generator for AC0. Our generator $\epsilon$-fools circuits of depth $d$ and size $M$ and uses a seed of length $\tilde O( \log^{d+4} M/\epsilon)$. The previous best construction for $d \geq 3$ was due to Nisan, and had seed length $O(\log^{2d+6} M/\epsilon)$.

A seed length of ...
more >>>

Loïck Magnin, Jérémie Roland

The polynomial method and the adversary method are the two main techniques to prove lower bounds on quantum query complexity, and they have so far been considered as unrelated approaches. Here, we show an explicit reduction from the polynomial method to the multiplicative adversary method. The proof goes by extending ... more >>>

Avi Wigderson, Amir Yehudayoff

We study several problems in which an {\em unknown} distribution over an {\em unknown} population of vectors needs to be recovered from partial or noisy samples, each of which nearly completely erases or obliterates the original vector. For example, consider a distribution $p$ over a population $V \subseteq \{0,1\}^n$. A ... more >>>

Ilario Bonacina, Nicola Galesi

We devise a new combinatorial characterization for proving space lower bounds in algebraic systems like Polynomial Calculus (Pc) and Polynomial Calculus with Resolution (Pcr). Our method can be thought as a Spoiler-Duplicator game, which is capturing boolean reasoning on polynomials instead that clauses as in the case of Resolution. Hence, ... more >>>

Boaz Barak

In this survey, I discuss the general question of what evidence can we use to predict the answer for open questions in computational complexity, as well as the concrete evidence currently known for two conjectures: Khot's Unique Games Conjecture and Feige's Random 3SAT Hypothesis.

Pavel Hrubes

Koiran's real $\tau$-conjecture asserts that if a non-zero real polynomial can be written as $f=\sum_{i=1}^{p}\prod_{j=1}^{q}f_{ij},$

where each $f_{ij}$ contains at most $k$ monomials, then the number of distinct real roots of $f$ is polynomial in $pqk$. We show that the conjecture implies quite a strong property of the ...
more >>>

Giorgio Ausiello, Francesco Cristiano, Luigi Laura

We investigate the complexity of the syntactic isomorphism problem of CNF Boolean Formulas (CSFI): given two CNF Boolean formulas $\varphi(a_{1},\ldots,a_{n})$ and $\varphi(b_{1},\ldots,b_{n})$ decide whether there exists a permutation of clauses, a permutation of literals and a bijection between their variables such that $\varphi(a_{1},\ldots,a_{n})$ and $\varphi(b_{1},\ldots,b_{n})$ become syntactically identical. We first ... more >>>

Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan

We present an iterative approach to constructing pseudorandom generators, based on the repeated application of mild pseudorandom restrictions. We use this template to construct pseudorandom generators for combinatorial rectangles and read-once CNFs and a hitting set generator for width-3 branching programs, all of which achieve near optimal seed-length even in ... more >>>

Massimo Lauria

Ramsey Theorem is a cornerstone of combinatorics and logic. In its

simplest formulation it says that there is a function $r$ such that

any simple graph with $r(k,s)$ vertices contains either a clique of

size $k$ or an independent set of size $s$. We study the complexity

of proving upper ...
more >>>

Zahra Jafargholi, Hamidreza Jahanjou, Eric Miles, Jaideep Ramachandran, Emanuele Viola

Common presentations of the NP-completeness of SAT suffer

from two drawbacks which hinder the scope of this

flagship result. First, they do not apply to machines

equipped with random-access memory, also known as

direct-access memory, even though this feature is

critical in basic algorithms. Second, they incur a

quadratic blow-up ...
more >>>

Shiva Kintali, Sinziana Munteanu

We present a logspace algorithm to compute path decompositions of bounded pathwidth graphs, thus settling its complexity. Prior to our work, the best known upper bound to compute such decompositions was linear time. We also show that deciding if the pathwidth of a graph is at most a given constant ... more >>>

Eshan Chattopadhyay, Adam Klivans, Pravesh Kothari

Let $X \subseteq \mathbb{R}^{n}$ and let ${\mathcal C}$ be a class of functions mapping $\mathbb{R}^{n} \rightarrow \{-1,1\}.$ The famous VC-Theorem states that a random subset $S$ of $X$ of size $O(\frac{d}{\epsilon^{2}} \log \frac{d}{\epsilon})$, where $d$ is the VC-Dimension of ${\mathcal C}$, is (with constant probability) an $\epsilon$-approximation for ${\mathcal C}$ ... more >>>

Nathanaël François, Frederic Magniez

This work is in the line of designing efficient checkers for testing the reliability of some massive data structures. Given a sequential access to the insert/extract operations on such a structure, one would like to decide, a posteriori only, if it corresponds to the evolution of a reliable structure. In ... more >>>

Iftach Haitner, Eran Omri, Hila Zarosim

In the random oracle model, the parties are given oracle access to a random member of

a (typically huge) function family, and are assumed to have unbounded computational power

(though they can only make a bounded number of oracle queries). This model provides powerful

properties that allow proving the security ...
more >>>

Abuzer Yakaryilmaz

We introduce a new public quantum interactive proof system, namely qAM, by augmenting the verifier with a fixed-size quantum register in Arthur-Merlin game. We focus on space-bounded verifiers, and compare our new public system with private-coin interactive proof (IP) system in the same space bounds. We show that qAM systems ... more >>>

Mark Braverman, Ankur Moitra

We prove an unconditional lower bound that any linear program that achieves an $O(n^{1-\epsilon})$ approximation for clique has size $2^{\Omega(n^\epsilon)}$. There has been considerable recent interest in proving unconditional lower bounds against any linear program. Fiorini et al proved that there is no polynomial sized linear program for traveling salesman. ... more >>>

Yuval Filmus, Massimo Lauria, Jakob Nordström, Noga Ron-Zewi, Neil Thapen

During the last decade, an active line of research in proof complexity has been to study space complexity and time-space trade-offs for proofs. Besides being a natural complexity measure of intrinsic interest, space is also an important issue in SAT solving, and so research has mostly focused on weak systems ... more >>>

Noga Alon, Gil Cohen

We introduce a class of polynomials, which we call \emph{subspace polynomials} and show that the problem of explicitly constructing a rigid matrix can be reduced to the problem of explicitly constructing a small hitting set for this class. We prove that small-bias sets are hitting sets for the class of ... more >>>

Alexander Razborov, Emanuele Viola

We highlight the challenge of proving correlation bounds

between boolean functions and integer-valued polynomials,

where any non-boolean output counts against correlation.

We prove that integer-valued polynomials of degree $\frac 12

\log_2 \log_2 n$ have zero correlation with parity. Such a

result is false for modular and threshold polynomials.

Its proof ...
more >>>

Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, Julia Wolf

We give new combinatorial proofs of known almost-periodicity results for sumsets of sets with small doubling in the spirit of Croot and Sisask [Geom. Funct. Anal. 2010], whose almost-periodicity lemma has had far-reaching implications in additive combinatorics. We provide an alternative (and $L^p$-norm free) point of view, which allows for ... more >>>

Dan Boneh, Mark Zhandry

We construct the first Message Authentication Codes (MACs) that are existentially unforgeable against a quantum chosen message attack. These chosen message attacks model a quantum adversary’s ability to obtain the MAC on a superposition of messages of its choice. We begin by showing that a quantum secure PRF is sufficient ... more >>>

Johan Håstad

We prove that the correlation of a depth-$d$

unbounded fanin circuit of size $S$ with parity

of $n$ variables is at most $2^{-\Omega(n/(\log S)^{d-1})}$.

Zeev Dvir, Shubhangi Saraf, Avi Wigderson

We study the rank of complex sparse matrices in which the supports of different columns have small intersections. The rank of these matrices, called design matrices, was the focus of a recent work by Barak et. al. (BDWY11) in which they were used to answer questions regarding point configurations. In ... more >>>

Albert Ai, Zeev Dvir, Shubhangi Saraf, Avi Wigderson

We study questions in incidence geometry where the precise position of points is `blurry' (e.g. due to noise, inaccuracy or error). Thus lines are replaced by narrow tubes, and more generally affine subspaces are replaced by their small neighborhood. We show that the presence of a sufficiently large number of ... more >>>

Mark Zhandry

In the presence of a quantum adversary, there are two possible definitions of security for a pseudorandom function. The first, which we call standard-security, allows the adversary to be quantum, but requires queries to the function to be classical. The second, quantum-security, allows the adversary to query the function on ... more >>>

Dmitry Itsykson, Dmitry Sokolov

The paper is devoted to lower bounds on the time complexity of DPLL algorithms that solve the satisfiability problem using a splitting strategy. Exponential lower bounds on the running time of DPLL algorithms on unsatisfiable formulas follow from the lower bounds for resolution proofs. Lower bounds on satisfiable instances are ... more >>>

Markus Bläser

We consider the complexity of computing the determinant over arbitrary finite-dimensional algebras. We first consider the case that $A$ is fixed. We obtain the following dichotomy: If $A/rad(A)$ is noncommutative, then computing the determinant over $A$ is hard. ``Hard'' here means $\#P$-hard over fields of characteristic $0$ and $ModP_p$-hard over ... more >>>

Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff

We give exponentially small upper bounds on the success probability for computing the direct product of any function over any distribution using a communication protocol. Let suc(?,f,C) denote the maximum success probability of a 2-party communication protocol for computing f(x,y) with C bits of communication, when the inputs (x,y) are ... more >>>

Rocco Servedio, Emanuele Viola

We highlight the special case of Valiant's rigidity

problem in which the low-rank matrices are truth-tables

of sparse polynomials. We show that progress on this

special case entails that Inner Product is not computable

by small $\acz$ circuits with one layer of parity gates

close to the inputs. We then ...
more >>>

Cenny Wenner

Håstad established that any predicate $P \subseteq \{0,1\}^m$ containing parity of width at least three is approximation resistant for almost satisfiable instances. However, in comparison to for example the approximation hardness of Max-3SAT, the result only holds for almost satisfiable instances. This limitation was addressed by O'Donnell, Wu, and Huang ... more >>>

Venkatesan Guruswami, Chaoping Xing

We consider Reed-Solomon (RS) codes whose evaluation points belong to a subfield, and give a linear-algebraic list decoding algorithm that can correct a fraction of errors approaching the code distance, while pinning down the candidate messages to a well-structured affine space of dimension a constant factor smaller than the code ... more >>>

Xin Li

We study the problem of constructing explicit extractors for independent general weak random sources. For weak sources on $n$ bits with min-entropy $k$, perviously the best known extractor needs to use at least $\frac{\log n}{\log k}$ independent sources \cite{Rao06, BarakRSW06}. In this paper we give a new extractor that only ... more >>>

Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf

We describe new constructions of error correcting codes, obtained by "degree-lifting" a short algebraic geometry (AG) base-code of block-length $q$ to a lifted-code of block-length $q^m$, for arbitrary integer $m$. The construction generalizes the way degree-$d$, univariate polynomials evaluated over the $q$-element field (also known as Reed-Solomon codes) are "lifted" ... more >>>

Alan Guo, Swastik Kopparty, Madhu Sudan

the ``lifting'' of ``affine-invariant'' codes.

Affine-invariant codes are simply linear codes whose coordinates

are a vector space over a field and which are invariant under

affine-transformations of the coordinate space. Lifting takes codes

defined over a vector space of small dimension ...
more >>>

Michael Elberfeld, Christoph Stockhusen, Till Tantau

Parameterized complexity theory measures the complexity of computational problems predominantly in terms of their parameterized time complexity. The purpose of the present paper is to demonstrate that the study of parameterized space complexity can give new insights into the complexity of well-studied parameterized problems like the feedback vertex set problem. ... more >>>

Subhash Khot, Madhur Tulsiani, Pratik Worah

A boolean predicate $f:\{0,1\}^k\to\{0,1\}$ is said to be {\em somewhat approximation resistant} if for some constant $\tau > \frac{|f^{-1}(1)|}{2^k}$, given a $\tau$-satisfiable instance of the MAX-$k$-CSP$(f)$ problem, it is NP-hard to find an assignment that {\it strictly beats} the naive algorithm that outputs a uniformly random assignment. Let $\tau(f)$ denote ... more >>>

Anindya De, Ilias Diakonikolas, Rocco Servedio

We initiate the study of \emph{inverse} problems in approximate uniform generation, focusing on uniform generation of satisfying assignments of various types of Boolean functions. In such an inverse problem, the algorithm is given uniform random satisfying assignments of an unknown function $f$ belonging to a class $\C$ of Boolean functions ... more >>>

Joshua Brody, Amit Chakrabarti, Ranganath Kondapally

The \textsc{equality} problem is usually one's first encounter with

communication complexity and is one of the most fundamental problems in the

field. Although its deterministic and randomized communication complexity

were settled decades ago, we find several new things to say about the

problem by focusing on two subtle aspects. The ...
more >>>

Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah

In this paper we define and examine the power of the conditional-sampling oracle in the context of distribution-property testing. The conditional-sampling oracle for a discrete distribution $\mu$ takes as input a subset $S \subset [n]$ of the domain, and outputs a random sample $i \in S$ drawn according to $\mu$, ... more >>>

Clement Canonne, Dana Ron, Rocco Servedio

We study a new framework for property testing of probability distributions, by considering distribution testing algorithms that have access to a conditional sampling oracle. \footnote{Independently from our work, Chakraborty et al. [CFGM13] also considered this framework. We discuss their work in Subsection 1.4.} This is an oracle that takes as ... more >>>

Andrej Bogdanov, Chin Ho Lee

We show that public-key bit encryption schemes which support weak homomorphic evaluation of parity or majority cannot be proved message indistinguishable beyond AM intersect coAM via general (adaptive) reductions, and beyond statistical zero-knowledge via reductions of constant query complexity.

Previous works on the limitation of reductions for proving security of ... more >>>

Andrej Bogdanov, Chin Ho Lee

We show that secure homomorphic evaluation of any non-trivial functionality of sufficiently many inputs with respect to any CPA secure encryption scheme cannot be implemented by constant depth, polynomial size circuits, i.e. in the class AC0. In contrast, we observe that certain previously studied encryption schemes (with quasipolynomial security) can ... more >>>

Aditya Bhaskara, Devendra Desai, Srikanth Srinivasan

We consider the problem of constructing explicit Hitting sets for Combinatorial Shapes, a class of statistical tests first studied by Gopalan, Meka, Reingold, and Zuckerman (STOC 2011). These generalize many well-studied classes of tests, including symmetric functions and combinatorial rectangles. Generalizing results of Linial, Luby, Saks, and Zuckerman (Combinatorica 1997) ... more >>>

Eli Ben-Sasson, Michael Viderman

The study of locally testable codes (LTCs) has benefited from a number of nontrivial constructions discovered in recent years. Yet we still lack a good understanding of what makes a linear error correcting code locally testable and as a result we do not know what is the rate-limit of LTCs ... more >>>

Frederic Green, Daniel Kreymer, Emanuele Viola

We show that degree-$d$ block-symmetric polynomials in

$n$ variables modulo any odd $p$ correlate with parity

exponentially better than degree-$d$ symmetric

polynomials, if $n \ge c d^2 \log d$ and $d \in [0.995

\cdot p^t - 1,p^t)$ for some $t \ge 1$. For these

infinitely many degrees, our result ...
more >>>

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria

We explain an asymmetric Prover-Delayer game which precisely characterizes proof size in tree-like Resolution. This game was previously described in a parameterized complexity context to show lower bounds for parameterized formulas and for the classical pigeonhole principle. The main point of this note is to show that the asymmetric game ... more >>>

Hans-Joachim Boeckenhauer, Juraj Hromkovic, Dennis Komm, Sacha Krug, Jasmin Smula, Andreas Sprock

The advice complexity of an online problem describes the additional information both necessary and sufficient for online algorithms to compute solutions of a certain quality. In this model, an oracle inspects the input before it is processed by an online algorithm. Depending on the input string, the oracle prepares an ... more >>>

Avishay Tal

For Boolean functions $f:\{0,1\}^n \to \{0,1\}$ and $g:\{0,1\}^m \to \{0,1\}$, the function composition of $f$ and $g$ denoted by $f\circ g : \{0,1\}^{nm} \to \{0,1\}$ is the value of $f$ on $n$ inputs, each of them is the calculation of $g$ on a distinct set of $m$ Boolean variables. Motivated ... more >>>

Rafail Ostrovsky, Ivan Visconti

In FOCS 2001, Barak, Goldreich, Goldwasser and Lindell conjectured that the existence of ZAPs, introduced by Dwork and Naor in FOCS 2000, could lead to the design of a zero-knowledge proof system that is secure against both resetting provers and resetting verifiers. Their conjecture has been proven true by Deng, ... more >>>

Martin Albrecht, Pooya Farshim, Jean-Charles Faugère, Gottfried Herold, Ludovic Perret

We initiate the formal treatment of cryptographic constructions based on the hardness of computing remainders modulo an ideal in multivariate polynomial rings. Of particular interest to us is a class of schemes known as "Polly Cracker." We start by formalising and studying the relation between the ideal remainder problem and ... more >>>

Elad Haramaty, Madhu Sudan

We consider the task of compression of information when the source of the information and the destination do not agree on the prior, i.e., the distribution from which the information is being generated. This setting was considered previously by Kalai et al. (ICS 2011) who suggested that this was a ... more >>>

Periklis Papakonstantinou, Charles Rackoff, Yevgeniy Vahlis

The question whether Identity-Based Encryption (IBE) can be based on the Decisional Diffie-Hellman (DDH) assumption is one of the most prominent questions in Cryptography related to DDH. We study limitations on the use of the DDH assumption in cryptographic constructions, and show that it is impossible to construct a secure ... more >>>

Michael Viderman

An error-correcting code $C \subseteq \F^n$ is called $(q,\epsilon)$-strong locally testable code (LTC) if there exists a randomized algorithm (tester) that makes at most $q$ queries to the input word. This algorithm accepts all codewords with probability 1 and rejects all non-codewords $x\notin C$ with probability at least $\epsilon \cdot ... more >>>

Noga Alon, Santosh Vempala

We introduce and study the \epsilon-rank of a real matrix A, defi ned, for any \epsilon > 0 as the minimum rank over matrices that approximate every entry of A to within an additive \epsilon. This parameter is connected to other notions of approximate rank and is motivated by ... more >>>

Scott Aaronson, Travis Hance

Around 2002, Leonid Gurvits gave a striking randomized algorithm to approximate the permanent of an n×n matrix A. The algorithm runs in O(n^2/?^2) time, and approximates Per(A) to within ±?||A||^n additive error. A major advantage of Gurvits's algorithm is that it works for arbitrary matrices, not just for nonnegative matrices. ... more >>>

Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein

We develop a new local characterization of the zero-error information complexity function for two party communication problems, and use it to compute the exact internal and external information complexity of the 2-bit AND function: $IC(AND,0) = C_{\wedge}\approx 1.4923$ bits, and $IC^{ext}(AND,0) = \log_2 3 \approx 1.5839$ bits. This leads to ... more >>>

Mahdi Cheraghchi, Anna Gal, Andrew Mills

Locally decodable codes (LDCs) are error correcting codes with the extra property that it is sufficient to read just a small number of positions of a possibly corrupted codeword in order to recover any one position of the input. To achieve this, it is necessary to use randomness in the ... more >>>

Kfir Barhum, Thomas Holenstein

We present a new framework for proving fully black-box

separations and lower bounds. We prove a general theorem that facilitates

the proofs of fully black-box lower bounds from a one-way function (OWF).

Loosely speaking, our theorem says that in order to prove that a fully black-box

construction does ...
more >>>

Anat Ganor, Ilan Komargodski, Ran Raz

We show a connection between the deMorgan formula size of a Boolean function and the noise stability of the function. Using this connection, we show that the Fourier spectrum of any balanced Boolean function computed by a deMorgan formula of size $s$ is concentrated on coefficients of degree up to ... more >>>

James Cook, Omid Etesami, Rachel Miller, Luca Trevisan

A function $f$ mapping $n$-bit strings to $m$-bit strings can be constructed from a bipartite graph with $n$ vertices on the left and $m$ vertices on the right having right-degree $d$ together with a predicate $P:\{0,1\}^d\rightarrow\{0,1\}$. The vertices on the left correspond to the bits of the input to the ... more >>>

Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu

We present a polynomial time dynamic programming algorithm for optimal partitions in the shortest path metric induced by a tree. This resolves, among other things, the exact complexity status of the optimal partition problems in one dimensional geometric metric settings. Our method of solution could be also of independent interest ... more >>>

Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein

We use self-reduction methods to prove strong information lower bounds on two of the most studied functions in the communication complexity literature: Gap Hamming Distance (GHD) and Inner Product (IP). In our first result we affirm the conjecture that the information cost of GHD is linear even under the uniform ... more >>>

Paul Beame, Raphael Clifford, Widad Machmouchi

We consider time-space tradeoffs for exactly computing frequency

moments and order statistics over sliding windows.

Given an input of length $2n-1$, the task is to output the function of

each window of length $n$, giving $n$ outputs in total.

Computations over sliding windows are related to direct sum problems

except ...
more >>>

Joshua Brody, Harry Buhrman, Michal Koucky, Bruno Loff, Florian Speelman

Newman’s theorem states that we can take any public-coin communication protocol and convert it into one that uses only private randomness with only a little increase in communication complexity. We consider a reversed scenario in the context of information complexity: can we take a protocol that uses private randomness and ... more >>>

Chaim Even-Zohar, Shachar Lovett

Let $G$ be a finite abelian group of torsion $r$ and let $A$ be a subset of $G$.

The Freiman-Ruzsa theorem asserts that if $|A+A| \le K|A|$

then $A$ is contained in a coset of a subgroup of $G$ of size at most $K^2 r^{K^4} |A|$. It was ...
more >>>

Anindya De, Ilias Diakonikolas, Rocco Servedio

For $f$ a weighted voting scheme used by $n$ voters to choose between two candidates, the $n$ \emph{Shapley-Shubik Indices} (or {\em Shapley values}) of $f$ provide a measure of how much control each voter can exert over the overall outcome of the vote. Shapley-Shubik indices were introduced by Lloyd Shapley ... more >>>

Itay Berman, Iftach Haitner, Ilan Komargodski, Moni Naor

A common method for increasing the usability and uplifting the security of pseudorandom function families (PRFs) is to ``hash" the inputs into a smaller domain before applying the PRF. This approach, known as ``Levin's trick", is used to achieve ``PRF domain extension" (using a short, e.g., fixed, input length PRF ... more >>>

András Salamon

In graph streaming a graph with $n$ vertices and $m$ edges is presented as a read-once stream of edges. We obtain an $\Omega(n \log n)$ lower bound on the space required to decide graph connectivity. This improves the known bounds of $\Omega(n)$ for undirected and $\Omega(m)$ for sparse directed graphs. ... more >>>

Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett

Let $\mathbb{F} = \mathbb{F}_p$ for any fixed prime $p \geq 2$. An affine-invariant property is a property of functions on $\mathbb{F}^n$ that is closed under taking affine transformations of the domain. We prove that all affine-invariant property having local characterizations are testable. In fact, we show a proximity-oblivious test for ... more >>>

Siu Man Chan, Aaron Potechin

We prove tight size bounds on monotone switching networks for the NP-complete problem of

$k$-clique, and for an explicit monotone problem by analyzing a pyramid structure of height $h$ for

the P-complete problem of generation. This gives alternative proofs of the separations of m-NC

from m-P and of m-NC$^i$ from ...
more >>>

Andreas Krebs, Nutan Limaye

We define DLOGTIME proof systems, DLTPS, which generalize NC0 proof systems.

It is known that functions such as Exact-k and Majority do not have NC0 proof systems. Here, we give a DLTPS for Exact-k (and therefore for Majority) and also for other natural functions such as Reach and k-Clique. Though ...
more >>>