All reports in year 2008:

__
TR08-001
| 5th January 2008
__

Ran Raz#### Elusive Functions and Lower Bounds for Arithmetic Circuits

__
TR08-002
| 19th December 2007
__

Arkadev Chattopadhyay, Anil Ada#### Multiparty Communication Complexity of Disjointness

Revisions: 3

__
TR08-003
| 25th December 2007
__

Troy Lee, Adi Shraibman#### Disjointness is hard in the multi-party number-on-the-forehead model

__
TR08-004
| 2nd January 2008
__

Zeev Dvir, Amir Shpilka#### Noisy Interpolating Sets for Low Degree Polynomials

__
TR08-005
| 15th January 2008
__

Scott Aaronson, Avi Wigderson#### Algebrization: A New Barrier in Complexity Theory

__
TR08-006
| 18th January 2008
__

Ran Raz, Amir Yehudayoff#### Lower Bounds and Separations for Constant Depth Multilinear Circuits

__
TR08-007
| 6th February 2008
__

Dan Gutfreund, Salil Vadhan#### Limitations of Hardness vs. Randomness under Uniform Reductions

__
TR08-008
| 8th February 2008
__

Venkatesan Guruswami, Prasad Raghavendra#### Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness

Revisions: 1

__
TR08-009
| 7th December 2007
__

Per Austrin, Elchanan Mossel#### Approximation Resistant Predicates From Pairwise Independence

__
TR08-010
| 17th January 2008
__

Itai Benjamini, Oded Schramm, Asaf Shapira#### Every Minor-Closed Property of Sparse Graphs is Testable

__
TR08-011
| 21st November 2007
__

Kazuo Iwama, Suguru Tamaki#### The Complexity of the Hajos Calculus for Planar Graphs

__
TR08-012
| 20th November 2007
__

Arnab Bhattacharyya#### A Note on the Distance to Monotonicity of Boolean Functions

__
TR08-013
| 16th January 2008
__

Anup Rao#### Parallel Repetition in Projection Games and a Concentration Bound

__
TR08-014
| 26th February 2008
__

Matei David#### Separating NOF communication complexity classes RP and NP

__
TR08-015
| 23rd January 2008
__

Anup Rao#### Extractors for Low-Weight Affine Sources

__
TR08-016
| 26th February 2008
__

Alexander Razborov, Alexander A. Sherstov#### The Sign-Rank of AC^0

__
TR08-017
| 16th December 2007
__

Thomas Watson, Dieter van Melkebeek#### A Quantum Time-Space Lower Bound for the Counting Hierarchy

__
TR08-018
| 28th February 2008
__

Ran Raz#### A Counterexample to Strong Parallel Repetition

__
TR08-019
| 6th March 2008
__

Stasys Jukna#### Entropy of operators or why matrix multiplication is hard for small depth circuits

Revisions: 1

__
TR08-020
| 7th March 2008
__

Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan#### Decodability of Group Homomorphisms beyond the Johnson Bound

__
TR08-021
| 3rd March 2008
__

Shankar Kalyanaraman, Chris Umans#### The Complexity of Rationalizing Matchings

__
TR08-022
| 9th January 2008
__

Harry Buhrman, John Hitchcock#### NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP/poly

__
TR08-023
| 10th January 2008
__

Anindya De, Piyush Kurur, Chandan Saha, Ramprasad Saptharishi#### Fast Integer Multiplication using Modular Arithmetic

__
TR08-024
| 26th February 2008
__

Paul Beame, Trinh Huynh#### On the Value of Multiple Read/Write Streams for Approximating Frequency Moments

Revisions: 2

__
TR08-025
| 3rd January 2008
__

Vikraman Arvind, Partha Mukhopadhyay, Srikanth Srinivasan#### New results on Noncommutative and Commutative Polynomial Identity Testing

Revisions: 2

__
TR08-026
| 28th February 2008
__

Jakob Nordström, Johan Hastad#### Towards an Optimal Separation of Space and Length in Resolution

__
TR08-027
| 4th December 2007
__

Till Tantau#### Generalizations of the Hartmanis-Immerman-Sewelson Theorem and Applications to Infinite Subsets of P-Selective Sets

__
TR08-028
| 5th December 2007
__

Michael Bauland, Martin Mundhenk, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer#### The Tractability of Model-Checking for LTL: The Good, the Bad, and the Ugly Fragments

__
TR08-029
| 7th January 2008
__

Christian Glaßer, Christian Reitwießner, Victor Selivanov#### The Shrinking Property for NP and coNP

__
TR08-030
| 16th November 2007
__

Bruno Durand, Alexander Shen, Andrei Romashchenko#### Fixed Point and Aperiodic Tilings

__
TR08-031
| 14th January 2008
__

James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers#### Computability and Complexity in Self-Assembly

__
TR08-032
| 18th March 2008
__

Dmitriy Cherukhin#### Lower Bounds for Boolean Circuits with Finite Depth and Arbitrary Gates

__
TR08-033
| 21st March 2008
__

Elena Grigorescu, Tali Kaufman, Madhu Sudan#### 2-Transitivity is Insufficient for Local Testability

__
TR08-034
| 19th January 2008
__

Dan Gutfreund, Guy Rothblum#### The Complexity of Local List Decoding

Revisions: 1

__
TR08-035
| 18th February 2008
__

James I. Lathrop, Jack H. Lutz, Scott M. Summers#### Strict Self-Assembly of Discrete Sierpinski Triangles

__
TR08-036
| 14th March 2008
__

Venkatesan Guruswami, Atri Rudra#### Soft decoding, dual BCH codes, and better list-decodable eps-biased codes

__
TR08-037
| 29th February 2008
__

Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo#### Curves That Must Be Retraced

Revisions: 1

__
TR08-038
| 4th April 2008
__

Eric Allender, Michal Koucky#### Amplifying Lower Bounds by Means of Self-Reducibility

Revisions: 2

__
TR08-039
| 7th April 2008
__

Oded Goldreich, Dana Ron#### Algorithmic Aspects of Property Testing in the Dense Graphs Model

__
TR08-040
| 3rd April 2008
__

Sourav Chakraborty, Laszlo Babai#### Property Testing of Equivalence under a Permutation Group Action

__
TR08-041
| 10th April 2008
__

Oded Goldreich, Dana Ron#### On Proximity Oblivious Testing

__
TR08-042
| 6th April 2008
__

Zeev Dvir#### Deterministic Extractors for Algebraic Sources

__
TR08-043
| 12th April 2008
__

Gábor Ivanyos, Marek Karpinski, Nitin Saxena#### Schemes for Deterministic Polynomial Factoring

__
TR08-044
| 2nd April 2008
__

Miki Hermann, Reinhard Pichler#### Complexity of Counting the Optimal Solutions

__
TR08-045
| 23rd April 2008
__

Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil Vadhan#### Dense Subsets of Pseudorandom Sets

__
TR08-046
| 14th April 2008
__

Nikhil R. Devanur, Lance Fortnow#### A Computational Theory of Awareness and Decision Making

__
TR08-047
| 17th March 2008
__

Vijay V. Vazirani, Wang Lei#### Continuity Properties of Equilibria in Some Fisher and Arrow-Debreu Market Models

__
TR08-048
| 8th April 2008
__

Meena Mahajan, B. V. Raghavendra Rao#### Arithmetic circuits, syntactic multilinearity, and the limitations of skew formulae

__
TR08-049
| 10th April 2008
__

Vikraman Arvind, Partha Mukhopadhyay#### Derandomizing the Isolation Lemma and Lower Bounds for Noncommutative Circuit Size

Revisions: 3

__
TR08-050
| 12th March 2008
__

Manoj Prabhakaran, Mike Rosulek#### Cryptographic Complexity of Multi-party Computation Problems: Classifications and Separations

__
TR08-051
| 4th April 2008
__

Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter Shor#### The Power of Unentanglement

__
TR08-052
| 29th April 2008
__

Vikraman Arvind, T.C. Vijayaraghavan#### The Orbit problem is in the GapL Hierarchy

Revisions: 1

__
TR08-053
| 27th March 2008
__

Stephen A. Fenner, William Gasarch, Brian Postow#### The complexity of learning SUBSEQ(A)

__
TR08-054
| 13th May 2008
__

Venkatesan Guruswami, Atri Rudra#### Concatenated codes can achieve list-decoding capacity

__
TR08-055
| 19th May 2008
__

Ryan O'Donnell#### Some Topics in Analysis of Boolean Functions

__
TR08-056
| 22nd April 2008
__

Beate Bollig#### On the OBDD complexity of the most significant bit of integer multiplication

__
TR08-057
| 14th May 2008
__

Alexander A. Sherstov#### Communication Lower Bounds Using Dual Polynomials

__
TR08-058
| 1st June 2008
__

Zeev Dvir, Avi Wigderson#### Kakeya sets, new mergers and old extractors

__
TR08-059
| 20th May 2008
__

Farid Ablayev, Alexander Vasiliev#### On the Computation of Boolean Functions by Quantum Branching Programs via Fingerprinting

Revisions: 1

__
TR08-060
| 10th April 2008
__

James R. Lee, Prasad Raghavendra#### Coarse Differentiation and Multi-flows in Planar Graphs

__
TR08-061
| 11th June 2008
__

Paul Beame, Trinh Huynh#### Multiparty Communication Complexity of AC^0

Revisions: 1

__
TR08-062
| 11th June 2008
__

Manindra Agrawal, V Vinay#### Arithmetic Circuits: A Chasm at Depth Four

__
TR08-063
| 21st April 2008
__

Müller Moritz#### Valiant-Vazirani Lemmata for Various Logics

__
TR08-064
| 11th July 2008
__

Or Meir#### On the Efficiency of Non-Uniform PCPP Verifiers

__
TR08-065
| 11th July 2008
__

Noga Alon, Rina Panigrahy, Sergey Yekhanin#### Deterministic Approximation Algorithms for the Nearest Codeword Problem

__
TR08-066
| 16th July 2008
__

Noga Alon, Shai Gutner#### Kernels for the Dominating Set Problem on Graphs with an Excluded Minor

Revisions: 1

__
TR08-067
| 4th June 2008
__

Scott Aaronson#### On Perfect Completeness for QMA

__
TR08-068
| 3rd July 2008
__

Lior Malka#### Instance-Dependent Commitment Schemes and the Round Complexity of Perfect Zero-Knowledge Proofs

__
TR08-069
| 5th August 2008
__

Klim Efremenko#### 3-Query Locally Decodable Codes of Subexponential Length

__
TR08-071
| 6th August 2008
__

Dana Moshkovitz, Ran Raz#### Two Query PCP with Sub-Constant Error

__
TR08-072
| 11th August 2008
__

Shachar Lovett, Tali Kaufman#### Worst case to Average case reductions for polynomials

__
TR08-073
| 4th August 2008
__

Dmitry Itsykson#### Structural complexity of AvgBPP

__
TR08-074
| 19th July 2008
__

Neeraj Kayal, Timur Nezhmetdinov#### Factoring groups efficiently

__
TR08-075
| 7th July 2008
__

Olaf Beyersdorff, Johannes Köbler, Sebastian Müller#### Nondeterministic Instance Complexity and Proof Systems with Advice

__
TR08-076
| 17th June 2008
__

Ryan Williams#### Non-Linear Time Lower Bound for (Succinct) Quantified Boolean Formulas

__
TR08-077
| 23rd May 2008
__

Felix Brandt, Felix Fischer, Markus Holzer#### On Iterated Dominance, Matrix Elimination, and Matched Paths

__
TR08-078
| 15th April 2008
__

Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steve Homer#### Universal Quantum Circuits

__
TR08-079
| 31st August 2008
__

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson#### Uniform Direct-Product Theorems: Simplified, Optimized, and Derandomized

__
TR08-080
| 3rd July 2008
__

Ido Ben-Eliezer, Rani Hod, Shachar Lovett#### Random low degree polynomials are hard to approximate

Revisions: 1

__
TR08-081
| 11th September 2008
__

Alexander Razborov#### A simple proof of Bazzi's theorem

__
TR08-082
| 11th September 2008
__

Paul Beame, Trinh Huynh#### Multiparty Communication Complexity and Threshold Circuit Size of AC^0

Revisions: 2

__
TR08-083
| 10th June 2008
__

Yijia Chen, Jörg Flum#### A logic for PTIME and a parameterized halting problem

__
TR08-084
| 16th June 2008
__

Sanjeeb Dash#### On the complexity of cutting plane proofs using split cuts

__
TR08-085
| 19th June 2008
__

Farid Ablayev, Airat Khasianov, Alexander Vasiliev#### On Complexity of Quantum Branching Programs Computing Equality-like Boolean Functions

Revisions: 1

__
TR08-086
| 9th July 2008
__

Vikraman Arvind, Partha Mukhopadhyay#### Quantum Query Complexity of Multilinear Identity Testing

__
TR08-087
| 31st July 2008
__

Tomas Feder, Carlos Subi#### Nearly Tight Bounds on the Number of Hamiltonian Circuits of the Hypercube and Generalizations (revised)

__
TR08-088
| 13th September 2008
__

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie#### Testing Linear-Invariant Non-Linear Properties

Revisions: 1

__
TR08-089
| 28th September 2008
__

Noam Berger, Kapur Nevin, Schulman Leonard, Vazirani Vijay#### SOLVENCY GAMES

__
TR08-090
| 6th August 2008
__

Ulrich Schöpp, Martin Hofmann#### Pointer Programs and Undirected Reachability

Revisions: 1

__
TR08-091
| 10th September 2008
__

Vitaly Feldman#### On The Power of Membership Queries in Agnostic Learning

Revisions: 1

__
TR08-092
| 26th August 2008
__

Scott Aaronson, John Watrous#### Closed Timelike Curves Make Quantum and Classical Computing Equivalent

__
TR08-093
| 1st October 2008
__

Cristopher Moore, Alexander Russell#### A simple constant-probability RP reduction from NP to Parity P

__
TR08-094
| 10th October 2008
__

Piotr Berman, Marek Karpinski, Alexander Zelikovsky#### 1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two

__
TR08-095
| 31st October 2008
__

Brendan Juba, Madhu Sudan#### Universal Semantic Communication II: A Theory of Goal-Oriented Communication

Revisions: 1

__
TR08-096
| 8th September 2008
__

Andrew Drucker#### Multitask Efficiencies in the Decision Tree Model

__
TR08-097
| 14th November 2008
__

Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg#### Hierarchy Theorems for Property Testing

Revisions: 1

__
TR08-098
| 12th November 2008
__

Victor Chen#### A Hypergraph Dictatorship Test with Perfect Completeness

Revisions: 1

__
TR08-099
| 19th November 2008
__

Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena#### Trading GRH for algebra: algorithms for factoring polynomials and related structures

__
TR08-100
| 14th November 2008
__

Chris Peikert#### Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem

__
TR08-101
| 20th November 2008
__

Marek Karpinski, Warren Schudy#### Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems

__
TR08-102
| 9th November 2008
__

Adi Akavia#### Finding Significant Fourier Transform Coefficients Deterministically and Locally

__
TR08-103
| 22nd November 2008
__

Luca Trevisan, Madhur Tulsiani, Salil Vadhan#### Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution

__
TR08-104
| 23rd November 2008
__

Madhur Tulsiani#### CSP Gaps and Reductions in the Lasserre Hierarchy

__
TR08-105
| 26th November 2008
__

Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra, Prasad Raghavendra#### List Decoding Tensor Products and Interleaved Codes

__
TR08-106
| 12th November 2008
__

Jack H. Lutz#### A Divergence Formula for Randomness and Dimension

__
TR08-107
| 12th November 2008
__

Zenon Sadowski#### Optimal Proof Systems and Complete Languages

__
TR08-108
| 19th November 2008
__

Nitin Saxena, C. Seshadhri#### An Almost Optimal Rank Bound for Depth-3 Identities

__
TR08-109
| 10th November 2008
__

Marc Kaplan, Sophie Laplante#### Kolmogorov complexity and combinatorial methods in communication complexity

__
TR08-110
| 19th November 2008
__

Chris Calabro#### A Lower Bound on the Size of Series-Parallel Graphs Dense in Long Paths

__
TR08-111
| 14th November 2008
__

Shachar Lovett, Tali Kaufman#### The List-Decoding Size of Reed-Muller Codes

Revisions: 2

Ran Raz

A basic fact in linear algebra is that the image of the curve

$f(x)=(x^1,x^2,x^3,...,x^m)$, say over $C$, is not contained in any

$m-1$ dimensional affine subspace of $C^m$. In other words, the image

of $f$ is not contained in the image of any polynomial-mapping

$G:C^{m-1} ---> C^m$ ...
more >>>

Arkadev Chattopadhyay, Anil Ada

We extend the 'Generalized Discrepancy' technique suggested by Sherstov to the `Number on the Forehead' model of multiparty communication. This allows us to prove strong lower bounds of n^{\Omega(1)} on the communication needed by k players to compute the Disjointness function, provided $k$ is a constant. In general, our method ... more >>>

Troy Lee, Adi Shraibman

We show that disjointness requires randomized communication

Omega(\frac{n^{1/2k}}{(k-1)2^{k-1}2^{2^{k-1}}})

in the general k-party number-on-the-forehead model of complexity.

The previous best lower bound was Omega(\frac{log n}{k-1}). By

results of Beame, Pitassi, and Segerlind, this implies

2^{n^{Omega(1)}} lower bounds on the size of tree-like Lovasz-Schrijver

proof systems needed to refute certain unsatisfiable ...
more >>>

Zeev Dvir, Amir Shpilka

A Noisy Interpolating Set (NIS) for degree $d$ polynomials is a

set $S \subseteq \F^n$, where $\F$ is a finite field, such that

any degree $d$ polynomial $q \in \F[x_1,\ldots,x_n]$ can be

efficiently interpolated from its values on $S$, even if an

adversary corrupts a constant fraction of the values. ...
more >>>

Scott Aaronson, Avi Wigderson

Any proof of P!=NP will have to overcome two barriers: relativization

and natural proofs. Yet over the last decade, we have seen circuit

lower bounds (for example, that PP does not have linear-size circuits)

that overcome both barriers simultaneously. So the question arises of

whether there ...
more >>>

Ran Raz, Amir Yehudayoff

We prove an exponential lower bound for the size of constant depth multilinear arithmetic circuits computing either the determinant or the permanent (a circuit is called multilinear, if the polynomial computed by each of its gates is multilinear). We also prove a super-polynomial separation between the size of product-depth $d$ ... more >>>

Dan Gutfreund, Salil Vadhan

We consider (uniform) reductions from computing a function f to the task of distinguishing the output of some pseudorandom generator G from uniform. Impagliazzo and Wigderson (FOCS `98, JCSS `01) and Trevisan and Vadhan (CCC `02, CC `07) exhibited such reductions for every function f in PSPACE. Moreover, their reductions ... more >>>

Venkatesan Guruswami, Prasad Raghavendra

We study the approximability of the \maxcsp problem over non-boolean domains, more specifically over $\{0,1,\ldots,q-1\}$ for some integer $q$. We obtain a approximation algorithm that achieves a ratio of $C(q) \cdot k/q^k$ for some constant $C(q)$ depending only on $q$. Further, we extend the techniques of Samorodnitsky and Trevisan to ... more >>>

Per Austrin, Elchanan Mossel

We study the approximability of predicates on $k$ variables from a

domain $[q]$, and give a new sufficient condition for such predicates

to be approximation resistant under the Unique Games Conjecture.

Specifically, we show that a predicate $P$ is approximation resistant

if there exists a balanced pairwise independent distribution over

more >>>

Itai Benjamini, Oded Schramm, Asaf Shapira

Testing a property P of graphs in the bounded degree model deals with the following problem: given a graph G of bounded degree d we should distinguish (with probability 0.9, say) between the case that G satisfies P and the case that one should add/remove at least \epsilon d n ... more >>>

Kazuo Iwama, Suguru Tamaki

The planar Hajos calculus is the Hajos calculus with the restriction that all the graphs that appear in the construction (including a final graph) must be planar. We prove that the planar Hajos calculus is polynomially bounded iff the HajLos calculus is polynomially bounded.

more >>>Arnab Bhattacharyya

Given a boolean function, let epsilon_M(f) denote the smallest distance between f and a monotone function on {0,1}^n. Let delta_M(f) denote the fraction of hypercube edges where f violates monotonicity. We give an alternative proof of the tight bound: delta_M(f) >= 2/n eps_M(f) for any boolean function f. This was ... more >>>

Anup Rao

In a two player game, a referee asks two cooperating players (who are

not allowed to communicate) questions sampled from some distribution

and decides whether they win or not based on some predicate of the

questions and their answers. The parallel repetition of the game is

the game in which ...
more >>>

Matei David

We provide a non-explicit separation of the number-on-forehead communication complexity classes RP and NP when the number of players is up to \delta log(n) for any \delta<1. Recent lower bounds on Set-Disjointness [LS08,CA08] provide an explicit separation between these classes when the number of players is only up to o(loglog(n)).

... more >>>Anup Rao

We give polynomial time computable extractors for low-weight affine sources. A distribution is affine if it samples a random point from some unknown low dimensional subspace of F^n_2 . A distribution is low weight affine if the corresponding linear space has a basis of low-weight vectors. Low-weight ane sources are ... more >>>

Alexander Razborov, Alexander A. Sherstov

The sign-rank of a matrix A=[A_{ij}] with +/-1 entries

is the least rank of a real matrix B=[B_{ij}] with A_{ij}B_{ij}>0

for all i,j. We obtain the first exponential lower bound on the

sign-rank of a function in AC^0. Namely, let

f(x,y)=\bigwedge_{i=1}^m\bigvee_{j=1}^{m^2} (x_{ij}\wedge y_{ij}).

We show that the matrix [f(x,y)]_{x,y} has ...
more >>>

Thomas Watson, Dieter van Melkebeek

We obtain the first nontrivial time-space lower bound for quantum algorithms solving problems related to satisfiability. Our bound applies to MajSAT and MajMajSAT, which are complete problems for the first and second levels of the counting hierarchy, respectively. We prove that for every real $d$ and every positive real $\epsilon$ ... more >>>

Ran Raz

The parallel repetition theorem states that for any two-prover game,

with value $1- \epsilon$ (for, say, $\epsilon \leq 1/2$), the value of

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

$(1- \epsilon^c)^{\Omega(n/s)}$, where $s$ is the answers' length

(of the original game) and $c$ is a universal ...
more >>>

Stasys Jukna

In this note we consider unbounded fanin depth-2 circuits with arbitrary boolean functions as gates.

We define the entropy of an operator f:{0,1}^n --> {0,1}^m is as the logarithm of the maximum number of vectors distinguishable by at least one special subfunction of f. Then we prove that every ... more >>>

Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan

Given a pair of finite groups $G$ and $H$, the set of homomorphisms from $G$ to $H$ form an error-correcting code where codewords differ in at least $1/2$ the coordinates. We show that for every pair of {\em abelian} groups $G$ and $H$, the resulting code is (locally) list-decodable from ... more >>>

Shankar Kalyanaraman, Chris Umans

Given a set of observed economic choices, can one infer

preferences and/or utility functions for the players that are

consistent with the data? Questions of this type are called {\em

rationalization} or {\em revealed preference} problems in the

economic literature, and are the subject of a rich body of work.

Harry Buhrman, John Hitchcock

We show that hard sets S for NP must have exponential density, i.e. |S<sub>=n</sub>| ≥ 2<sup>n<sup>ε</sup></sup> for some ε > 0 and infinitely many n, unless coNP ⊆ NP\poly and the polynomial-time hierarchy collapses. This result holds for Turing reductions that make n<sup>1-ε</sup> queries.

In addition we study the instance ... more >>>

Anindya De, Piyush Kurur, Chandan Saha, Ramprasad Saptharishi

We give an $O(N\cdot \log N\cdot 2^{O(\log^*N)})$ algorithm for

multiplying two $N$-bit integers that improves the $O(N\cdot \log

N\cdot \log\log N)$ algorithm by

Sch\"{o}nhage-Strassen. Both these algorithms use modular

arithmetic. Recently, F\"{u}rer gave an $O(N\cdot \log

N\cdot 2^{O(\log^*N)})$ algorithm which however uses arithmetic over

complex numbers as opposed to ...
more >>>

Paul Beame, Trinh Huynh

Recently, an extension of the standard data stream model has been introduced in which an algorithm can create and manipulate multiple read/write streams in addition to its input data stream. Like the data stream model, the most important parameter for this model is the amount of internal memory used by ... more >>>

Vikraman Arvind, Partha Mukhopadhyay, Srikanth Srinivasan

Using ideas from automata theory we design a new efficient

(deterministic) identity test for the \emph{noncommutative}

polynomial identity testing problem (first introduced and studied by

Raz-Shpilka in 2005 and Bogdanov-Wee in 2005). More precisely,

given as input a noncommutative

circuit $C(x_1,\cdots,x_n)$ computing a ...
more >>>

Jakob Nordström, Johan Hastad

Most state-of-the-art satisfiability algorithms today are variants of

the DPLL procedure augmented with clause learning. The main bottleneck

for such algorithms, other than the obvious one of time, is the amount

of memory used. In the field of proof complexity, the resources of

time and memory correspond to the length ...
more >>>

Till Tantau

The Hartmanis--Immerman--Sewelson theorem is the classical link between the exponential and the polynomial time realm. It states that NE = E if, and only if, every sparse set in NP lies in P. We establish similar links for classes other than sparse sets:

1. E = UE if, and only ... more >>>

Michael Bauland, Martin Mundhenk, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer

In a seminal paper from 1985, Sistla and Clarke showed

that the model-checking problem for Linear Temporal Logic (LTL) is either NP-complete

or PSPACE-complete, depending on the set of temporal operators used.

If, in contrast, the set of propositional operators is restricted, the complexity may decrease.

...
more >>>

Christian Glaßer, Christian Reitwießner, Victor Selivanov

We study the shrinking and separation properties (two notions well-known in descriptive set theory) for NP and coNP and show that under reasonable complexity-theoretic assumptions, both properties do not hold for NP and the shrinking property does not hold for coNP. In particular we obtain the following results.

1. NP ... more >>>

Bruno Durand, Alexander Shen, Andrei Romashchenko

An aperiodic tile set was first constructed by R.Berger while

proving the undecidability of the domino problem. It turned out

that aperiodic tile sets appear in many topics ranging from

logic (the Entscheidungsproblem) to physics (quasicrystals)

We present a new construction of an aperiodic tile set. The

flexibility of this ...
more >>>

James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers

This paper explores the impact of geometry on computability =

and complexity in

Winfree's model of nanoscale self-assembly. We work in the =

two-dimensional

tile assembly model, i.e., in the discrete Euclidean plane Z x Z. Our =

first

main theorem says that there is a roughly quadratic function f ...
more >>>

Dmitriy Cherukhin

We consider bounded depth circuits over an arbitrary field $K$. If the field $K$ is finite, then we allow arbitrary gates $K^n\to K$. For instance, in the case of field $GF(2)$ we allow any Boolean gates. If the field $K$ is infinite, then we allow only polinomials.

For every fixed ... more >>>

Elena Grigorescu, Tali Kaufman, Madhu Sudan

A basic goal in Property Testing is to identify a

minimal set of features that make a property testable.

For the case when the property to be tested is membership

in a binary linear error-correcting code, Alon et al.~\cite{AKKLR}

had conjectured that the presence of a {\em single} low weight

more >>>

Dan Gutfreund, Guy Rothblum

We study the complexity of locally list-decoding binary error correcting codes with good parameters (that are polynomially related to information theoretic bounds). We show that computing majority over $\Theta(1/\eps)$ bits is essentially equivalent to locally list-decoding binary codes from relative distance $1/2-\eps$ with list size $\poly(1/\eps)$. That is, a local-decoder ... more >>>

James I. Lathrop, Jack H. Lutz, Scott M. Summers

Winfree (1998) showed that discrete Sierpinski triangles can self-assemble in the Tile Assembly Model. A striking molecular realization of this self-assembly, using DNA tiles a few nanometers long and verifying the results by atomic-force microscopy, was achieved by Rothemund, Papadakis, and Winfree (2004). Precisely speaking, the above self-assemblies tile completely ... more >>>

Venkatesan Guruswami, Atri Rudra

We construct binary linear codes that are efficiently list-decodable

up to a fraction $(1/2-\eps)$ of errors. The codes encode $k$ bits

into $n = {\rm poly}(k/\eps)$ bits and are constructible and

list-decodable in time polynomial in $k$ and $1/\eps$ (in

particular, in our results $\eps$ need ...
more >>>

Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo

We exhibit a polynomial time computable plane curve GAMMA that has finite length, does not intersect itself, and is smooth except at one endpoint, but has the following property. For every computable parametrization f of GAMMA and every positive integer n, there is some positive-length subcurve of GAMMA that f ... more >>>

Eric Allender, Michal Koucky

We observe that many important computational problems in NC^1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial size TC^0 circuits if and only if it has TC^0 circuits of size n^{1+\epsilon} for every \epsilon > 0 (counting the ... more >>>

Oded Goldreich, Dana Ron

In this paper we consider two refined questions regarding

the query complexity of testing graph properties

in the adjacency matrix model.

The first question refers to the relation between adaptive

and non-adaptive testers, whereas the second question refers to

testability within complexity that

is inversely proportional to ...
more >>>

Sourav Chakraborty, Laszlo Babai

For a permutation group $G$ acting on the set $\Omega$

we say that two strings $x,y\,:\,\Omega\to\boole$

are {\em $G$-isomorphic} if they are equivalent under

the action of $G$, \ie, if for some $\pi\in G$ we have

$x(i^{\pi})=y(i)$ for all $i\in\Omega$.

Cyclic Shift, Graph Isomorphism ...
more >>>

Oded Goldreich, Dana Ron

We initiate a systematic study of a special type of property testers.

These testers consist of repeating a basic test

for a number of times that depends on the proximity parameters,

whereas the basic test is oblivious of the proximity parameter.

We refer to such basic ...
more >>>

Zeev Dvir

An algebraic source is a random variable distributed

uniformly over the set of common zeros of one or more multivariate

polynomials defined over a finite field $F$. Our main result is

the construction of an explicit deterministic extractor for

algebraic sources over exponentially large prime fields. More

precisely, we give ...
more >>>

Gábor Ivanyos, Marek Karpinski, Nitin Saxena

In this work we relate the deterministic

complexity of factoring polynomials (over

finite

fields) to certain combinatorial objects we

call

m-schemes. We extend the known conditional

deterministic subexponential time polynomial

factoring algorithm for finite fields to get an

underlying m-scheme. We demonstrate ...
more >>>

Miki Hermann, Reinhard Pichler

Following the approach of Hemaspaandra and Vollmer, we can define

counting complexity classes #.C for any complexity class C of decision

problems. In particular, the classes #.Pi_{k}P with k >= 1

corresponding to all levels of the polynomial hierarchy have thus been

studied. However, for a large variety of counting ...
more >>>

Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil Vadhan

A theorem of Green, Tao, and Ziegler can be stated (roughly)

as follows: if R is a pseudorandom set, and D is a dense subset of R,

then D may

be modeled by a set M that is dense in the entire domain such that D and

more >>>

Nikhil R. Devanur, Lance Fortnow

We exhibit a new computational-based definition of awareness,

informally that our level of unawareness of an object is the amount

of time needed to generate that object within a certain environment.

We give several examples to show this notion matches our intuition

in scenarios where one organizes, accesses and transfers

more >>>

Vijay V. Vazirani, Wang Lei

Following up on the work of Megiddo and Vazirani \cite{MV.2007}, who

determined continuity properties of equilibrium prices and

allocations for perhaps the simplest market model, Fisher's linear

case, we do the same for:

\begin{itemize}

\item

Fisher's model with piecewise-linear, concave utilities

\item

Fisher's model with spending constraint utilities

\item

Arrow-Debreu's ...
more >>>

Meena Mahajan, B. V. Raghavendra Rao

Functions in arithmetic NC1 are known to have equivalent constant

width polynomial degree circuits, but the converse containment is

unknown. In a partial answer to this question, we show that syntactic

multilinear circuits of constant width and polynomial degree can be

depth-reduced, though the resulting circuits need not be ...
more >>>

Vikraman Arvind, Partha Mukhopadhyay

We give a randomized polynomial-time identity test for

noncommutative circuits of polynomial degree based on the isolation

lemma. Using this result, we show that derandomizing the isolation

lemma implies noncommutative circuit size lower bounds. More

precisely, we consider two restricted versions of the isolation

lemma and show that derandomizing each ...
more >>>

Manoj Prabhakaran, Mike Rosulek

We develop new tools to study the relative complexities of secure

multi-party computation tasks (functionalities) in the Universal

Composition framework. When one task can be securely realized using

another task as a black-box, we interpret this as a

qualitative, complexity-theoretic reduction between the two tasks.

Virtually all previous characterizations of ...
more >>>

Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter Shor

The class QMA(k), introduced by Kobayashi et al., consists

of all languages that can be verified using k unentangled quantum

proofs. Many of the simplest questions about this class have remained

embarrassingly open: for example, can we give any evidence that k

quantum proofs are more powerful than one? Can ...
more >>>

Vikraman Arvind, T.C. Vijayaraghavan

The \emph{Orbit problem} is defined as follows: Given a matrix $A\in

\Q ^{n\times n}$ and vectors $\x,\y\in \Q ^n$, does there exist a

non-negative integer $i$ such that $A^i\x=\y$. This problem was

shown to be in deterministic polynomial time by Kannan and Lipton in

\cite{KL1986}. In this paper we place ...
more >>>

Stephen A. Fenner, William Gasarch, Brian Postow

Higman showed that if A is *any* language then SUBSEQ(A)

is regular, where SUBSEQ(A) is the language of all

subsequences of strings in A. (The result we attribute

to Higman is actually an easy consequence of his work.)

Let s_1, s_2, s_3, ...
more >>>

Venkatesan Guruswami, Atri Rudra

We prove that binary linear concatenated codes with an outer algebraic code (specifically, a folded Reed-Solomon code) and independently and randomly chosen linear inner codes achieve the list-decoding capacity with high probability. In particular, for any $0 < \rho < 1/2$ and $\epsilon > 0$, there exist concatenated codes of ... more >>>

Ryan O'Donnell

This article accompanies a tutorial talk given at the 40th ACM STOC conference. In it, we give a brief introduction to Fourier analysis of boolean functions and then discuss some applications: Arrow?s Theorem and other ideas from the theory of Social Choice; the Bonami-Beckner Inequality as an extension of Chernoff/Hoeffding ... more >>>

Beate Bollig

Integer multiplication as one of the basic arithmetic functions has been

in the focus of several complexity theoretical investigations.

Ordered binary decision diagrams (OBDDs) are one of the most common

dynamic data structures for boolean functions.

Among the many areas of application are verification, model checking,

computer-aided design, relational algebra, ...
more >>>

Alexander A. Sherstov

Representations of Boolean functions by real polynomials

play an important role in complexity theory. Typically,

one is interested in the least degree of a polynomial

p(x_1,...,x_n) that approximates or sign-represents

a given Boolean function f(x_1,...,x_n). This article

surveys a new and growing body of work in communication

complexity that centers ...
more >>>

Zeev Dvir, Avi Wigderson

A merger is a probabilistic procedure which extracts the

randomness out of any (arbitrarily correlated) set of random

variables, as long as one of them is uniform. Our main result is

an efficient, simple, optimal (to constant factors) merger, which,

for $k$ random vairables on $n$ bits each, uses a ...
more >>>

Farid Ablayev, Alexander Vasiliev

We develop quantum fingerprinting technique for constructing quantum

branching programs (QBPs), which are considered as circuits with an

ability to use classical bits as control variables.

We demonstrate our approach constructing optimal quantum ordered

binary decision diagram (QOBDD) for $MOD_m$ and $DMULT_n$ Boolean

functions. The construction of our technique also ...
more >>>

James R. Lee, Prasad Raghavendra

We show that the multi-commodity max-flow/min-cut gap for series-parallel graphs can be as bad as 2, matching a recent upper bound by Chakrabarti.et.al for this class, and resolving one side of a conjecture of Gupta, Newman, Rabinovich, and Sinclair.

This also improves the largest known gap for planar graphs ... more >>>

Paul Beame, Trinh Huynh

We prove n^Omega(1) lower bounds on the multiparty communication complexity of AC^0 functions in the number-on-forehead (NOF) model for up to Theta(log n) players. These are the first lower bounds for any AC^0 function for omega(loglog n) players. In particular we show that there are families of depth 3 read-once ... more >>>

Manindra Agrawal, V Vinay

We show that proving exponential lower bounds on depth four arithmetic

circuits imply exponential lower bounds for unrestricted depth arithmetic

circuits. In other words, for exponential sized circuits additional depth

beyond four does not help.

We then show that a complete black-box derandomization of Identity Testing problem for depth four ... more >>>

Müller Moritz

We show analogues of a theorem due to Valiant and Vazirani

for intractable parameterized complexity classes such as W[P], W[SAT]

and the classes of the W-hierarchy as well as those of the A-hierarchy.

We do so by proving a general ``logical'' version of it which may be of

independent interest

Or Meir

We define a non-uniform model of PCPs of Proximity, and observe that in this model the non-uniform verifiers can always be made very efficient. Specifically, we show that any non-uniform verifier can be modified to run in time that is roughly polynomial in its randomness and query complexity.

more >>>Noga Alon, Rina Panigrahy, Sergey Yekhanin

The Nearest Codeword Problem (NCP) is a basic algorithmic question in the theory of error-correcting codes. Given a point v in an n-dimensional space over F_2 and a linear subspace L in F_2^n of dimension k NCP asks to find a point l in L that minimizes the (Hamming) distance ... more >>>

Noga Alon, Shai Gutner

The domination number of a graph $G=(V,E)$ is the minimum size of

a dominating set $U \subseteq V$, which satisfies that every

vertex in $V \setminus U$ is adjacent to at least one vertex in

$U$. The notion of a problem kernel refers to a polynomial time

algorithm that achieves ...
more >>>

Scott Aaronson

Whether the class QMA (Quantum Merlin Arthur) is equal to QMA1, or QMA with one-sided error, has been an open problem for years. This note helps to explain why the problem is difficult, by using ideas from real analysis to give a "quantum oracle" relative to which QMA and QMA1 ... more >>>

Lior Malka

We study the question whether the number of rounds in public-coin perfect zero-knowledge (PZK) proofs can be collapsed to a constant. Despite extensive research into the round complexity of interactive

and zero-knowledge protocols, there is no indication how to address this question. Furthermore, the main tool to tackle this question ...
more >>>

Klim Efremenko

Locally Decodable Codes (LDC) allow one to decode any particular

symbol of the input message by making a constant number of queries

to a codeword, even if a constant fraction of the codeword is

damaged. In recent work ~\cite{Yekhanin08} Yekhanin constructs a

$3$-query LDC with sub-exponential length of size

$\exp(\exp(O(\frac{\log ...
more >>>

Dana Moshkovitz, Ran Raz

We show that the NP-Complete language 3Sat has a PCP

verifier that makes two queries to a proof of almost-linear size

and achieves sub-constant probability of error $o(1)$. The

verifier performs only projection tests, meaning that the answer

to the first query determines at most one accepting answer to the

more >>>

Shachar Lovett, Tali Kaufman

A degree-d polynomial p in n variables over a field F is equidistributed if it takes on each of its |F| values close to equally often, and biased otherwise. We say that p has low rank if it can be expressed as a function of a small number of lower ... more >>>

Dmitry Itsykson

We study class AvgBPP that consists of distributional problems that can be solved in average polynomial time (in terms of Levin's average-case complexity) by randomized algorithms with bounded error. We prove that there exists a distributional problem that is complete for AvgBPP under polynomial-time samplable distributions. Since we use deterministic ... more >>>

Neeraj Kayal, Timur Nezhmetdinov

We give a polynomial time algorithm that computes a

decomposition of a finite group G given in the form of its

multiplication table. That is, given G, the algorithm outputs two

subgroups A and B of G such that G is the direct product

of A ...
more >>>

Olaf Beyersdorff, Johannes Köbler, Sebastian Müller

Motivated by strong Karp-Lipton collapse results in bounded arithmetic, Cook and Krajicek have recently introduced the notion of propositional proof systems with advice.

In this paper we investigate the following question: Do there exist polynomially bounded proof systems with advice for arbitrary languages?

Depending on the complexity of the ...
more >>>

Ryan Williams

We prove a model-independent non-linear time lower bound for a slight generalization of the quantified Boolean formula problem (QBF). In particular, we give a reduction from arbitrary languages in alternating time t(n) to QBFs describable in O(t(n)) bits by a reasonable (polynomially) succinct encoding. The reduction works for many reasonable ... more >>>

Felix Brandt, Felix Fischer, Markus Holzer

We study computational problems that arise in the context of iterated dominance in anonymous games, and show that deciding whether a game can be solved by means of iterated weak dominance is NP-hard for anonymous games with three actions. For the case of two actions, this problem can be reformulated ... more >>>

Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steve Homer

Abstract:We define and construct efficient depth-universal and almost-size-universal quantum circuits. Such circuits can be viewed as general-purpose simulators for central classes of quantum circuits and can be used to capture the computational power of the circuit class being simulated. For depth we construct universal circuits whose depth is the same ... more >>>

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson

The classical Direct-Product Theorem for circuits says

that if a Boolean function $f:\{0,1\}^n\to\{0,1\}$ is somewhat hard

to compute on average by small circuits, then the corresponding

$k$-wise direct product function

$f^k(x_1,\dots,x_k)=(f(x_1),\dots,f(x_k))$ (where each

$x_i\in\{0,1\}^n$) is significantly harder to compute on average by

slightly smaller ...
more >>>

Ido Ben-Eliezer, Rani Hod, Shachar Lovett

We study the problem of how well a typical multivariate polynomial can be approximated by lower degree polynomials over $\F$.

We prove that, with very high probability, a random degree $d$ polynomial has only an exponentially small correlation with all polynomials of degree $d-1$, for all degrees $d$ up to ...
more >>>

Alexander Razborov

In 1990, Linial and Nisan asked if any polylog-wise independent distribution fools any function in AC^0. In a recent remarkable development, Bazzi solved this problem for the case of DNF formulas.

The aim of this note is to present a simplified version of his proof.

Paul Beame, Trinh Huynh

We prove an n^{Omega(1)}/2^{O(k)} lower bound on the randomized k-party communication complexity of read-once depth 4 AC^0 functions in the number-on-forehead (NOF) model for O(log n) players. These are the first non-trivial lower bounds for general NOF multiparty communication complexity for any AC^0 function for omega(log log n) players. For ... more >>>

Yijia Chen, Jörg Flum

In [Blass, Gurevich, and Shelah, 99] a logic L_Y has been introduced as a possible candidate for a logic capturing the PTIME properties of structures (even in the absence of an ordering of their universe). A reformulation of this problem in terms of a parameterized halting problem p-Acc for nondeterministic ... more >>>

Sanjeeb Dash

We prove a monotone interpolation property for split cuts which, together with results from Pudlak (1997), implies that cutting-plane proofs which use split cuts have exponential length in the worst case.

As split cuts are equivalent to mixed-integer rounding cuts and Gomory mixed-integer cuts, cutting-plane proofs using the above cuts ...
more >>>

Farid Ablayev, Airat Khasianov, Alexander Vasiliev

We consider Generalized Equality, the Hidden Subgroup,

and related problems in the context of quantum Ordered Binary

Decision Diagrams. For the decision versions of considered problems

we show polynomial upper bounds in terms of quantum OBDD width. We

apply a new modification of the fingerprinting technique and present

the algorithms ...
more >>>

Vikraman Arvind, Partha Mukhopadhyay

Motivated by the quantum algorithm in \cite{MN05} for testing

commutativity of black-box groups, we study the following problem:

Given a black-box finite ring $R=\angle{r_1,\cdots,r_k}$ where

$\{r_1,r_2,\cdots,r_k\}$ is an additive generating set for $R$ and a

multilinear polynomial $f(x_1,\cdots,x_m)$ over $R$ also accessed as

a ...
more >>>

Tomas Feder, Carlos Subi

It has been shown that for every perfect matching $M$ of the $d$-dimensional

$n$-vertex hypercube, $d\geq 2, n=2^d$, there exists a second perfect matching

$M'$ such that the union of $M$ and $M'$ forms a Hamiltonian circuit of the

$d$-dimensional hypercube. We prove a generalization of a special case of ...
more >>>

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

We consider the task of testing properties of Boolean functions that

are invariant under linear transformations of the Boolean cube. Previous

work in property testing, including the linearity test and the test

for Reed-Muller codes, has mostly focused on such tasks for linear

properties. The one exception is a test ...
more >>>

Noam Berger, Kapur Nevin, Schulman Leonard, Vazirani Vijay

Abstract. We study the decision theory of a maximally risk-averse investor | one whose objec-

tive, in the face of stochastic uncertainties, is to minimize the probability of ever going broke. With

a view to developing the mathematical basics of such a theory, we start with a very simple model

more >>>

Ulrich Schöpp, Martin Hofmann

We study pointer programs as a model of structured computation within LOGSPACE. Pointer programs capture the common description of LOGSPACE algorithms as programs that take as input some structured data (e.g. a graph) and that store in memory only a constant number of pointers to the input (e.g. to the ... more >>>

Vitaly Feldman

We study the properties of the agnostic learning framework of Haussler (1992)and Kearns, Schapire and Sellie (1992). In particular, we address the question: is there any situation in which membership queries are useful in agnostic learning?

Our results show that the answer is negative for distribution-independent agnostic learning and positive ... more >>>

Scott Aaronson, John Watrous

While closed timelike curves (CTCs) are not known to exist, studying their consequences has led to nontrivial insights in general relativity, quantum information, and other areas. In this paper we show that if CTCs existed, then quantum computers would be no more powerful than classical computers: both would have the ... more >>>

Cristopher Moore, Alexander Russell

The proof of Toda's celebrated theorem that the polynomial hierarchy is contained in $\P^\numP$ relies on the fact that, under mild technical conditions on the complexity class $\mathcal{C}$, we have $\exists \,\mathcal{C} \subset \BP \cdot \oplus \,\mathcal{C}$. More concretely, there is a randomized reduction which transforms nonempty sets and the ... more >>>

Piotr Berman, Marek Karpinski, Alexander Zelikovsky

We give a 1.25 approximation algorithm for the Steiner Tree Problem with distances one and two, improving on the best known bound for that problem.

more >>>Brendan Juba, Madhu Sudan

We continue the investigation of the task of meaningful communication among intelligent entities (players, agents) without any prior common language. Our generic thesis is that such communication is feasible provided the goals of the communicating players are verifiable and compatible. In a previous work we gave supporting evidence for this ... more >>>

Andrew Drucker

In Direct Sum problems [KRW], one tries to show that for a given computational model, the complexity of computing a collection $F = \{f_1(x_1), \ldots f_l(x_l)\}$ of finite functions on independent inputs is approximately the sum of their individual complexities. In this paper, by contrast, we study the diversity of ... more >>>

Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg

Referring to the query complexity of property testing,

we prove the existence of a rich hierarchy of corresponding

complexity classes. That is, for any relevant function $q$,

we prove the existence of properties that have testing

complexity Theta(q).

Such results are proven in three standard

domains often considered in property ...
more >>>

Victor Chen

A hypergraph dictatorship test is first introduced by Samorodnitsky

and Trevisan and serves as a key component in

their unique games based $\PCP$ construction. Such a test has oracle

access to a collection of functions and determines whether all the

functions are the same dictatorship, or all their low degree ...
more >>>

Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena

In this paper we develop techniques that eliminate the need of the Generalized

Riemann Hypothesis (GRH) from various (almost all) known results about deterministic

polynomial factoring over finite fields. Our main result shows that given a

polynomial f(x) of degree n over a finite field k, we ...
more >>>

Chris Peikert

We construct public-key cryptosystems that are secure assuming the

\emph{worst-case} hardness of approximating the length of a shortest

nonzero vector in an $n$-dimensional lattice to within a small

$\poly(n)$ factor. Prior cryptosystems with worst-case connections

were based either on the shortest vector problem for a \emph{special

class} of lattices ...
more >>>

Marek Karpinski, Warren Schudy

We design a linear time approximation scheme for the Gale-Berlekamp Switching Game and generalize it to a wider class of dense fragile minimization problems including the Nearest Codeword Problem (NCP) and Unique Games Problem. Further applications include, among other things, finding a constrained form of matrix rigidity and maximum likelihood ... more >>>

Adi Akavia

Computing the Fourier transform is a basic building block used in numerous applications. For data intensive applications, even the $O(N\log N)$ running time of the Fast Fourier Transform (FFT) algorithm may be too slow, and {\em sub-linear} running time is necessary. Clearly, outputting the entire Fourier transform in sub-linear ... more >>>

Luca Trevisan, Madhur Tulsiani, Salil Vadhan

We show that every high-entropy distribution is indistinguishable from an

efficiently samplable distribution of the same entropy. Specifically, we prove

that if $D$ is a distribution over $\{ 0,1\}^n$ of min-entropy at least $n-k$,

then for every $S$ and $\epsilon$ there is a circuit $C$ of size at most

$S\cdot ...
more >>>

Madhur Tulsiani

We study integrality gaps for SDP relaxations of constraint satisfaction problems, in the hierarchy of SDPs defined by Lasserre. Schoenebeck recently showed the first integrality gaps for these

problems, showing that for MAX k-XOR, the ratio of the SDP optimum to the integer optimum may be as large as ...
more >>>

Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra, Prasad Raghavendra

We design the first efficient algorithms and prove new combinatorial bounds for list decoding tensor products of codes and interleaved codes.

1)We show that for every code, the ratio of its list decoding radius to its minimum distance stays unchanged under the tensor product operation (rather than squaring, as one ... more >>>

Jack H. Lutz

If $S$ is an infinite sequence over a finite alphabet $\Sigma$ and $\beta$ is a probability measure on $\Sigma$, then the {\it dimension} of $ S$ with respect to $\beta$, written $\dim^\beta(S)$, is a constructive version of Billingsley dimension that coincides with the (constructive Hausdorff) dimension $\dim(S)$ when $\beta$ is ... more >>>

Zenon Sadowski

We investigate the connection between optimal propositional

proof systems and complete languages for promise classes.

We prove that an optimal propositional proof system exists

if and only if there exists a propositional proof system

in which every promise class with the test set in co-NP

...
more >>>

Nitin Saxena, C. Seshadhri

We show that the rank of a depth-3 circuit (over any field) that is simple,

minimal and zero is at most O(k^3\log d). The previous best rank bound known was

2^{O(k^2)}(\log d)^{k-2} by Dvir and Shpilka (STOC 2005).

This almost resolves the rank question first posed by ...
more >>>

Marc Kaplan, Sophie Laplante

A very important problem in quantum communication complexity is to show that there is, or isn?t, an exponential gap between randomized and quantum complexity for a total function. There are currently no clear candidate functions for such a separation; and there are fewer and fewer randomized lower bound techniques that ... more >>>

Chris Calabro

One way to quantify how dense a multidag is in long paths is to find

the largest n, m such that whichever ≤ n edges are removed, there is still

a path from an original input to an original output with ≥ m edges

- the larger ...
more >>>

Shachar Lovett, Tali Kaufman

In this work we study the list-decoding size of Reed-Muller codes. Given a received word and a distance parameter, we are interested in bounding the size of the list of Reed-Muller codewords that are within that distance from the received word. Previous bounds of Gopalan, Klivans and Zuckerman~\cite{GKZ08} on the ... more >>>