All reports in year 2010:

__
TR10-001
| 30th December 2009
__

Iftach Haitner, Mohammad Mahmoody, David Xiao#### A New Sampling Protocol and Applications to Basing Cryptographic Primitives on the Hardness of $NP$

__
TR10-002
| 4th January 2010
__

Ran Raz#### Tensor-Rank and Lower Bounds for Arithmetic Formulas

__
TR10-003
| 6th January 2010
__

Venkatesan Guruswami, Johan Håstad, Swastik Kopparty#### On the List-Decodability of Random Linear Codes

__
TR10-004
| 6th January 2010
__

Eli Ben-Sasson, Michael Viderman#### Low Rate Is Insufficient for Local Testability

Revisions: 3

__
TR10-005
| 3rd January 2010
__

Haitao Jiang, Binhai Zhu#### Weak Kernels

Revisions: 7

__
TR10-006
| 11th January 2010
__

YI WU, Ryan O'Donnell, David Zuckerman, Parikshit Gopalan#### Fooling functions of halfspaces under product distributions

Revisions: 2

__
TR10-007
| 12th January 2010
__

Atri Rudra, steve uurtamo#### Two Theorems in List Decoding

__
TR10-008
| 13th January 2010
__

Yijia Chen, Joerg Flum#### On optimal proof systems and logics for PTIME

Revisions: 1

__
TR10-009
| 13th January 2010
__

A. Pavan, Raghunath Tewari, Vinodchandran Variyam#### On the Power of Unambiguity in Logspace

__
TR10-010
| 16th January 2010
__

Shachar Lovett#### Equivalence of polynomial conjectures in additive combinatorics

__
TR10-011
| 22nd January 2010
__

Amir Shpilka, Ilya Volkovich#### Read-Once Polynomial Identity Testing

__
TR10-012
| 27th January 2010
__

Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin#### Matching Vector Codes

Revisions: 1

__
TR10-013
| 31st January 2010
__

Nitin Saxena, C. Seshadhri#### From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits

Revisions: 1

__
TR10-014
| 2nd February 2010
__

Daniele Micciancio, Panagiotis Voulgaris#### A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations

Revisions: 1

__
TR10-015
| 8th February 2010
__

Maurice Jansen, Youming Qiao, Jayalal Sarma#### Deterministic Black-Box Identity Testing $\pi$-Ordered Algebraic Branching Programs

__
TR10-016
| 22nd December 2009
__

Alexander Fanghänel, Sascha Geulen, Martin Hoefer, Berthold Vöcking#### Online Capacity Maximization in Wireless Networks

__
TR10-017
| 10th February 2010
__

Jonathan Ullman, Salil Vadhan#### PCPs and the Hardness of Generating Synthetic Data

Revisions: 4

__
TR10-018
| 15th February 2010
__

Vitaly Feldman#### A Complete Characterization of Statistical Query Learning with Applications to Evolvability

Revisions: 1

__
TR10-019
| 19th February 2010
__

Andrew Drucker#### A PCP Characterization of AM

__
TR10-020
| 19th February 2010
__

Vipul Goyal, Yuval Ishai, Mohammad Mahmoody, Amit Sahai#### Interactive Locking, Zero-Knowledge PCPs, and Unconditional Cryptography

__
TR10-021
| 21st February 2010
__

Pavel Hrubes, Avi Wigderson, Amir Yehudayoff#### Non-commutative circuits and the sum-of-squares problem

__
TR10-022
| 23rd February 2010
__

Vitaly Feldman, Homin Lee, Rocco Servedio#### Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas

__
TR10-023
| 23rd February 2010
__

Adam Klivans, Homin Lee, Andrew Wan#### Mansour’s Conjecture is True for Random DNF Formulas

Revisions: 3

__
TR10-024
| 21st February 2010
__

Henning Wunderlich, Stefan Arnold#### On a singular value method in quantum communication complexity

Comments: 1

__
TR10-025
| 24th February 2010
__

Alexander A. Sherstov#### Optimal bounds for sign-representing the intersection of two halfspaces by polynomials

__
TR10-026
| 25th February 2010
__

Hao Huang, Benny Sudakov#### A counterexample to the Alon-Saks-Seymour conjecture and related problems

__
TR10-027
| 28th February 2010
__

Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant#### Testing monotonicity of distributions over general partial orders

__
TR10-028
| 4th March 2010
__

Miklos Ajtai#### Oblivious RAMs without Cryptographic Assumptions

Revisions: 1

__
TR10-029
| 3rd March 2010
__

Alexandra Kolla#### Spectral Algorithms for Unique Games

__
TR10-030
| 18th February 2010
__

Airat Khasianov#### Stronger Lower Bounds on Quantum OBDD for the Hidden Subgroup Problem

Revisions: 2

__
TR10-031
| 4th March 2010
__

Christian Glaßer, Christian Reitwießner, Heinz Schmitz, Maximilian Witek#### Hardness and Approximability in Multi-Objective Optimization

__
TR10-032
| 19th January 2010
__

Jack H. Lutz, Brad Shutters#### Approximate Self-Assembly of the Sierpinski Triangle

__
TR10-033
| 6th March 2010
__

Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka#### Pseudorandom generators for $\mathrm{CC}_0[p]$ and the Fourier spectrum of low-degree polynomials over finite fields

__
TR10-034
| 7th March 2010
__

Luca Trevisan#### The Program-Enumeration Bottleneck in Average-Case Complexity Theory

__
TR10-035
| 7th March 2010
__

Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff#### Pseudorandom Generators for Regular Branching Programs

__
TR10-036
| 8th March 2010
__

Amir Shpilka, Ilya Volkovich#### On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors

__
TR10-037
| 8th March 2010
__

Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson#### Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors

__
TR10-038
| 10th March 2010
__

Dieter van Melkebeek, Holger Dell#### Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses

Revisions: 1

__
TR10-039
| 10th March 2010
__

Gil Cohen, Amir Shpilka#### On the degree of symmetric functions on the Boolean cube

Comments: 1

__
TR10-040
| 10th March 2010
__

Pavel Hrubes, Avi Wigderson, Amir Yehudayoff#### Relationless completeness and separations

__
TR10-041
| 11th March 2010
__

Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer#### Improved Algorithms for Unique Games via Divide and Conquer

__
TR10-042
| 12th March 2010
__

Thomas Watson#### Relativized Worlds Without Worst-Case to Average-Case Reductions for NP

Revisions: 3

__
TR10-043
| 5th March 2010
__

Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky#### Interval Graphs: Canonical Representation in Logspace

Revisions: 1

__
TR10-044
| 12th March 2010
__

Eli Ben-Sasson, Swastik Kopparty#### Affine Dispersers from Subspace Polynomials

__
TR10-045
| 15th March 2010
__

Jakob Nordström#### On the Relative Strength of Pebbling and Resolution

Revisions: 1

__
TR10-046
| 22nd March 2010
__

Ján Pich#### Nisan-Wigderson generators in proof systems with forms of interpolation

__
TR10-047
| 23rd March 2010
__

Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma#### Local list decoding with a constant number of queries

Revisions: 1

__
TR10-048
| 24th March 2010
__

David García Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet#### Monotonicity Testing and Shortest-Path Routing on the Cube

__
TR10-049
| 24th March 2010
__

Alexey Pospelov#### Bounds for Bilinear Complexity of Noncommutative Group Algebras

Revisions: 1
,
Comments: 1

__
TR10-050
| 25th March 2010
__

Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner#### Graph Isomorphism for $K_{3,3}$-free and $K_5$-free graphs is in Log-space

__
TR10-051
| 26th March 2010
__

Madhu Sudan#### Invariance in Property Testing

__
TR10-052
| 8th March 2010
__

Melanie Winkler, Berthold Vöcking, Sascha Geulen#### Regret Minimization for Online Buffering Problems Using the Weighted Majority Algorithm

__
TR10-053
| 28th March 2010
__

Dana Moshkovitz, Subhash Khot#### Hardness of Approximately Solving Linear Equations Over Reals

Comments: 1

__
TR10-054
| 30th March 2010
__

Jan Krajicek#### On the proof complexity of the Nisan-Wigderson generator based on a hard $NP \cap coNP$ function

__
TR10-055
| 31st March 2010
__

Eric Allender#### Avoiding Simplicity is Complex

Revisions: 2

__
TR10-056
| 1st April 2010
__

Kord Eickmeyer, Martin Grohe#### Randomisation and Derandomisation in Descriptive Complexity Theory

Revisions: 1

__
TR10-057
| 1st April 2010
__

Scott Aaronson, Andrew Drucker#### A Full Characterization of Quantum Advice

Revisions: 3

__
TR10-058
| 7th April 2010
__

Oded Goldreich, Tali Kaufman#### Proximity Oblivious Testing and the Role of Invariances

Revisions: 1

__
TR10-059
| 8th April 2010
__

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria#### Hardness of Parameterized Resolution

__
TR10-060
| 5th April 2010
__

Dmitry Gavinsky, Alexander A. Sherstov#### A Separation of NP and coNP in Multiparty Communication Complexity

__
TR10-061
| 10th April 2010
__

Oded Goldreich#### On Testing Computability by Small Width OBDDs

Revisions: 2

__
TR10-062
| 7th April 2010
__

Michael Elberfeld, Andreas Jakoby, Till Tantau#### Logspace Versions of the Theorems of Bodlaender and Courcelle

__
TR10-063
| 12th April 2010
__

Venkatesan Guruswami, Yuan Zhou#### Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set}

Revisions: 1

__
TR10-064
| 13th April 2010
__

Xin Li#### A New Approach to Affine Extractors and Dispersers

__
TR10-065
| 13th April 2010
__

Tali Kaufman, Shachar Lovett#### Testing of exponentially large codes, by a new extension to Weil bound for character sums

Revisions: 1

__
TR10-066
| 14th April 2010
__

Sanjeev Arora, Rong Ge#### Learning Parities with Structured Noise

Revisions: 1

__
TR10-067
| 14th April 2010
__

Sourav Chakraborty, Eldar Fischer, Arie Matsliah#### Query Complexity Lower Bounds for Reconstruction of Codes

__
TR10-068
| 15th April 2010
__

Shir Ben-Israel, Eli Ben-Sasson, David Karger#### Breaking local symmetries can dramatically reduce the length of propositional refutations

__
TR10-069
| 17th April 2010
__

Eric Allender, Vikraman Arvind, Fengming Wang#### Uniform Derandomization from Pathetic Lower Bounds

Revisions: 1
,
Comments: 1

__
TR10-070
| 17th April 2010
__

Eric Allender, Klaus-Joern Lange#### Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata

__
TR10-071
| 19th April 2010
__

Rahul Jain, Ashwin Nayak#### The space complexity of recognizing well-parenthesized expressions

Revisions: 4

__
TR10-072
| 19th April 2010
__

Russell Impagliazzo, Valentine Kabanets#### Constructive Proofs of Concentration Bounds

__
TR10-073
| 21st April 2010
__

Neeraj Kayal#### Algorithms for Arithmetic Circuits

__
TR10-074
| 20th April 2010
__

Parikshit Gopalan, Rocco Servedio#### Learning and Lower Bounds for AC$^0$ with Threshold Gates

__
TR10-075
| 22nd April 2010
__

Ben Reichardt#### Least span program witness size equals the general adversary lower bound on quantum query complexity

__
TR10-076
| 18th April 2010
__

Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor#### Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition

Revisions: 1

__
TR10-077
| 26th April 2010
__

Venkatesan Guruswami, Adam Smith#### Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate

__
TR10-078
| 27th April 2010
__

Holger Dell, Thore Husfeldt, Martin Wahlén#### Exponential Time Complexity of the Permanent and the Tutte Polynomial

Revisions: 1

__
TR10-079
| 28th April 2010
__

Samir Datta, Raghav Kulkarni, Raghunath Tewari, Vinodchandran Variyam#### Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs

__
TR10-080
| 5th May 2010
__

Andrew Drucker#### Improved Direct Product Theorems for Randomized Query Complexity

Revisions: 1

__
TR10-081
| 10th May 2010
__

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria#### A Lower Bound for the Pigeonhole Principle in Tree-like Resolution by Asymmetric Prover-Delayer Games

__
TR10-082
| 11th May 2010
__

Oded Goldreich#### Introduction to Testing Graph Properties

__
TR10-083
| 13th May 2010
__

Mark Braverman, Anup Rao#### Efficient Communication Using Partial Information

Revisions: 1

__
TR10-084
| 14th May 2010
__

Maurice Jansen, Youming Qiao, Jayalal Sarma#### Deterministic Identity Testing of Read-Once Algebraic Branching Programs

__
TR10-085
| 20th May 2010
__

Eli Ben-Sasson, Jan Johannsen#### Lower bounds for width-restricted clause learning on small width formulas

__
TR10-086
| 17th May 2010
__

Henning Wunderlich#### On a Theorem of Razborov

__
TR10-087
| 17th May 2010
__

Shachar Lovett, Ely Porat#### A lower bound for dynamic approximate membership data structures

__
TR10-088
| 17th May 2010
__

Jiri Sima, Stanislav Zak#### A Polynomial Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3

Revisions: 2
,
Comments: 3

__
TR10-089
| 26th May 2010
__

Iftach Haitner, Omer Reingold, Salil Vadhan#### Efficiency Improvements in Constructing Pseudorandom Generators from One-way Functions

__
TR10-090
| 14th May 2010
__

Nikolay Vereshchagin#### {Algorithmic Minimal Sufficient Statistics: a New Definition

__
TR10-091
| 14th May 2010
__

Nikolay Vereshchagin#### An Encoding Invariant Version of Polynomial Time
Computable Distributions

__
TR10-092
| 22nd May 2010
__

Charanjit Jutla, Arnab Roy#### A Completeness Theorem for Pseudo-Linear Functions with Applications to UC Security

Revisions: 1
,
Comments: 1

__
TR10-093
| 3rd June 2010
__

Sourav Chakraborty, David García Soriano, Arie Matsliah#### Nearly Tight Bounds for Testing Function Isomorphism

__
TR10-094
| 17th May 2010
__

Ajesh Babu, Nutan Limaye, Girish Varma#### Streaming algorithms for some problems in log-space.

__
TR10-095
| 11th June 2010
__

Masaki Yamamoto#### A combinatorial analysis for the critical clause tree

__
TR10-096
| 16th June 2010
__

Dana Moshkovitz#### An Alternative Proof of The Schwartz-Zippel Lemma

Revisions: 1

__
TR10-097
| 16th June 2010
__

Iddo Tzameret#### Algebraic Proofs over Noncommutative Formulas

Revisions: 1

__
TR10-098
| 17th June 2010
__

Daniel Kane, Jelani Nelson#### A Derandomized Sparse Johnson-Lindenstrauss Transform

Revisions: 2

__
TR10-099
| 20th June 2010
__

T.C. Vijayaraghavan#### A Note on Closure Properties of ModL

__
TR10-100
| 25th June 2010
__

Amit Chakrabarti#### A Note on Randomized Streaming Space Bounds for the Longest Increasing Subsequence Problem

__
TR10-101
| 25th June 2010
__

Samir Datta, Meena Mahajan, Raghavendra Rao B V, Michael Thomas, Heribert Vollmer#### Counting Classes and the Fine Structure between NC$^1$ and L.

__
TR10-102
| 12th May 2010
__

Per Kristian Lehre, Carsten Witt#### Black-Box Search by Unbiased Variation

Revisions: 1

__
TR10-103
| 28th June 2010
__

Andreas Krebs, Nutan Limaye, Meena Mahajan#### Counting paths in VPA is complete for \#NC$^1$

__
TR10-104
| 29th June 2010
__

Paul Beame, Widad Machmouchi#### Making RAMs Oblivious Requires Superlogarithmic Overhead

Revisions: 3
,
Comments: 1

__
TR10-105
| 29th June 2010
__

Scott Aaronson, Dieter van Melkebeek#### A note on circuit lower bounds from derandomization

__
TR10-106
| 17th June 2010
__

Yuichi Yoshida#### Optimal Constant-Time Approximation Algorithms and (Unconditional) Inapproximability Results for Every Bounded-Degree CSP

Revisions: 1

__
TR10-107
| 6th July 2010
__

Irit Dinur, Or Meir#### Derandomized Parallel Repetition via Structured PCPs

Revisions: 3

__
TR10-108
| 9th July 2010
__

Eli Ben-Sasson, Madhu Sudan#### Limits on the rate of locally testable affine-invariant codes

__
TR10-109
| 11th July 2010
__

Scott Aaronson#### A Counterexample to the Generalized Linial-Nisan Conjecture

__
TR10-110
| 14th July 2010
__

Ben Reichardt#### Span programs and quantum query algorithms

__
TR10-111
| 14th July 2010
__

Venkatesan Guruswami, Ali Kemal Sinop#### The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number

__
TR10-112
| 15th July 2010
__

Subhash Khot, Dana Moshkovitz#### NP-Hardness of Approximately Solving Linear Equations Over Reals

__
TR10-113
| 16th July 2010
__

Michal Koucky, Prajakta Nimbhorkar, Pavel Pudlak#### Pseudorandom Generators for Group Products

__
TR10-114
| 17th July 2010
__

Zhixiang Chen, Bin Fu#### The Complexity of Testing Monomials in Multivariate Polynomials

__
TR10-115
| 17th July 2010
__

Shachar Lovett, Emanuele Viola#### Bounded-depth circuits cannot sample good codes

__
TR10-116
| 21st July 2010
__

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie#### Testing linear-invariant non-linear properties: A short report

__
TR10-117
| 22nd July 2010
__

Arkadev Chattopadhyay, Jacobo Toran, Fabian Wagner#### Graph Isomorphism is not AC^0 reducible to Group Isomorphism

__
TR10-118
| 27th July 2010
__

Maurice Jansen#### Extracting Roots of Arithmetic Circuits by Adapting Numerical Methods

Revisions: 2

__
TR10-119
| 27th July 2010
__

Michal Moshkovitz#### Distance Estimators with Sublogarithmic Number of Queries

__
TR10-120
| 27th July 2010
__

Noa Eidelstein, Alex Samorodnitsky#### Lower bounds for designs in symmetric spaces

__
TR10-121
| 28th July 2010
__

Ashwin Nayak#### Inverting a permutation is as hard as unordered search

Revisions: 1

__
TR10-122
| 18th July 2010
__

Zhixiang Chen, Bin Fu, Yang Liu, Robert Schweller#### Algorithms for Testing Monomials in Multivariate Polynomials

__
TR10-123
| 4th August 2010
__

Eli Ben-Sasson#### Limitation on the rate of families of locally testable codes

Revisions: 1

__
TR10-124
| 18th July 2010
__

Zhixiang Chen, Bin Fu#### Approximating Multilinear Monomial Coefficients and Maximum Multilinear Monomials in Multivariate Polynomials

__
TR10-125
| 11th August 2010
__

Eli Ben-Sasson, Jakob Nordström#### Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions

__
TR10-126
| 12th August 2010
__

Thomas Watson#### Query Complexity in Errorless Hardness Amplification

Revisions: 2

__
TR10-127
| 9th August 2010
__

Brett Hemenway, Rafail Ostrovsky#### Building Injective Trapdoor Functions From Oblivious Transfer

Revisions: 1

__
TR10-128
| 15th August 2010
__

Scott Aaronson#### The Equivalence of Sampling and Searching

Revisions: 1

__
TR10-129
| 16th August 2010
__

Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel#### Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds

__
TR10-130
| 18th August 2010
__

Tali Kaufman, Michael Viderman#### Locally Testable vs. Locally Decodable Codes

Revisions: 1

__
TR10-131
| 9th July 2010
__

Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, Shinnosuke Seki#### The Power of Nondeterminism in Self-Assembly

__
TR10-132
| 18th August 2010
__

Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson#### Approximating Linear Threshold Predicates

__
TR10-133
| 20th August 2010
__

Parikshit Gopalan, Adam Klivans, Raghu Meka#### Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs

__
TR10-134
| 23rd August 2010
__

Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma#### A Note on Amplifying the Error-Tolerance of Locally Decodable Codes

Revisions: 2

__
TR10-135
| 24th August 2010
__

Oded Goldreich#### In a World of P=BPP

Revisions: 2

__
TR10-136
| 26th August 2010
__

Arnab Bhattacharyya, Elena Grigorescu, Jakob Nordström, Ning Xie#### Separations of Matroid Freeness Properties

Revisions: 1

__
TR10-137
| 29th August 2010
__

Or Meir#### IP = PSPACE using Error Correcting Codes

Revisions: 5

__
TR10-138
| 17th September 2010
__

Eric Allender, Luke Friedman, William Gasarch#### Exposition of the Muchnik-Positselsky Construction of a Prefix Free Entropy Function that is not Complete under Truth-Table Reductions

__
TR10-139
| 17th September 2010
__

Eric Allender, Luke Friedman, William Gasarch#### Limits on the Computational Power of Random Strings

Revisions: 1

__
TR10-140
| 17th September 2010
__

Amit Chakrabarti, Oded Regev#### An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance

__
TR10-141
| 18th September 2010 (removed)
__

Ran Raz#### A Strong Parallel Repetition Theorem for Projection Games on Expanders

Reason: This paper has been remove on the author's behalf. Please note that TR10-142 is the corrected version.

__
TR10-142
| 18th September 2010
__

Ran Raz, Ricky Rosen#### A Strong Parallel Repetition Theorem for Projection Games on Expanders

__
TR10-143
| 19th September 2010
__

Bo'az Klartag, Oded Regev#### Quantum One-Way Communication is Exponentially Stronger Than Classical Communication

__
TR10-144
| 20th September 2010
__

Eli Ben-Sasson, Noga Ron-Zewi#### From Affine to Two-Source Extractors via Approximate Duality

Revisions: 1

__
TR10-145
| 21st September 2010
__

Ron Rothblum#### A Taxonomy of Enhanced Trapdoor Permutations

__
TR10-146
| 21st September 2010
__

Ron Rothblum#### Homomorphic Encryption: from Private-Key to Public-Key

__
TR10-147
| 22nd September 2010
__

Dieter van Melkebeek, Thomas Watson#### Time-Space Efficient Simulations of Quantum Computations

Revisions: 1

__
TR10-148
| 23rd September 2010
__

Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin#### High-rate codes with sublinear-time decoding

__
TR10-149
| 22nd September 2010
__

Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff#### Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes

Revisions: 1

__
TR10-150
| 19th September 2010
__

Bjørn Kjos-Hanssen#### A strong law of computationally weak subsets

__
TR10-151
| 30th September 2010
__

Raghunath Tewari, Vinodchandran Variyam#### Green’s Theorem and Isolation in Planar Graphs

__
TR10-152
| 6th October 2010
__

Alexey Pospelov#### Faster Polynomial Multiplication via Discrete Fourier Transforms

__
TR10-153
| 7th October 2010
__

Lorenzo Carlucci, Nicola Galesi, Massimo Lauria#### Paris-Harrington tautologies

Revisions: 2

__
TR10-154
| 8th October 2010
__

Derrick Stolee, Vinodchandran Variyam#### Space-Efficient Algorithms for Reachability in Surface-Embedded Graphs

__
TR10-155
| 14th October 2010
__

Brendan Juba, Madhu Sudan#### Efficient Semantic Communication via Compatible Beliefs

__
TR10-156
| 24th October 2010
__

Victor Chen, Madhu Sudan, Ning Xie#### Property Testing via Set-Theoretic Operations

__
TR10-157
| 24th October 2010
__

Reut Levi, Dana Ron, Ronitt Rubinfeld#### Testing Properties of Collections of Distributions

Revisions: 1

__
TR10-158
| 31st October 2010
__

Shiva Kintali#### Realizable Paths and the NL vs L Problem

Revisions: 2

__
TR10-159
| 28th October 2010
__

Graham Cormode, Justin Thaler, Ke Yi#### Verifying Computations with Streaming Interactive Proofs

__
TR10-160
| 28th October 2010
__

Zeev Dvir, Dan Gutfreund, Guy Rothblum, Salil Vadhan#### On Approximating the Entropy of Polynomial Mappings

__
TR10-161
| 25th October 2010
__

Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira#### A Unified Framework for Testing Linear-Invariant Properties

__
TR10-162
| 30th October 2010
__

Zohar Karnin#### Deterministic Construction of a high dimensional $\ell_p$ section in $\ell_1^n$ for any $p<2$

__
TR10-163
| 3rd November 2010
__

Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolay Vereshchagin#### Sparse Selfreducible Sets and Nonuniform Lower Bounds

__
TR10-164
| 4th November 2010
__

Falk Unger#### Better gates can make fault-tolerant computation impossible

Revisions: 1

__
TR10-165
| 4th November 2010
__

Dmitry Gavinsky, Tsuyoshi Ito#### Quantum Fingerprints that Keep Secrets

__
TR10-166
| 5th November 2010
__

Mark Braverman, Anup Rao#### Towards Coding for Maximum Errors in Interactive Communication

__
TR10-167
| 5th November 2010
__

Nitin Saxena, C. Seshadhri#### Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter

__
TR10-168
| 9th November 2010
__

Thomas Watson#### Pseudorandom Generators for Combinatorial Checkerboards

Revisions: 2

__
TR10-169
| 10th November 2010
__

Siavosh Benabbas, Konstantinos Georgiou, Avner Magen#### The Sherali-Adams System Applied to Vertex Cover: Why Borsuk Graphs Fool Strong LPs and some Tight Integrality Gaps for SDPs

Revisions: 2

__
TR10-170
| 11th November 2010
__

Scott Aaronson, Alex Arkhipov#### The Computational Complexity of Linear Optics

__
TR10-171
| 11th November 2010
__

Michael Viderman#### A Note on high-rate Locally Testable Codes with sublinear query complexity

__
TR10-172
| 11th November 2010
__

Prasad Raghavendra, David Steurer, Madhur Tulsiani#### Reductions Between Expansion Problems

__
TR10-173
| 9th November 2010
__

Yeow Meng Chee, Tao Feng, San Ling, Huaxiong Wang, Liang Feng Zhang#### Query-Efficient Locally Decodable Codes

__
TR10-174
| 12th November 2010
__

Scott Aaronson, Baris Aydinlioglu, Harry Buhrman, John Hitchcock, Dieter van Melkebeek#### A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games

__
TR10-175
| 14th November 2010
__

Emanuele Viola#### Randomness buys depth for approximate counting

Revisions: 1

__
TR10-176
| 15th November 2010
__

Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman#### Pseudorandom Generators for Combinatorial Shapes

Revisions: 1

__
TR10-177
| 16th November 2010
__

Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu#### Bypassing UGC from some optimal geometric inapproximability results

Revisions: 1

__
TR10-178
| 17th November 2010
__

Amir Shpilka, Avishay Tal#### On the Minimal Fourier Degree of Symmetric Boolean Functions

__
TR10-179
| 18th November 2010
__

Gregory Valiant, Paul Valiant#### A CLT and tight lower bounds for estimating entropy

Revisions: 1

__
TR10-180
| 18th November 2010
__

Gregory Valiant, Paul Valiant#### Estimating the unseen: A sublinear-sample canonical estimator of distributions

__
TR10-181
| 21st November 2010
__

Hamed Hatami, Shachar Lovett#### Higher-order Fourier analysis of $\mathbb{F}_p^n$ and the complexity of systems of linear forms

__
TR10-182
| 26th November 2010
__

Shachar Lovett#### An elementary proof of anti-concentration of polynomials in Gaussian variables

__
TR10-183
| 29th November 2010
__

Raghu Meka#### Almost Optimal Explicit Johnson-Lindenstrauss Transformations

Revisions: 2

__
TR10-184
| 19th November 2010
__

Manjish Pal#### Combinatorial Geometry of Graph Partitioning - I

__
TR10-185
| 2nd December 2010
__

Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu#### Agnostic Learning of Monomials by Halfspaces is Hard

__
TR10-186
| 2nd December 2010
__

Bill Fefferman, Ronen Shaltiel, Chris Umans, Emanuele Viola#### On beating the hybrid argument

__
TR10-187
| 3rd December 2010
__

Gus Gutoski#### Interactive proofs with competing teams of no-signaling provers

Revisions: 2

__
TR10-188
| 8th December 2010
__

Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich#### Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae

Revisions: 1

__
TR10-189
| 8th December 2010
__

Neeraj Kayal, Chandan Saha#### On the Sum of Square Roots of Polynomials and related problems

__
TR10-190
| 9th December 2010
__

Xin Li#### Improved Constructions of Three Source Extractors

__
TR10-191
| 9th December 2010
__

Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland#### Symmetry-assisted adversaries for quantum state generation

__
TR10-192
| 8th December 2010
__

Frederic Magniez, Ashwin Nayak, Miklos Santha, David Xiao#### Improved bounds for the randomized decision tree complexity of recursive majority

Revisions: 1

__
TR10-193
| 5th December 2010
__

Edward Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal#### On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography

__
TR10-194
| 9th December 2010
__

Thanh Minh Hoang#### Isolation of Matchings via Chinese Remaindering

__
TR10-195
| 13th November 2010
__

Ho-Lin Chen, David Doty, Shinnosuke Seki, David Soloveichik#### Parallelism, Program Size, Time, and Temperature in Self-Assembly

Revisions: 1

__
TR10-196
| 8th December 2010
__

Bin Fu#### NE is not NP Turing Reducible to Nonexpoentially Dense NP Sets

__
TR10-197
| 14th December 2010
__

Albert Atserias, Elitza Maneva#### Mean-payoff games and propositional proofs

__
TR10-198
| 13th December 2010
__

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander Razborov#### Parameterized Bounded-Depth Frege is Not Optimal

__
TR10-199
| 14th December 2010
__

Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan#### Symmetric LDPC codes are not necessarily locally testable

__
TR10-200
| 14th December 2010
__

Eli Ben-Sasson, Michael Viderman#### Towards lower bounds on locally testable codes via density arguments

__
TR10-201
| 21st December 2010
__

Samir Datta, Raghav Kulkarni, Raghunath Tewari#### Perfect Matching in Bipartite Planar Graphs is in UL

Revisions: 1

__
TR10-202
| 9th December 2010
__

Bin Fu#### Multivariate Polynomial Integration and Derivative Are Polynomial Time Inapproximable unless P=NP

Iftach Haitner, Mohammad Mahmoody, David Xiao

We investigate the question of what languages can be decided efficiently with the help of a recursive collision-finding oracle. Such an oracle can be used to break collision-resistant hash functions or, more generally, statistically hiding commitments. The oracle we consider, $Sam_d$ where $d$ is the recursion depth, is based on ... more >>>

Ran Raz

We show that any explicit example for a tensor $A:[n]^r \rightarrow \mathbb{F}$ with tensor-rank

$\geq n^{r \cdot (1- o(1))}$,

(where $r = r(n) \leq \log n / \log \log n$), implies an explicit super-polynomial lower bound for the size of general arithmetic formulas over $\mathbb{F}$. This shows that strong enough ...
more >>>

Venkatesan Guruswami, Johan Håstad, Swastik Kopparty

For every fixed finite field $\F_q$, $p \in (0,1-1/q)$ and $\varepsilon >

0$, we prove that with high probability a random subspace $C$ of

$\F_q^n$ of dimension $(1-H_q(p)-\varepsilon)n$ has the

property that every Hamming ball of radius $pn$ has at most

$O(1/\varepsilon)$ codewords.

This ... more >>>

Eli Ben-Sasson, Michael Viderman

Locally testable codes (LTCs) are error-correcting codes for which membership of a given word in the code can be tested probabilistically by examining it in very few locations.

Kaufman and Sudan \cite{KS07} proved that sparse, low-bias linear codes are locally testable (in particular sparse random codes are locally testable).

Kopparty ...
more >>>

Haitao Jiang, Binhai Zhu

In this paper, we formalize a folklore concept and formally define

{\em weak kernels} for fixed-parameter computation. We show that a

problem has a (traditional) kernel then it also has a weak kernel.

It is unknown yet whether the converse is always true. On the other hand,

for a problem ...
more >>>

YI WU, Ryan O'Donnell, David Zuckerman, Parikshit Gopalan

We construct pseudorandom generators that fool functions of halfspaces (threshold functions) under a very broad class of product distributions. This class includes not only familiar cases such as the uniform distribution on the discrete cube, the uniform distribution on the solid cube, and the multivariate Gaussian distribution, but also includes ... more >>>

Atri Rudra, steve uurtamo

We prove the following results concerning the list decoding of error-correcting codes:

We show that for any code with a relative distance of $\delta$

(over a large enough alphabet), the

following result holds for random errors: With high probability,

for a $\rho\le \delta -\eps$ fraction of random errors (for any ...
more >>>

Yijia Chen, Joerg Flum

We prove that TAUT has a $p$-optimal proof system if and only if $L_\le$, a logic introduced in [Gurevich, 88], is a P-bounded logic for P. Furthermore, using the method developed in [Chen and Flum, 10], we show that TAUT has no \emph{effective} $p$-optimal proof system under some reasonable complexity-theoretic ... more >>>

A. Pavan, Raghunath Tewari, Vinodchandran Variyam

We report progress on the \NL\ vs \UL\ problem.

\begin{itemize}

\item[-] We show unconditionally that the complexity class $\ReachFewL\subseteq\UL$. This improves on the earlier known upper bound $\ReachFewL \subseteq \FewL$.

\item[-] We investigate the complexity of min-uniqueness - a central

notion in studying the \NL\ vs \UL\ problem.

more >>>

Shachar Lovett

We study two conjectures in additive combinatorics. The first is the polynomial Freiman-Ruzsa conjecture, which relates to the structure of sets with small doubling. The second is the inverse Gowers conjecture for $U^ $, which relates to functions which locally look like quadratics. In both cases a weak form, with ... more >>>

Amir Shpilka, Ilya Volkovich

An \emph{arithmetic read-once formula} (ROF for short) is a

formula (a circuit whose underlying graph is a tree) in which the

operations are $\{+,\times\}$ and such that every input variable

labels at most one leaf. A \emph{preprocessed ROF} (PROF for

short) is a ROF in which we are allowed to ...
more >>>

Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin

An $(r,\delta,\epsilon)$-locally decodable code encodes a $k$-bit message $x$ to an $N$-bit codeword $C(x),$ such that for every $i\in [k],$ the $i$-th message bit can be recovered with probability $1-\epsilon,$ by a randomized decoding procedure that reads only $r$ bits, even if the codeword $C(x)$ is corrupted in up to ... more >>>

Nitin Saxena, C. Seshadhri

We study the problem of identity testing for depth-3 circuits, over the

field of reals, of top fanin k and degree d (called sps(k,d)

identities). We give a new structure theorem for such identities and improve

the known deterministic d^{k^k}-time black-box identity test (Kayal &

Saraf, FOCS 2009) to one ...
more >>>

Daniele Micciancio, Panagiotis Voulgaris

We give deterministic $2^{O(n)}$-time algorithms to solve all the most important computational problems on point lattices in NP, including the Shortest Vector Problem (SVP), Closest Vector Problem (CVP), and Shortest Independent Vectors Problem (SIVP).

This improves the $n^{O(n)}$ running time of the best previously known algorithms for CVP (Kannan, ...
more >>>

Maurice Jansen, Youming Qiao, Jayalal Sarma

In this paper we study algebraic branching programs (ABPs) with restrictions on the order and the number of reads of variables in the program. Given a permutation $\pi$ of $n$ variables, for a $\pi$-ordered ABP ($\pi$-OABP), for any directed path $p$ from source to sink, a variable can appear at ... more >>>

Alexander Fanghänel, Sascha Geulen, Martin Hoefer, Berthold Vöcking

In this paper we study a dynamic version of capacity maximization in the physical model of wireless communication. In our model, requests for connections between pairs of points in Euclidean space of constant dimension $d$ arrive iteratively over time. When a new request arrives, an online algorithm needs to decide ... more >>>

Jonathan Ullman, Salil Vadhan

Assuming the existence of one-way functions, we show that there is no

polynomial-time, differentially private algorithm $A$ that takes a database

$D\in (\{0,1\}^d)^n$ and outputs a ``synthetic database'' $\hat{D}$ all of whose two-way

marginals are approximately equal to those of $D$. (A two-way marginal is the fraction

of database rows ...
more >>>

Vitaly Feldman

Statistical query (SQ) learning model of Kearns (1993) is a natural restriction of the PAC learning model in which a learning algorithm is allowed to obtain estimates of statistical properties of the examples but cannot see the examples themselves. We describe a new and simple characterization of the query complexity ... more >>>

Andrew Drucker

We introduce a 2-round stochastic constraint-satisfaction problem, and show that its approximation version is complete for (the promise version of) the complexity class $\mathsf{AM}$. This gives a `PCP characterization' of $\mathsf{AM}$ analogous to the PCP Theorem for $\mathsf{NP}$. Similar characterizations have been given for higher levels of the Polynomial Hierarchy, ... more >>>

Vipul Goyal, Yuval Ishai, Mohammad Mahmoody, Amit Sahai

Motivated by the question of basing cryptographic protocols on stateless tamper-proof hardware tokens, we revisit the question of unconditional two-prover zero-knowledge proofs for $NP$. We show that such protocols exist in the {\em interactive PCP} model of Kalai and Raz (ICALP '08), where one of the provers is replaced by ... more >>>

Pavel Hrubes, Avi Wigderson, Amir Yehudayoff

We initiate a direction for proving lower bounds on the size of non-commutative arithmetic circuits. This direction is based on a connection between lower bounds on the size of \emph{non-commutative} arithmetic circuits and a problem about \emph{commutative} degree four polynomials, the classical sum-of-squares problem: find the smallest $n$ such that ... more >>>

Vitaly Feldman, Homin Lee, Rocco Servedio

Much work has been done on learning various classes of ``simple'' monotone functions under the uniform distribution. In this paper we give the first unconditional lower bounds for learning problems of this sort by showing that polynomial-time algorithms cannot learn constant-depth monotone Boolean formulas under the uniform distribution in the ... more >>>

Adam Klivans, Homin Lee, Andrew Wan

In 1994, Y. Mansour conjectured that for every DNF formula on $n$ variables with $t$ terms there exists a polynomial $p$ with $t^{O(\log (1/\epsilon))}$ non-zero coefficients such that $\E_{x \in \{0,1\}}[(p(x)-f(x))^2] \leq \epsilon$. We make the first progress on this conjecture and show that it is true for several natural ... more >>>

Henning Wunderlich, Stefan Arnold

We introduce a new lower bound method for bounded-error quantum communication complexity,

the \emph{singular value method (svm)}, based on sums of squared singular values of the

communication matrix, and we compare it with existing methods.

The first finding is a constant factor improvement of lower bounds based on the

spectral ...
more >>>

Alexander A. Sherstov

The threshold degree of a function

$f\colon\{0,1\}^n\to\{-1,+1\}$ is the least degree of a

real polynomial $p$ with $f(x)\equiv\mathrm{sgn}\; p(x).$ We

prove that the intersection of two halfspaces on

$\{0,1\}^n$ has threshold degree $\Omega(n),$ which

matches the trivial upper bound and completely answers

a question due to Klivans (2002). The best ...
more >>>

Hao Huang, Benny Sudakov

Consider a graph obtained by taking edge disjoint union of $k$ complete bipartite graphs.

Alon, Saks and Seymour conjectured that such graph has chromatic number at most $k+1$.

This well known conjecture remained open for almost twenty years.

In this paper, we construct a counterexample to this

conjecture and discuss ...
more >>>

Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant

We investigate the number of samples required for testing the monotonicity of a distribution with respect to an arbitrary underlying partially ordered set. Our first result is a nearly linear lower bound for the sample complexity of testing monotonicity with respect to the poset consisting of a directed perfect matching. ... more >>>

Miklos Ajtai

Abstract. We show that oblivious on-line simulation with only

polylogarithmic increase in the time and space requirements is possible

on a probabilistic (coin flipping) RAM without using any cryptographic

assumptions. The simulation will fail with a negligible probability.

If $n$ memory locations are used, then the probability of failure is ...
more >>>

Alexandra Kolla

We present a new algorithm for Unique Games which is based on purely {\em spectral} techniques, in contrast to previous

work in the area, which relies heavily on semidefinite programming (SDP). Given a highly satisfiable instance of Unique Games, our algorithm is able to recover a good assignment.

The approximation ...
more >>>

Airat Khasianov

We consider the \emph{Hidden Subgroup} in the context of quantum \emph{Ordered Binary Decision Diagrams}.

We show several lower bounds for this function.

In this paper we also consider a slightly more general definition of the

hidden subgroup problem (in contrast to that in \cite{khashsp1}). It turns out that ...
more >>>

Christian Glaßer, Christian Reitwießner, Heinz Schmitz, Maximilian Witek

We systematically study the hardness and the approximability of combinatorial multi-objective NP optimization problems (multi-objective problems, for short).

We define solution notions that precisely capture the typical algorithmic tasks in multi-objective optimization. These notions inherit polynomial-time Turing reducibility from multivalued functions, which allows us to compare the solution notions and ... more >>>

Jack H. Lutz, Brad Shutters

The Tile Assembly Model is a Turing universal model that Winfree introduced in order to study the nanoscale self-assembly of complex (typically aperiodic) DNA crystals. Winfree exhibited a self-assembly that tiles the first quadrant of the Cartesian plane with specially labeled tiles appearing at exactly the positions of points in ... more >>>

Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka

In this paper we give the first construction of a pseudorandom generator, with seed length $O(\log n)$, for $\mathrm{CC}_0[p]$, the class of constant-depth circuits with unbounded fan-in $\mathrm{MOD}_p$ gates, for some prime $p$. More accurately, the seed length of our generator is $O(\log n)$ for any constant error $\epsilon>0$. In ... more >>>

Luca Trevisan

Three fundamental results of Levin involve algorithms or reductions

whose running time is exponential in the length of certain programs. We study the

question of whether such dependency can be made polynomial.

(1) Levin's ``optimal search algorithm'' performs at most a constant factor more slowly

than any other fixed ...
more >>>

Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff

We give new pseudorandom generators for \emph{regular} read-once branching programs of small width.

A branching program is regular if the in-degree of every vertex in it is (0 or) $2$.

For every width $d$ and length $n$,

our pseudorandom generator uses a seed of length $O((\log d + \log\log n ...
more >>>

Amir Shpilka, Ilya Volkovich

We say that a polynomial $f(x_1,\ldots,x_n)$ is {\em indecomposable} if it cannot be written as a product of two polynomials that are defined over disjoint sets of variables. The {\em polynomial decomposition} problem is defined to be the task of finding the indecomposable factors of a given polynomial. Note that ... more >>>

Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson

We present new explicit constructions of *deterministic* randomness extractors, dispersers and related objects. We say that a

distribution $X$ on binary strings of length $n$ is a

$\delta$-source if $X$ assigns probability at most $2^{-\delta n}$

to any string of length $n$. For every $\delta>0$ we construct the

following poly($n$)-time ...
more >>>

Dieter van Melkebeek, Holger Dell

Consider the following two-player communication process to decide a language $L$: The first player holds the entire input $x$ but is polynomially bounded; the second player is computationally unbounded but does not know any part of $x$; their goal is to cooperatively decide whether $x$ belongs to $L$ at small ... more >>>

Gil Cohen, Amir Shpilka

In this paper we study the degree of non-constant symmetric functions $f:\{0,1\}^n \to \{0,1,\ldots,c\}$, where $c\in

\mathbb{N}$, when represented as polynomials over the real numbers. We show that as long as $c < n$ it holds that deg$(f)=\Omega(n)$. As we can have deg$(f)=1$ when $c=n$, our

result shows a surprising ...
more >>>

Pavel Hrubes, Avi Wigderson, Amir Yehudayoff

This paper extends Valiant's work on $\vp$ and $\vnp$ to the settings in which variables are not multiplicatively commutative and/or associative. Our main result is a theory of completeness for these algebraic worlds.

We define analogs of Valiant's classes $\vp$ and $\vnp$, as well as of the polynomials permanent ...
more >>>

Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer

We present two new approximation algorithms for Unique Games. The first generalizes the results of Arora, Khot, Kolla, Steurer, Tulsiani, and Vishnoi who give polynomial time approximation algorithms for graphs with high conductance. We give a polynomial time algorithm assuming only good local conductance, i.e. high conductance for small subgraphs. ... more >>>

Thomas Watson

We prove that relative to an oracle, there is no worst-case to errorless-average-case reduction for $\NP$. This result is the first progress on an open problem posed by Impagliazzo in 1995, namely to construct an oracle relative to which $\NP$ is worst-case hard but errorless-average-case easy. We also handle classes ... more >>>

Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky

We present a logspace algorithm for computing a canonical interval representation and a canonical labeling of interval graphs. As a consequence, the isomorphism and automorphism problems for interval graphs are solvable in logspace.

more >>>Eli Ben-Sasson, Swastik Kopparty

{\em Dispersers} and {\em extractors} for affine sources of dimension $d$ in $\mathbb F_p^n$ --- where $\mathbb F_p$ denotes the finite field of prime size $p$ --- are functions $f: \mathbb F_p^n \rightarrow \mathbb F_p$ that behave pseudorandomly when their domain is restricted to any particular affine space $S \subseteq ... more >>>

Jakob Nordström

The last decade has seen a revival of interest in pebble games in the

context of proof complexity. Pebbling has proven to be a useful tool

for studying resolution-based proof systems when comparing the

strength of different subsystems, showing bounds on proof space, and

establishing size-space trade-offs. The typical approach ...
more >>>

Ján Pich

We prove that the Nisan-Wigderson generators based on computationally hard functions and suitable matrices are hard for propositional proof systems that admit feasible interpolation.

more >>>Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma

Recently Efremenko showed locally-decodable codes of sub-exponential

length. That result showed that these codes can handle up to

$\frac{1}{3} $ fraction of errors. In this paper we show that the

same codes can be locally unique-decoded from error rate

$\half-\alpha$ for any $\alpha>0$ and locally list-decoded from

error rate $1-\alpha$ ...
more >>>

David García Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet

We study the problem of monotonicity testing over the hypercube. As

previously observed in several works, a positive answer to a natural question about routing

properties of the hypercube network would imply the existence of efficient

monotonicity testers. In particular, if any $\ell$ disjoint source-sink pairs

on the directed hypercube ...
more >>>

Alexey Pospelov

We study the complexity of multiplication in noncommutative group algebras which is closely related to the complexity of matrix multiplication. We characterize such semisimple group algebras of the minimal bilinear complexity and show nontrivial lower bounds for the rest of the group algebras. These lower bounds are built on the ... more >>>

Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner

Graph isomorphism is an important and widely studied computational problem, with

a yet unsettled complexity.

However, the exact complexity is known for isomorphism of various classes of

graphs. Recently [DLN$^+$09] proved that planar graph isomorphism is complete for log-space.

We extend this result of [DLN$^+$09] further

to the ...
more >>>

Madhu Sudan

Property testing considers the task of testing rapidly (in particular, with very few samples into the data), if some massive data satisfies some given property, or is far from satisfying the property. For ``global properties'', i.e., properties that really depend somewhat on every piece of the data, one could ask ... more >>>

Melanie Winkler, Berthold Vöcking, Sascha Geulen

Suppose a decision maker has to purchase a commodity over time with

varying prices and demands. In particular, the price per unit might

depend on the amount purchased and this price function might vary from

step to step. The decision maker has a buffer of bounded size for

storing units ...
more >>>

Dana Moshkovitz, Subhash Khot

In this paper, we consider the problem of approximately solving a

system of homogeneous linear equations over reals, where each

equation contains at most three variables.

Since the all-zero assignment always satisfies all the equations

exactly, we restrict the assignments to be ``non-trivial". Here is

an informal statement of our ...
more >>>

Jan Krajicek

Let $g$ be a map defined as the Nisan-Wigderson generator

but based on an $NP \cap coNP$-function $f$. Any string $b$ outside the range of

$g$ determines a propositional tautology $\tau(g)_b$ expressing this

fact. Razborov \cite{Raz03} has conjectured that if $f$ is hard on average for

P/poly then these ...
more >>>

Eric Allender

It is a trivial observation that every decidable set has strings of length $n$ with Kolmogorov complexity $\log n + O(1)$ if it has any strings of length $n$ at all. Things become much more interesting when one asks whether a similar property holds when one

considers *resource-bounded* Kolmogorov complexity. ...
more >>>

Kord Eickmeyer, Martin Grohe

We study probabilistic complexity classes and questions of derandomisation from a logical point of view. For each logic $\mathcal{L}$ we introduce a new logic $\mathsf{BP}\mathcal{L}$, bounded error probabilistic $\mathcal{L}$, which is defined from $\mathcal{L}$ in a similar way as the

complexity class $\mathsf{BPP}$, bounded error probabilistic polynomial time, is defined ...
more >>>

Scott Aaronson, Andrew Drucker

We prove the following surprising result: given any quantum state rho on n qubits, there exists a local Hamiltonian H on poly(n) qubits (e.g., a sum of two-qubit interactions), such that any ground state of H can be used to simulate rho on all quantum circuits of fixed polynomial size. ... more >>>

Oded Goldreich, Tali Kaufman

We present a general notion of properties that

are characterized by local conditions that are invariant

under a sufficiently rich class of symmetries.

Our framework generalizes two popular models of

testing graph properties as well as the algebraic

invariances studied by Kaufman and Sudan (STOC'08).

We show that, in the ... more >>>

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria

Parameterized Resolution and, moreover, a general framework for parameterized proof complexity was introduced by Dantchev, Martin, and Szeider (FOCS'07). In that paper, Dantchev et al. show a complexity gap in tree-like Parameterized Resolution for propositional formulas arising from translations of first-order principles.

We broadly investigate Parameterized Resolution obtaining the following ...
more >>>

Dmitry Gavinsky, Alexander A. Sherstov

We prove that NP$\ne$coNP and coNP$\nsubseteq$MA in the number-on-forehead model of multiparty communication complexity for up to $k=(1-\epsilon)\log n$ players, where $\epsilon>0$ is any constant. Specifically, we construct a function $F:(\zoon)^k\to\zoo$ with co-nondeterministic

complexity $O(\log n)$ and Merlin-Arthur

complexity $n^{\Omega(1)}$.

The problem was open for $k\geq3$.

Oded Goldreich

We take another step in the study of the testability

of small-width OBDDs, initiated by Ron and Tsur (Random'09).

That is, we consider algorithms that,

given oracle access to a function $f:\{0,1\}^n\to\{0,1\}$,

need to determine whether $f$ can be implemented

by some restricted class of OBDDs or is far from

more >>>

Michael Elberfeld, Andreas Jakoby, Till Tantau

Bodlaender's Theorem states that for every $k$ there is a linear-time algorithm that decides whether an input graph has tree width~$k$ and, if so, computes a width-$k$ tree composition. Courcelle's Theorem builds on Bodlaender's Theorem and states that for every monadic second-order formula $\phi$ and for

every $k$ there is ...
more >>>

Venkatesan Guruswami, Yuan Zhou

We study the approximability of two natural Boolean constraint satisfaction problems: Horn satisfiability and exact hitting set. Under the Unique Games conjecture, we prove the following optimal inapproximability and approximability results for finding an assignment satisfying as many constraints as possible given a {\em

near-satisfiable} instance.

\begin{enumerate}

\item ...
more >>>

Xin Li

We study the problem of constructing affine extractors over $\mathsf{GF(2)}$. Previously the only known construction that can handle sources with arbitrarily linear entropy is due to Bourgain (and a slight modification by Yehudayoff), which relies heavily on the technique of Van der Corput differencing and a careful choice of a ... more >>>

Tali Kaufman, Shachar Lovett

In this work we consider linear codes which are locally testable

in a sublinear number of queries. We give the first general family

of locally testable codes of exponential size. Previous results of

this form were known only for codes of quasi-polynomial size (e.g.

Reed-Muller codes). We accomplish this by ...
more >>>

Sanjeev Arora, Rong Ge

In the {\em learning parities with noise} problem ---well-studied in learning theory and cryptography--- we

have access to an oracle that, each time we press a button,

returns a random vector $ a \in \GF(2)^n$ together with a bit $b \in \GF(2)$ that was computed as

$a\cdot u +\eta$, where ...
more >>>

Sourav Chakraborty, Eldar Fischer, Arie Matsliah

We investigate the problem of {\em local reconstruction}, as defined by Saks and Seshadhri (2008), in the context of error correcting codes.

The first problem we address is that of {\em message reconstruction}, where given oracle access to a corrupted encoding $w \in \zo^n$ of some message $x \in \zo^k$ ... more >>>

Shir Ben-Israel, Eli Ben-Sasson, David Karger

This paper shows that the use of ``local symmetry breaking'' can dramatically reduce the length of propositional refutations. For each of the three propositional proof systems known as (i) treelike resolution, (ii) resolution, and (iii) k-DNF resolution, we describe families of unsatisfiable formulas in conjunctive normal form (CNF) that are ... more >>>

Eric Allender, Vikraman Arvind, Fengming Wang

A recurring theme in the literature on derandomization is that probabilistic

algorithms can be simulated quickly by deterministic algorithms, if one can obtain *impressive* (i.e., superpolynomial, or even nearly-exponential) circuit size lower bounds for certain problems. In contrast to what is

needed for derandomization, existing lower bounds seem rather pathetic ...
more >>>

Eric Allender, Klaus-Joern Lange

We show that every language accepted by a nondeterministic auxiliary pushdown automaton in polynomial time (that is, every language in SAC$^1$ = LogCFL) can be accepted by a symmetric auxiliary pushdown automaton in polynomial time.

Rahul Jain, Ashwin Nayak

We show an Omega(sqrt(n)/T^3) lower bound for the space required by any

unidirectional constant-error randomized T-pass streaming algorithm that recognizes whether an expression over two types of parenthesis is well-parenthesized. This proves a conjecture due to Magniez, Mathieu, and Nayak

(2009) and rigorously establishes the peculiar power of bi-directional streams ...
more >>>

Russell Impagliazzo, Valentine Kabanets

We give a simple combinatorial proof of the Chernoff-Hoeffding concentration bound~\cite{Chernoff, Hof63}, which says that the sum of independent $\{0,1\}$-valued random variables is highly concentrated around the expected value. Unlike the standard proofs,

our proof does not use the method of higher moments, but rather uses a simple ...
more >>>

Neeraj Kayal

Given a multivariate polynomial f(x) in F[x] as an arithmetic circuit we would like to efficiently determine:

(i) [Identity Testing.] Is f(x) identically zero?

(ii) [Degree Computation.] Is the degree of the

polynomial f(x) at most a given integer d.

(iii) [Polynomial Equivalence.] Upto an ...
more >>>

Parikshit Gopalan, Rocco Servedio

In 2002 Jackson et al. [JKS02] asked whether AC0 circuits augmented with a threshold gate at the output can be efficiently learned from uniform random examples. We answer this question affirmatively by showing that such circuits have fairly strong Fourier concentration; hence the low-degree algorithm of Linial, Mansour and Nisan ... more >>>

Ben Reichardt

Span programs form a linear-algebraic model of computation, with span program "size" used in proving classical lower bounds. Quantum query complexity is a coherent generalization, for quantum algorithms, of classical decision-tree complexity. It is bounded below by a semi-definite program (SDP) known as the general adversary bound. We connect these ... more >>>

Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor

This paper makes three main contributions to the theory of communication complexity and stream computation. First, we present new bounds on the information complexity of AUGMENTED-INDEX. In contrast to analogous results for INDEX by Jain, Radhakrishnan and Sen [J. ACM, 2009], we have to overcome the significant technical challenge that ... more >>>

Venkatesan Guruswami, Adam Smith

In this paper, we consider coding schemes for computationally bounded channels, which can introduce an arbitrary set of errors as long as (a) the fraction of errors is bounded with high probability by a parameter p and (b) the process which adds the errors can be described by a sufficiently ... more >>>

Holger Dell, Thore Husfeldt, Martin Wahlén

The Exponential Time Hypothesis (ETH) says that deciding the satisfiability of $n$-variable 3-CNF formulas requires time $\exp(\Omega(n))$. We relax this hypothesis by introducing its counting version #ETH, namely that every algorithm that counts the satisfying assignments requires time $\exp(\Omega(n))$. We transfer the sparsification lemma for $d$-CNF formulas to the counting ... more >>>

Samir Datta, Raghav Kulkarni, Raghunath Tewari, Vinodchandran Variyam

We investigate the space complexity of certain perfect matching

problems over bipartite graphs embedded on surfaces of constant genus

(orientable or non-orientable). We show that the problems of deciding

whether such graphs have (1) a perfect matching or not and (2) a

unique perfect matching or not, are in the ...
more >>>

Andrew Drucker

The direct product problem is a fundamental question in complexity theory which seeks to understand how the difficulty of computing a function on each of $k$ independent inputs scales with $k$.

We prove the following direct product theorem (DPT) for query complexity: if every $T$-query algorithm

has success probability at ...
more >>>

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria

In this note we show that the asymmetric Prover-Delayer game developed by Beyersdorff, Galesi, and Lauria (ECCC TR10-059) for Parameterized Resolution is also applicable to other tree-like proof systems. In particular, we use this asymmetric Prover-Delayer game to show a lower bound of the form $2^{\Omega(n\log n)}$ for the pigeonhole ... more >>>

Oded Goldreich

The aim of this article is to introduce the reader to the study

of testing graph properties, while focusing on the main models

and issues involved. No attempt is made to provide a

comprehensive survey of this study, and specific results

are often mentioned merely as illustrations of general ...
more >>>

Mark Braverman, Anup Rao

We show how to efficiently simulate the sending of a message M to a receiver who has partial information about the message, so that the expected number of bits communicated in the simulation is close to the amount of additional information that the message reveals to the receiver.

We ... more >>>

Maurice Jansen, Youming Qiao, Jayalal Sarma

An algebraic branching program (ABP) is given by a directed acyclic graph with source and sink vertices $s$ and $t$, respectively, and where edges are labeled by variables or field constants. An ABP computes the sum of weights of all directed paths from $s$ to $t$, where the weight of ... more >>>

Eli Ben-Sasson, Jan Johannsen

It has been observed empirically that clause learning does not significantly improve the performance of a SAT solver when restricted

to learning clauses of small width only. This experience is supported by lower bound theorems. It is shown that lower bounds on the runtime of width-restricted clause learning follow from ...
more >>>

Henning Wunderlich

In an unpublished Russian manuscript Razborov proved that a matrix family with high

rigidity over a finite field would yield a language outside the polynomial hierarchy

in communication complexity.

We present an alternative proof that strengthens the original result in several ways.

In particular, we replace rigidity by the strictly ...
more >>>

Shachar Lovett, Ely Porat

An approximate membership data structure is a randomized data

structure for representing a set which supports membership

queries. It allows for a small false positive error rate but has

no false negative errors. Such data structures were first

introduced by Bloom in the 1970's, and have since had numerous

applications, ...
more >>>

Jiri Sima, Stanislav Zak

The relationship between deterministic and probabilistic computations is one of the central issues in complexity theory. This problem can be tackled by constructing polynomial time hitting set generators which, however, belongs to the hardest problems in computer science even for severely restricted computational models. In our work, we consider read-once ... more >>>

Iftach Haitner, Omer Reingold, Salil Vadhan

We give a new construction of pseudorandom generators from any one-way function. The construction achieves better parameters and is simpler than that given in the seminal work of Haastad, Impagliazzo, Levin and Luby [SICOMP '99]. The key to our construction is a new notion of next-block pseudoentropy, which is inspired ... more >>>

Nikolay Vereshchagin

We express some criticism about the definition of an algorithmic sufficient statistic and, in particular, of an algorithmic minimal sufficient statistic. We propose another definition, which has better properties.

more >>>Nikolay Vereshchagin

When we represent a decision problem,like CIRCUIT-SAT, as a language over the binary alphabet,

we usually do not specify how to encode instances by binary strings.

This relies on the empirical observation that the truth of a statement of the form ``CIRCUIT-SAT belongs to a complexity class $C$''

more >>>

Charanjit Jutla, Arnab Roy

We consider multivariate pseudo-linear functions

over finite fields of characteristic two. A pseudo-linear polynomial

is a sum of guarded linear-terms, where a guarded linear-term is a product of one or more linear-guards

and a single linear term, and each linear-guard is

again a linear term but raised ...
more >>>

Sourav Chakraborty, David García Soriano, Arie Matsliah

In this paper we study the problem of testing structural equivalence (isomorphism) between a pair of Boolean

functions $f,g:\zo^n \to \zo$. Our main focus is on the most studied case, where one of the functions is given (explicitly), and the other function can be queried.

We prove that for every ... more >>>

Ajesh Babu, Nutan Limaye, Girish Varma

In this paper, we give streaming algorithms for some problems which are known to be in deterministic log-space, when the number of passes made on the input is unbounded. If the input data is massive,

the conventional deterministic log-space algorithms may not run efficiently. We study the complexity of the ...
more >>>

Masaki Yamamoto

In [FOCS1998],

Paturi, Pudl\'ak, Saks, and Zane proposed a simple randomized algorithm

for finding a satisfying assignment of a $k$-CNF formula.

The main lemma of the paper is as follows:

Given a satisfiable $k$-CNF formula that

has a $d$-isolated satisfying assignment $z$,

the randomized algorithm finds $z$

with probability at ...
more >>>

Dana Moshkovitz

We show a non-inductive proof of the Schwartz-Zippel lemma. The lemma bounds the number of zeros of a multivariate low degree polynomial over a finite field.

more >>>Iddo Tzameret

We study possible formulations of algebraic propositional proof systems operating with noncommutative formulas. We observe that a simple formulation gives rise to systems at least as strong as Frege--yielding a semantic way to define a Cook-Reckhow (i.e., polynomially verifiable) algebraic analogue of Frege proofs, different from that given in Buss ... more >>>

Daniel Kane, Jelani Nelson

Recent work of [Dasgupta-Kumar-Sarl\'{o}s, STOC 2010] gave a sparse Johnson-Lindenstrauss transform and left as a main open question whether their construction could be efficiently derandomized. We answer their question affirmatively by giving an alternative proof of their result requiring only bounded independence hash functions. Furthermore, the sparsity bound obtained in ... more >>>

T.C. Vijayaraghavan

Recently in [Vij09, Corollary 3.7] the complexity class ModL has been shown to be closed under complement assuming NL = UL. In this note we continue to show many other closure properties of ModL which include the following.

1. ModL is closed under $\leq ^L_m$ reduction, $\vee$(join) and $\leq ^{UL}_m$ ... more >>>

Amit Chakrabarti

The deterministic space complexity of approximating the length of the longest increasing subsequence of

a stream of $N$ integers is known to be $\widetilde{\Theta}(\sqrt N)$. However, the randomized

complexity is wide open. We show that the technique used in earlier work to establish the $\Omega(\sqrt

N)$ deterministic lower bound fails ...
more >>>

Samir Datta, Meena Mahajan, Raghavendra Rao B V, Michael Thomas, Heribert Vollmer

The class NC$^1$ of problems solvable by bounded fan-in circuit families of logarithmic depth is known to be contained in logarithmic space L, but not much about the converse is known. In this paper we examine the structure of classes in between NC$^1$ and L based on counting functions or, ... more >>>

Per Kristian Lehre, Carsten Witt

The complexity theory for black-box algorithms, introduced by

Droste et al. (2006), describes common limits on the efficiency of

a broad class of randomised search heuristics. There is an

obvious trade-off between the generality of the black-box model

and the strength of the bounds that can be proven in such ...
more >>>

Andreas Krebs, Nutan Limaye, Meena Mahajan

We give a \#NC$^1$ upper bound for the problem of counting accepting paths in any fixed visibly pushdown automaton. Our algorithm involves a non-trivial adaptation of the arithmetic formula evaluation algorithm of Buss, Cook, Gupta, Ramachandran (BCGR: SICOMP 21(4), 1992). We also show that the problem is \#NC$^1$ hard. Our ... more >>>

Paul Beame, Widad Machmouchi

We prove a time-space tradeoff lower bound of $T =

\Omega\left(n\log(\frac{n}{S}) \log \log(\frac{n}{S})\right) $ for

randomized oblivious branching programs to compute $1GAP$, also

known as the pointer jumping problem, a problem for which there is a

simple deterministic time $n$ and space $O(\log n)$ RAM (random

access machine) algorithm.

In ... more >>>

Scott Aaronson, Dieter van Melkebeek

We present an alternate proof of the result by Kabanets and Impagliazzo that derandomizing polynomial identity testing implies circuit lower bounds. Our proof is simpler, scales better, and yields a somewhat stronger result than the original argument.

more >>>Yuichi Yoshida

Raghavendra (STOC 2008) gave an elegant and surprising result: if Khot's Unique Games Conjecture (STOC 2002) is true, then for every constraint satisfaction problem (CSP), the best approximation ratio is attained by a certain simple semidefinite programming and a rounding scheme for it.

In this paper, we show that a ...
more >>>

Irit Dinur, Or Meir

A PCP is a proof system for NP in which the proof can be checked by a probabilistic verifier. The verifier is only allowed to read a very small portion of the proof, and in return is allowed to err with some bounded probability. The probability that the verifier accepts ... more >>>

Eli Ben-Sasson, Madhu Sudan

A linear code is said to be affine-invariant if the coordinates of the code can be viewed as a vector space and the code is invariant under an affine transformation of the coordinates. A code is said to be locally testable if proximity of a received word

to the code ...
more >>>

Scott Aaronson

In earlier work, we gave an oracle separating the relational versions of BQP and the polynomial hierarchy, and showed that an oracle separating the decision versions would follow from what we called the Generalized Linial-Nisan (GLN) Conjecture: that "almost k-wise independent" distributions are indistinguishable from the uniform distribution by constant-depth ... more >>>

Ben Reichardt

Quantum query complexity measures the number of input bits that must be read by a quantum algorithm in order to evaluate a function. Hoyer et al. (2007) have generalized the adversary semi-definite program that lower-bounds quantum query complexity. By giving a matching algorithm, we show that the general adversary lower ... more >>>

Venkatesan Guruswami, Ali Kemal Sinop

We prove almost tight hardness results for finding independent sets in bounded degree graphs and hypergraphs that admit a good

coloring. Our specific results include the following (where $\Delta$, assumed to be a constant, is a bound on the degree, and

$n$ is the number of vertices):

Subhash Khot, Dana Moshkovitz

In this paper, we consider the problem of approximately solving a system of homogeneous linear equations over reals, where each

equation contains at most three variables.

Since the all-zero assignment always satisfies all the equations exactly, we restrict the assignments to be ``non-trivial". Here is

an informal statement of our ...
more >>>

Michal Koucky, Prajakta Nimbhorkar, Pavel Pudlak

We prove that the pseudorandom generator introduced in Impagliazzo et al. (1994) fools group products of a given finite group. The seed length is $O(\log n \log 1 / \epsilon)$, where $n$ is the length of the word and $\epsilon$ is the error. The result is equivalent to the statement ... more >>>

Zhixiang Chen, Bin Fu

The work in this paper is to initiate a theory of testing

monomials in multivariate polynomials. The central question is to

ask whether a polynomial represented by certain economically

compact structure has a multilinear monomial in its sum-product

expansion. The complexity aspects of this problem and its variants

are investigated ...
more >>>

Shachar Lovett, Emanuele Viola

We study a variant of the classical circuit-lower-bound problems: proving lower bounds for sampling distributions given random bits. We prove a lower bound of $1-1/n^{\Omega(1)}$ on the statistical distance between (i) the output distribution of any small constant-depth (a.k.a.~$\mathrm{AC}^0$) circuit $f : \{0,1\}^{\mathrm{poly}(n)} \to \{0,1\}^n$, and (ii) the uniform distribution ... more >>>

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

The rich collection of successes in property testing raises a natural question: Why are so many different properties turning out to be locally testable? Are there some broad "features" of properties that make them testable? Kaufman and Sudan (STOC 2008) proposed the study of the relationship between the invariances satisfied ... more >>>

Arkadev Chattopadhyay, Jacobo Toran, Fabian Wagner

We give a new upper bound for the Group and Quasigroup

Isomorphism problems when the input structures

are given explicitly by multiplication tables. We show that these problems can be computed by polynomial size nondeterministic circuits of unbounded fan-in with $O(\log\log n)$ depth and $O(\log^2 n)$ nondeterministic bits, ...
more >>>

Maurice Jansen

For two polynomials $f \in \mathbb{F}[x_1, x_2, \ldots, x_n, y]$ and $p \in \mathbb{F}[x_1, x_2, \ldots, x_n]$, we say that $p$ is a root of $f$, if $f(x_1, x_2, \ldots, x_n, p) \equiv 0$. We study the relation between the arithmetic circuit sizes of $f$ and $p$ for general circuits ... more >>>

Michal Moshkovitz

A distance estimator is a code together with a randomized algorithm. The algorithm approximates the distance of any word from the code by making a small number of queries to the word. One such example is the Reed-Muller code equipped with an appropriate algorithm. It has polynomial length, polylogarithmic alphabet ... more >>>

Noa Eidelstein, Alex Samorodnitsky

A design is a finite set of points in a space on which every "simple" functions averages to its global mean. Illustrative examples of simple functions are low-degree polynomials on the Euclidean sphere or on the Hamming cube.

We prove lower bounds on designs in spaces with a large group ... more >>>

Ashwin Nayak

We describe a reduction from the problem of unordered search(with a unique solution) to the problem of inverting a permutation. Since there is a straightforward reduction in the reverse direction, the problems are essentially equivalent.

The reduction helps us bypass the Bennett-Bernstein-Brassard-Vazirani hybrid argument (1997} and the Ambainis quantum adversary ... more >>>

Zhixiang Chen, Bin Fu, Yang Liu, Robert Schweller

This paper is our second step towards developing a theory of

testing monomials in multivariate polynomials. The central

question is to ask whether a polynomial represented by an

arithmetic circuit has some types of monomials in its sum-product

expansion. The complexity aspects of this problem and its variants

have been ...
more >>>

Eli Ben-Sasson

This paper describes recent results which revolve around the question of the rate attainable by families of error correcting codes that are locally testable. Emphasis is placed on motivating the problem of proving upper bounds on the rate of these codes and a number of interesting open questions for future ... more >>>

Zhixiang Chen, Bin Fu

This paper is our third step towards developing a theory of testing monomials in multivariate polynomials and concentrates on two problems: (1) How to compute the coefficients of multilinear monomials; and (2) how to find a maximum multilinear monomial when the input is a $\Pi\Sigma\Pi$ polynomial.

We first prove ...
more >>>

Eli Ben-Sasson, Jakob Nordström

For current state-of-the-art satisfiability algorithms based on the DPLL procedure and clause learning, the two main bottlenecks are the amounts of time and memory used. In the field of proof complexity, these resources correspond to the length and space of resolution proofs for formulas in conjunctive normal form (CNF). There ... more >>>

Thomas Watson

An errorless circuit for a boolean function is one that outputs the correct answer or ``don't know'' on each input (and never outputs the wrong answer). The goal of errorless hardness amplification is to show that if $f$ has no size $s$ errorless circuit that outputs ``don't know'' on at ... more >>>

Brett Hemenway, Rafail Ostrovsky

Injective one-way trapdoor functions are one of the most fundamental cryptographic primitives. In this work we give a novel construction of injective trapdoor functions based on oblivious transfer for long strings.

Our main result is to show that any 2-message statistically sender-private semi-honest oblivious transfer (OT) for ...
more >>>

Scott Aaronson

In a sampling problem, we are given an input $x\in\left\{0,1\right\} ^{n}$, and asked to sample approximately from a probability

distribution $D_{x}$ over poly(n)-bit strings. In a search problem, we are given an input

$x\in\left\{ 0,1\right\} ^{n}$, and asked to find a member of a nonempty set

$A_{x}$ with high probability. ...
more >>>

Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel

The area of derandomization attempts to provide efficient deterministic simulations of randomized algorithms in various algorithmic settings. Goldreich and Wigderson introduced a notion of "typically-correct" deterministic simulations, which are allowed to err on few inputs. In this paper we further the study of typically-correct derandomization in two ways.

First, we ... more >>>

Tali Kaufman, Michael Viderman

We study the relation between locally testable and locally decodable codes.

Locally testable codes (LTCs) are error-correcting codes for which membership of a given word in the code can be tested probabilistically by examining it in very few locations. Locally decodable codes (LDCs) allow to recover each message entry with ...
more >>>

Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, Shinnosuke Seki

We investigate the role of nondeterminism in Winfree's abstract Tile Assembly Model (aTAM), which was conceived to model artificial molecular self-assembling systems constructed from DNA. Designing tile systems that assemble shapes, due to the algorithmic richness of the aTAM, is a form of sophisticated "molecular programming". Of particular practical importance ... more >>>

Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson

We study constraint satisfaction problems on the domain $\{-1,1\}$, where the given constraints are homogeneous linear threshold predicates. That is, predicates of the form $\mathrm{sgn}(w_1 x_1 + \cdots + w_n x_n)$ for some positive integer weights $w_1, \dots, w_n$. Despite their simplicity, current techniques fall short of providing a classification ... more >>>

Parikshit Gopalan, Adam Klivans, Raghu Meka

We give a deterministic, polynomial-time algorithm for approximately counting the number of {0,1}-solutions to any instance of the knapsack problem. On an instance of length n with total weight W and accuracy parameter eps, our algorithm produces a (1 + eps)-multiplicative approximation in time poly(n,log W,1/eps). We also give algorithms ... more >>>

Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma

We show a generic, simple way to amplify the error-tolerance of locally decodable codes.

Specifically, we show how to transform a locally decodable code that can tolerate a constant fraction of errors

to a locally decodable code that can recover from a much higher error-rate. We also show how to ...
more >>>

Oded Goldreich

We show that proving results such as BPP=P essentially

necessitate the construction of suitable pseudorandom generators

(i.e., generators that suffice for such derandomization results).

In particular, the main incarnation of this equivalence

refers to the standard notion of uniform derandomization

and to the corresponding pseudorandom generators

(i.e., the standard uniform ...
more >>>

Arnab Bhattacharyya, Elena Grigorescu, Jakob Nordström, Ning Xie

Properties of Boolean functions on the hypercube that are invariant

with respect to linear transformations of the domain are among some of

the most well-studied properties in the context of property testing.

In this paper, we study a particular natural class of linear-invariant

properties, called matroid freeness properties. These properties ...
more >>>

Or Meir

The IP theorem, which asserts that IP = PSPACE (Lund et. al., and Shamir, in J. ACM 39(4)), is one of the major achievements of complexity theory. The known proofs of the theorem are based on the arithmetization technique, which transforms a quantified Boolean formula into a related polynomial. The ... more >>>

Eric Allender, Luke Friedman, William Gasarch

In this paper we give an exposition of a theorem by Muchnik and Positselsky, showing that there is a universal prefix Turing machine U, with the property that there is no truth-table reduction from the halting problem to the set {(x,i) : there is a description d of length at ... more >>>

Eric Allender, Luke Friedman, William Gasarch

Let C(x) and K(x) denote plain and prefix Kolmogorov complexity, respectively, and let R_C and R_K denote the sets of strings that are ``random'' according to these measures; both R_K and R_C are undecidable. Earlier work has shown that every set in NEXP is in NP relative to both R_K ... more >>>

Amit Chakrabarti, Oded Regev

We prove an optimal $\Omega(n)$ lower bound on the randomized

communication complexity of the much-studied

Gap-Hamming-Distance problem. As a consequence, we

obtain essentially optimal multi-pass space lower bounds in the

data stream model for a number of fundamental problems, including

the estimation of frequency moments.

The Gap-Hamming-Distance problem is a ... more >>>

Ran Raz

Reason: This paper has been remove on the author's behalf. Please note that TR10-142 is the corrected version.

Ran Raz, Ricky Rosen

The parallel repetition theorem states that for any Two

Prover Game with value at most $1-\epsilon$ (for $\epsilon<1/2$),

the value of the game repeated $n$ times in parallel is at most

$(1-\epsilon^3)^{\Omega(n/s)}$, where $s$ is the length of the

answers of the two provers. For Projection

Games, the bound on ...
more >>>

Bo'az Klartag, Oded Regev

In STOC 1999, Raz presented a (partial) function for which there is a quantum protocol

communicating only $O(\log n)$ qubits, but for which any classical (randomized, bounded-error) protocol requires $\poly(n)$ bits of communication. That quantum protocol requires two rounds of communication. Ever since Raz's paper it was open whether the ...
more >>>

Eli Ben-Sasson, Noga Ron-Zewi

Two-source and affine extractors and dispersers are fundamental objects studied in the context of derandomization. This paper shows how to construct two-source extractors and dispersers for arbitrarily small min-entropy rate in a black-box manner from affine extractors with sufficiently good parameters. Our analysis relies on the study of approximate duality, ... more >>>

Ron Rothblum

Trapdoor permutations (TDPs) are among the most widely studied

building blocks of cryptography. Despite the extensive body of

work that has been dedicated to their study, in many setting and

applications (enhanced) trapdoor permutations behave

unexpectedly. In particular, a TDP may become easy to invert when

the inverter is given ...
more >>>

Ron Rothblum

We show that any private-key encryption scheme that is weakly

homomorphic with respect to addition modulo 2, can be transformed

into a public-key encryption scheme. The homomorphic feature

referred to is a minimalistic one; that is, the length of a

homomorphically generated encryption should be independent of the

number of ...
more >>>

Dieter van Melkebeek, Thomas Watson

We give two time- and space-efficient simulations of quantum computations with

intermediate measurements, one by classical randomized computations with

unbounded error and the other by quantum computations that use an arbitrary

fixed universal set of gates. Specifically, our simulations show that every

language solvable by a bounded-error quantum algorithm running ...
more >>>

Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin

Locally decodable codes are error-correcting codes that admit efficient decoding algorithms; any bit of the original message can be recovered by looking at only a small number of locations of a corrupted codeword. The tradeoff between the rate of a code and the locality/efficiency of its decoding algorithms has been ... more >>>

Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff

A $(q,k,t)$-design matrix is an m x n matrix whose pattern of zeros/non-zeros satisfies the following design-like condition: each row has at most $q$ non-zeros, each column has at least $k$ non-zeros and the supports of every two columns intersect in at most t rows. We prove that the rank ... more >>>

Bjørn Kjos-Hanssen

We show that in the setting of fair-coin measure on the power set of the natural numbers, each sufficiently random set has an infinite subset that computes no random set. That is, there is an almost sure event $\mathcal A$ such that if $X\in\mathcal A$ then $X$ has an infinite ... more >>>

Raghunath Tewari, Vinodchandran Variyam

We show a simple application of Green’s theorem from multivariable calculus to the isolation problem in planar graphs. In particular, we construct a skew-symmetric, polynomially bounded, edge weight function for a directed planar graph in logspace such that the weight of any simple cycle in the graph is non-zero with ... more >>>

Alexey Pospelov

We study the complexity of polynomial multiplication over arbitrary fields. We present a unified approach that generalizes all known asymptotically fastest algorithms for this problem. In particular, the well-known algorithm for multiplication of polynomials over fields supporting DFTs of large smooth orders, Schönhage-Strassen's algorithm over arbitrary fields of characteristic different ... more >>>

Lorenzo Carlucci, Nicola Galesi, Massimo Lauria

We initiate the study of the proof complexity of propositional encoding of (weak cases of) concrete independence results. In particular we study the proof complexity of Paris-Harrington's Large Ramsey Theorem. We prove a conditional lower bound in Resolution and a quasipolynomial upper bound in bounded-depth Frege.

more >>>Derrick Stolee, Vinodchandran Variyam

We consider the reachability problem for a certain class of directed acyclic graphs embedded on surfaces. Let ${\cal G}(m,g)$ be the class of directed acyclic graphs with $m = m(n)$ source vertices embedded on a surface (orientable or non-orientable) of genus $g = g(n)$. We give a log-space reduction that ... more >>>

Brendan Juba, Madhu Sudan

In previous works, Juba and Sudan (STOC 2008) and Goldreich, Juba and Sudan (ECCC TR09-075) considered the idea of "semantic communication", wherein two players, a user and a server, attempt to communicate with each other without any prior common language (or communication protocol). They showed that if communication was goal-oriented ... more >>>

Victor Chen, Madhu Sudan, Ning Xie

Given two testable properties $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$, under what conditions are the union, intersection or set-difference

of these two properties also testable?

We initiate a systematic study of these basic set-theoretic operations in the context of property

testing. As an application, we give a conceptually different proof that linearity is ...
more >>>

Reut Levi, Dana Ron, Ronitt Rubinfeld

We propose a framework for studying property testing of collections of distributions,

where the number of distributions in the collection is a parameter of the problem.

Previous work on property testing of distributions considered

single distributions or pairs of distributions. We suggest two models that differ

in the way the ...
more >>>

Shiva Kintali

A celebrated theorem of Savitch states that NSPACE(S) is contained DSPACE(S^2). In particular, Savitch gave a deterministic algorithm to solve ST-CONNECTIVITY (an NL-complete problem) using O(log^2{n}) space, implying NL is in DSPACE(log^2{n}). While Savitch’s theorem itself has not been improved in the last four decades, studying the space complexity of ... more >>>

Graham Cormode, Justin Thaler, Ke Yi

Applications based on outsourcing computation require guarantees to the data owner that the desired computation has been performed correctly by the service provider. Methods based on proof systems can give the data owner the necessary assurance, but previous work does not give a sufficiently scalable and practical solution, requiring a ... more >>>

Zeev Dvir, Dan Gutfreund, Guy Rothblum, Salil Vadhan

We investigate the complexity of the following computational problem:

Polynomial Entropy Approximation (PEA):

Given a low-degree polynomial mapping

$p : F^n\rightarrow F^m$, where $F$ is a finite field, approximate the output entropy

$H(p(U_n))$, where $U_n$ is the uniform distribution on $F^n$ and $H$ may be any of several entropy measures.

Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira

The study of the interplay between the testability of properties of Boolean functions and the invariances acting on their domain which preserve the property was initiated by Kaufman and Sudan (STOC 2008). Invariance with respect to F_2-linear transformations is arguably the most common symmetry exhibited by natural properties of Boolean ... more >>>

Zohar Karnin

For any $00$, we give an efficient

deterministic construction of a linear subspace $V \subseteq

\R^n$, of dimension $(1-\epsilon)n$ in which the $\ell_p$ and

$\ell_r$ norms are the same up to a multiplicative factor of

$\poly(\epsilon^{-1})$ (after the correct normalization). As a

corollary we get a deterministic compressed sensing algorithm

more >>>

Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolay Vereshchagin

It is well-known that the class of sets that can be computed by polynomial size circuits is equal to the class of sets that are polynomial time reducible to a sparse set. It is widely believed, but unfortunately up to now unproven, that there are sets in $EXP^{NP}$, or even ... more >>>

Falk Unger

We consider fault-tolerant computation with formulas composed of noisy Boolean gates with two input wires. In our model all gates fail independently of each other and of the input. When a gate fails, it outputs the opposite of the correct output. It is known that if all gates fail with ... more >>>

Dmitry Gavinsky, Tsuyoshi Ito

We introduce a new type of cryptographic primitive that we call hiding fingerprinting. No classical fingerprinting scheme is hiding. We construct quantum hiding fingerprinting schemes and argue their optimality.

more >>>Mark Braverman, Anup Rao

We show that it is possible to encode any communication protocol

between two parties so that the protocol succeeds even if a $(1/4 -

\epsilon)$ fraction of all symbols transmitted by the parties are

corrupted adversarially, at a cost of increasing the communication in

the protocol by a constant factor ...
more >>>

Nitin Saxena, C. Seshadhri

Let C be a depth-3 circuit with n variables, degree d and top fanin k (called sps(k,d,n) circuits) over base field F.

It is a major open problem to design a deterministic polynomial time blackbox algorithm

that tests if C is identically zero.

Klivans & Spielman (STOC 2001) observed ...
more >>>

Thomas Watson

We define a combinatorial checkerboard to be a function $f:\{1,\ldots,m\}^d\to\{1,-1\}$ of the form $f(u_1,\ldots,u_d)=\prod_{i=1}^df_i(u_i)$ for some functions $f_i:\{1,\ldots,m\}\to\{1,-1\}$. This is a variant of combinatorial rectangles, which can be defined in the same way but using $\{0,1\}$ instead of $\{1,-1\}$. We consider the problem of constructing explicit pseudorandom generators for combinatorial ... more >>>

Siavosh Benabbas, Konstantinos Georgiou, Avner Magen

We study the performance of the Sherali-Adams system for VERTEX COVER on graphs with vector

chromatic number $2+\epsilon$. We are able to construct solutions for LPs derived by any number of Sherali-Adams tightenings by introducing a new tool to establish Local-Global Discrepancy. When restricted to

$O(1/ \epsilon)$ tightenings we show ...
more >>>

Scott Aaronson, Alex Arkhipov

We give new evidence that quantum computers -- moreover, rudimentary quantum computers built entirely out of linear-optical elements -- cannot be efficiently simulated by classical computers. In particular, we define a

model of computation in which identical photons are generated, sent through a linear-optical network, then nonadaptively measured to count ...
more >>>

Michael Viderman

Inspired by recent construction of high-rate locally correctable codes with sublinear query complexity due to

Kopparty, Saraf and Yekhanin (2010) we address the similar question for locally testable codes (LTCs).

In this note we show a construction of high-rate LTCs with sublinear query complexity.

More formally, we show that for ...
more >>>

Prasad Raghavendra, David Steurer, Madhur Tulsiani

The Small-Set Expansion Hypothesis (Raghavendra, Steurer, STOC 2010) is a natural hardness assumption concerning the problem of approximating the edge expansion of small sets in graphs. This hardness assumption is closely connected to the Unique Games Conjecture (Khot, STOC 2002). In particular, the Small-Set Expansion Hypothesis implies the Unique ... more >>>

Yeow Meng Chee, Tao Feng, San Ling, Huaxiong Wang, Liang Feng Zhang

A $k$-query locally decodable code (LDC)

$\textbf{C}:\Sigma^{n}\rightarrow \Gamma^{N}$ encodes each message $x$ into

a codeword $\textbf{C}(x)$ such that each symbol of $x$ can be probabilistically

recovered by querying only $k$ coordinates of $\textbf{C}(x)$, even after a

constant fraction of the coordinates have been corrupted.

Yekhanin (2008)

constructed a $3$-query LDC ...
more >>>

Scott Aaronson, Baris Aydinlioglu, Harry Buhrman, John Hitchcock, Dieter van Melkebeek

We present an alternate proof of the recent result by Gutfreund and Kawachi that derandomizing Arthur-Merlin games into $P^{NP}$ implies linear-exponential circuit lower bounds for $E^{NP}$. Our proof is simpler and yields stronger results. In particular, consider the promise-$AM$ problem of distinguishing between the case where a given Boolean circuit ... more >>>

Emanuele Viola

We show that the promise problem of distinguishing $n$-bit strings of hamming weight $\ge 1/2 + \Omega(1/\log^{d-1} n)$ from strings of weight $\le 1/2 - \Omega(1/\log^{d-1} n)$ can be solved by explicit, randomized (unbounded-fan-in) poly(n)-size depth-$d$ circuits with error $\le 1/3$, but cannot be solved by deterministic poly(n)-size depth-$(d+1)$ circuits, ... more >>>

Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman

We construct pseudorandom generators for combinatorial shapes, which substantially generalize combinatorial rectangles, small-bias spaces, 0/1 halfspaces, and 0/1 modular sums. A function $f:[m]^n \rightarrow \{0,1\}^n$ is an $(m,n)$-combinatorial shape if there exist sets $A_1,\ldots,A_n \subseteq [m]$ and a symmetric function $h:\{0,1\}^n \rightarrow \{0,1\}$ such that $f(x_1,\ldots,x_n) = h(1_{A_1} (x_1),\ldots,1_{A_n}(x_n))$. Our ... more >>>

Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu

The Unique Games conjecture (UGC) has emerged in recent years as the starting point for several optimal inapproximability results. While for none of these results a reverse reduction to Unique Games is known, the assumption of bijective projections in the Label Cover instance seems critical in these proofs. In this ... more >>>

Amir Shpilka, Avishay Tal

In this paper we give a new upper bound on the minimal degree of a nonzero Fourier coefficient in any non-linear symmetric Boolean function.

Specifically, we prove that for every non-linear and symmetric $f:\{0,1\}^{k} \to \{0,1\}$ there exists a set $\emptyset\neq S\subset[k]$ such that $|S|=O(\Gamma(k)+\sqrt{k})$, and $\hat{f}(S) \neq 0$, where ...
more >>>

Gregory Valiant, Paul Valiant

We prove two new multivariate central limit theorems; the first relates the sum of independent distributions to the multivariate Gaussian of corresponding mean and covariance, under the earthmover distance matric (also known as the Wasserstein metric). We leverage this central limit theorem to prove a stronger but more specific central ... more >>>

Gregory Valiant, Paul Valiant

We introduce a new approach to characterizing the unobserved portion of a distribution, which provides sublinear-sample additive estimators for a class of properties that includes entropy and distribution support size. Together with the lower bounds proven in the companion paper [29], this settles the longstanding question of the sample complexities ... more >>>

Hamed Hatami, Shachar Lovett

In this article we are interested in the density of small linear structures (e.g. arithmetic progressions) in subsets $A$ of the group $\mathbb{F}_p^n$. It is possible to express these densities as certain analytic averages involving $1_A$, the indicator function of $A$. In the higher-order Fourier analytic approach, the function $1_A$ ... more >>>

Shachar Lovett

Recently there has been much interest in polynomial threshold functions in the context of learning theory, structural results and pseudorandomness. A crucial ingredient in these works is the understanding of the distribution of low-degree multivariate polynomials evaluated over normally distributed inputs. In particular, the two important properties are exponential tail ... more >>>

Raghu Meka

The Johnson-Lindenstrauss lemma is a fundamental result in probability with several applications in the design and analysis of algorithms in high dimensional geometry. Most known constructions of linear embeddings that satisfy the Johnson-Lindenstrauss property involve randomness. We address the question of explicitly constructing such embedding families and provide a construction ... more >>>

Manjish Pal

The {\sc $c$-Balanced Separator} problem is a graph-partitioning problem in which given a graph $G$, one aims to find a cut of minimum size such that both the sides of the cut have at least $cn$ vertices. In this paper, we present new directions of progress in the {\sc $c$-Balanced ... more >>>

Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu

We prove the following strong hardness result for learning: Given a distribution of labeled examples from the hypercube such that there exists a monomial consistent with $(1-\epsilon)$ of the examples, it is $\mathrm{NP}$-hard to find a halfspace that is correct on $(1/2+\epsilon)$ of the examples, for arbitrary constants $\epsilon ... more >>>

Bill Fefferman, Ronen Shaltiel, Chris Umans, Emanuele Viola

The {\em hybrid argument}

allows one to relate

the {\em distinguishability} of a distribution (from

uniform) to the {\em

predictability} of individual bits given a prefix. The

argument incurs a loss of a factor $k$ equal to the

bit-length of the

distributions: $\epsilon$-distinguishability implies only

$\epsilon/k$-predictability. ...
more >>>

Gus Gutoski

This paper studies a generalization of multi-prover interactive proofs in which a verifier interacts with two competing teams of provers: one team attempts to convince the verifier to accept while the other attempts to convince the verifier to reject. Each team consists of two provers who jointly implement a no-signaling ... more >>>

Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich

We present a polynomial-time deterministic algorithm for testing whether constant-read multilinear arithmetic formulae are identically zero. In such a formula each variable occurs only a constant number of times and each subformula computes a multilinear polynomial. Our algorithm runs in time $s^{O(1)}\cdot n^{k^{O(k)}}$, where $s$ denotes the size of the ... more >>>

Neeraj Kayal, Chandan Saha

The sum of square roots problem over integers is the task of deciding the sign of a nonzero sum, $S = \Sigma_{i=1}^{n}{\delta_i}$ . \sqrt{$a_i$}, where $\delta_i \in$ { +1, -1} and $a_i$'s are positive integers that are upper bounded by $N$ (say). A fundamental open question in numerical analysis and ... more >>>

Xin Li

We study the problem of constructing extractors for independent weak random sources. The probabilistic method shows that there exists an extractor for two independent weak random sources on $n$ bits with only logarithmic min-entropy. However, previously the best known explicit two source extractor only achieves min-entropy $0.499n$ \cite{Bourgain05}, and the ... more >>>

Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland

We introduce a new quantum adversary method to prove lower bounds on the query complexity of the quantum state generation problem. This problem encompasses both, the computation of partial or total functions and the preparation of target quantum states. There has been hope for quite some time that quantum ... more >>>

Frederic Magniez, Ashwin Nayak, Miklos Santha, David Xiao

We consider the randomized decision tree complexity of the recursive 3-majority function. For evaluating a height $h$ formulae, we prove a lower bound for the $\delta$-two-sided-error randomized decision tree complexity of $(1-2\delta)(5/2)^h$, improving the lower bound of $(1-2\delta)(7/3)^h$ given by Jayram et al. (STOC '03). We also state a conjecture ... more >>>

Edward Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal

The existence of an optimal propositional proof system is a major open question in proof complexity; many people conjecture that such systems do not exist. Krajicek and Pudlak (1989) show that this question is equivalent to the existence of an algorithm that is optimal on all propositional tautologies. Monroe (2009) ... more >>>

Thanh Minh Hoang

In this paper we investigate the question whether a perfect matching can be isolated by a weighting scheme

using Chinese Remainder Theorem (short: CRT). We give a systematical analysis to a method based on CRT

suggested by Agrawal in a CCC'03-paper

for testing perfect matchings. We show that ...
more >>>

Ho-Lin Chen, David Doty, Shinnosuke Seki, David Soloveichik

We settle a number of questions in variants of Winfree's abstract Tile Assembly Model (aTAM), a model of molecular algorithmic self-assembly. In the "hierarchical" aTAM, two assemblies, both consisting of multiple tiles, are allowed to aggregate together, whereas in the "seeded" aTAM, tiles attach one at a time to a ... more >>>

Bin Fu

A long standing open problem in the computational complexity theory

is to separate NE from BPP, which is a subclass of $NP_T (NP\cap P/poly)$.

In this paper, we show that $NE\not\subseteq NP_T (NP \cap$ Nonexponentially-Dense-Class),

where Nonexponentially-Dense-Class is the class of languages A without exponential density

(for ...
more >>>

Albert Atserias, Elitza Maneva

We associate a CNF-formula to every instance of the mean-payoff game problem in such a way that if the value of the game is non-negative the formula is satisfiable, and if the value of the game is negative the formula has a polynomial-size refutation in $\Sigma_2$-Frege (i.e.~DNF-resolution). This reduces mean-payoff ... more >>>

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander Razborov

A general framework for parameterized proof complexity was introduced by Dantchev, Martin, and Szeider (FOCS'07). In that framework the parameterized version of any proof system is not fpt-bounded for some technical reasons, but we remark that this question becomes much more interesting if we restrict ourselves to those parameterized contradictions ... more >>>

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

Locally testable codes, i.e., codes where membership in the code is testable with a constant number of queries, have played a central role in complexity theory. It is well known that a code must be a "low-density parity check" (LDPC) code for it to be locally testable, but few LDPC ... more >>>

Eli Ben-Sasson, Michael Viderman

The main open problem in the area of locally testable codes (LTCs) is whether there exists an asymptotically good family of LTCs and to resolve this question it suffices to consider the case of query complexity $3$. We argue that to refute the existence of such an asymptotically good family ... more >>>

Samir Datta, Raghav Kulkarni, Raghunath Tewari

We prove that Perfect Matching in bipartite planar graphs is in UL, improving upon

the previous bound of SPL (see [DKR10]) on its space complexity. We also exhibit space

complexity bounds for some related problems. Summarizing, we show that, constructing:

1. a Perfect Matching in bipartite planar graphs is in ...
more >>>

Bin Fu

We investigate the complexity of integration and

derivative for multivariate polynomials in the standard computation

model. The integration is in the unit cube $[0,1]^d$ for a

multivariate polynomial, which has format

$f(x_1,\cdots,

x_d)=p_1(x_1,\cdots, x_d)p_2(x_1,\cdots, x_d)\cdots p_k(x_1,\cdots,

x_d)$,

where each $p_i(x_1,\cdots, x_d)=\sum_{j=1}^d q_j(x_j)$ with

all single variable polynomials $q_j(x_j)$ ...
more >>>