Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

How to color 3 colorable graphs with few colors is a problem of longstanding interest. The best polynomial-time algorithm uses

n

0.2072

colors. There are no indications that coloring using say

O

(log

n

) colors is hard. It has been suggested that SDP hierarchies could be used to design algorithms that use

n

ε

colors for arbitrarily small

ε

 > 0.

We explore this possibility in this paper and find some cause for optimism. While the case of general graphs is till open, we can analyse the Lasserre relaxation for two interesting families of graphs.

For graphs with low

threshold rank

(a class of graphs identified in the recent paper of Arora, Barak and Steurer on the unique games problem), Lasserre relaxations can be used to find an independent set of size Ω(

n

) (i.e., progress towards a coloring with

O

(log

n

) colors) in

n

O

(

D

)

time, where

D

is the threshold rank of the graph. This algorithm is inspired by recent work of Barak, Raghavendra, and Steurer on using Lasserre Hierarchy for unique games. The algorithm can also be used to show that known integrality gap instances for SDP relaxations like

strict vector chromatic number

cannot survive a few rounds of Lasserre lifting, which also seems reason for optimism.

For

distance transitive

graphs of diameter Δ, we can show how to color them using

O

(log

n

) colors in

$n^{2^{O(\Delta)}}$

time. This family is interesting because the family of graphs of diameter

O

(1/

ε

) is easily seen to be

complete

for coloring with

n

ε

colors. The distance-transitive property implies that the graph “looks” the same in all neighborhoods.

The full version of this paper can be found at:

http://www.cs.princeton.edu/~rongge/LasserreColoring.pdf

.

In recent work of Hazan and Krauthgamer (SICOMP 2011), it was shown that finding an

ε

-approximate Nash equilibrium with near-optimal value in a two-player game is as hard as finding a hidden clique of size

O

(log

n

) in the random graph

$G(n,\frac12)$

. This raises the question of whether a similar intractability holds for approximate Nash equilibrium without such constraints. We give evidence that the constraint of near-optimal value makes the problem distinctly harder: a simple algorithm finds an optimal

$\frac{1}{2}$

-approximate equilibrium, while finding strictly better than

$\frac12$

-approximate equilibria is as hard as the Hidden Clique problem. This is in contrast to the unconstrained problem where more sophisticated algorithms, achieving better approximations, are known.

Unlike general Nash equilibrium, which is in PPAD, optimal (maximum value) Nash equilibrium is NP-hard. We proceed to show that optimal Nash equilibrium is just one of several known NP-hard problems related to Nash equilibrium, all of which have approximate variants which are as hard as finding a planted clique. In particular, we show this for approximate variants of the following problems: finding a Nash equilibrium with value greater than

η

(for any

η

 > 0, even when the best Nash equilibrium has value 1 − 

η

), finding a second Nash equilibrium, and finding a Nash equilibrium with small support.

Finally, we consider the complexity of approximate pure Bayes Nash equilibria in two-player games. Here we show that for general Bayesian games the problem is NP-hard. For the special case where the distribution over types is uniform, we give a quasi-polynomial time algorithm matched by a hardness result based on the Hidden Clique problem.

The goal of sparse recovery is to recover the (approximately) best

k

-sparse approximation

$\hat{x}$

of an

n

-dimensional vector

x

from linear measurements

Ax

of

x

. We consider a variant of the problem which takes into account

partial knowledge

about the signal. In particular, we focus on the scenario where, after the measurements are taken, we are given a set

S

of size

s

that is supposed to contain most of the “large” coefficients of

x

. The goal is then to find

$\hat{x}$

such that

$$ \| x-\hat{x}\|_p \le C \min_{\substack{k\text{-sparse }x'\\\textrm{supp}(x') \subseteq S }} \|x-x'\|_q\enspace.$$

We refer to this formulation as the

sparse recovery with partial support knowledge problem (

$\textrm{SRPSK}$

)

. We show that

$\textrm{SRPSK}$

can be solved, up to an approximation factor of

C

 = 1 + 

ε

, using

O

( (

k

/

ε

) log(

s

/

k

)) measurements, for

p

 = 

q

 = 2. Moreover, this bound is tight as long as

s

 = 

O

(

εn

/ log(

n

/

ε

)). This completely resolves the asymptotic measurement complexity of the problem except for a very small range of the parameter

s

.

To the best of our knowledge, this is the first variant of (1 + 

ε

)-approximate sparse recovery for which the asymptotic measurement complexity has been determined.

Recently, Chakrabarty et al. [5] initiated a systematic study of capacitated set cover problems, and considered the question of how their approximability relates to that of the uncapacitated problem on the same underlying set system. Here, we investigate this connection further and give several results, both positive and negative. In particular, we show that if the underlying set system satisfies a certain

hereditary property

, then the approximability of the capacitated problem is closely related to that of the uncapacitated version. We also give related lower bounds, and show that the hereditary property is necessary to obtain non-trivial results. Finally, we give some results for capacitated covering problems on set systems with low hereditary discrepancy and low VC dimension.

We design an algorithm to embed graph metrics into ℓ

p

with dimension and distortion both dependent only upon the bandwidth of the graph. In particular we show that any graph of bandwidth

k

embeds with distortion polynomial in

k

into

O

(log

k

) dimensional ℓ

p

, 1 ≤ 

p

 ≤ ∞. Prior to our result the only known embedding with distortion independent of

n

was into high dimensional ℓ

1

and had distortion exponential in

k

. Our low dimensional embedding is based on a general method for reducing dimension in an ℓ

p

embedding, satisfying certain conditions, to the intrinsic dimension of the point set, without substantially increasing the distortion. As we observe that the family of graphs with bounded bandwidth are doubling, our result can be viewed as a positive answer to a conjecture of Assouad [2], limited to this family. We also study an extension to graphs of bounded tree-bandwidth.

We develop constant-factor approximation algorithms for minimizing the maximum movement made by pebbles on a graph to reach a configuration in which the pebbles form a connected subgraph (connectivity), or interconnect a constant number of stationary nodes (Steiner tree). These problems model the minimization of the total time required to reconfigure a robot swarm to achieve a proximity (e.g., radio) network with these connectivity properties. Our approximation factors are tight up to constant factors, as none of these problems admit a (2 − 

ε

)-approximation assuming P ≠ NP.

Given a metric space on

n

points, an

α

-approximate

universal

algorithm for the Steiner tree problem outputs a distribution over rooted spanning trees such that for any subset

X

of vertices containing the root, the expected cost of the induced subtree is within an

α

factor of the optimal Steiner tree cost for

X

. An

α

-approximate

differentially private

algorithm for the Steiner tree problem takes as input a subset

X

of vertices, and outputs a tree distribution that induces a solution within an

α

factor of the optimal as before, and satisfies the additional property that for any set

X

′ that differs in a single vertex from

X

, the tree distributions for

X

and

X

′ are “close” to each other. Universal and differentially private algorithms for TSP are defined similarly. An

α

-approximate universal algorithm for the Steiner tree problem or TSP is also an

α

-approximate differentially private algorithm. It is known that both problems admit

O

(log

n

)-approximate universal algorithms, and hence

O

(log

n

) approximate differentially private algorithms as well.

We prove an Ω(log

n

) lower bound on the approximation ratio achievable for the universal Steiner tree problem and the universal TSP, matching the known upper bounds. Our lower bound for the Steiner tree problem holds even when the algorithm is allowed to output a more general solution of a distribution on paths to the root. We then show that whenever the universal problem has a lower bound that satisfies an additional property, it implies a similar lower bound for the differentially private version. Using this converse relation between universal and private algorithms, we establish an Ω(log

n

) lower bound for the differentially private Steiner tree and the differentially private TSP. This answers a question of Talwar [19]. Our results highlight a natural connection between universal and private approximation algorithms that is likely to have other applications.

We study social welfare in one-sided matching markets where the goal is to efficiently allocate

n

items to

n

agents that each have a complete, private preference list and a unit demand over the items. Our focus is on allocation mechanisms that do not involve any monetary payments. We consider two natural measures of social welfare: the

ordinal welfare factor

which measures the number of agents that are at least as happy as in some unknown, arbitrary benchmark allocation, and the

linear welfare factor

which assumes an agent’s utility linearly decreases down his preference lists, and measures the total utility to that achieved by an optimal allocation.

We analyze two matching mechanisms which have been extensively studied by economists. The first mechanism is the random serial dictatorship (RSD) where agents are ordered in accordance with a randomly chosen permutation, and are successively allocated their best choice among the unallocated items. The second mechanism is the probabilistic serial (PS) mechanism of Bogomolnaia and Moulin [8], which computes a fractional allocation that can be expressed as a convex combination of integral allocations. The welfare factor of a mechanism is the infimum over all instances. For RSD, we show that the ordinal welfare factor is asymptotically 1/2, while the linear welfare factor lies in the interval [.526,2/3]. For PS, we show that the ordinal welfare factor is also 1/2 while the linear welfare factor is roughly 2/3. To our knowledge, these results are the first non-trivial performance guarantees for these natural mechanisms.

The location-routing problem arises in the context of providing integrated support for logistics in a number of transportation settings, where given a set of requests and potential depot locations, one must simultaneously decide where to locate depots as well as how to route tours so that all requests are connected to an open depot. This problem can be formulated either with specific costs incurred for choosing to open each depot, or with an upper bound

k

on the number of open depots, which we call the

k-location-routing problem

.

We develop a primal-dual schema and use Lagrangian relaxation to provide a 2-approximation algorithm for the

k

-location-routing problem; no constant performance guarantee was known previously for this problem. This strengthens previous work of Goemans & Williamson who gave a 2-approximation algorithm for the variant in which there are opening costs, but no limit on the number of depots. We give a new primal-dual algorithm and a strengthened analysis that proves a so-called Lagrangian-preserving performance guarantee. In contrast to the results of Jain & Vazirani for the uncapacitated facility location and

k

-median problems, our results have the surprising property that our performance guarantee for the

k

-location-routing problem matches the guarantee for the version in which there are depot opening costs; furthermore, this relies on a simple structural property of the algorithm that allows us to identify the critical Lagrangian value for the opening cost with a single execution of the primal-dual algorithm, rather than invoking a bisection search.

We consider the problem of scheduling a set of resources over time. Each resource is specified by a set of time intervals (and the associated amount of resource available), and we can choose to schedule it in one of these intervals. The goal is to maximize the number of demands satisfied, where each demand is an interval with a starting and ending time, and a certain resource requirement. This problem arises naturally in many scenarios, e.g., the resource could be an energy source, and we would like to suitably combine different energy sources to satisfy as many demands as possible. We give a constant factor randomized approximation algorithm for this problem, under suitable assumptions (the so called no-bottleneck assumptions). We show that without these assumptions, the problem is as hard as the independent set problem. Our proof requires a novel configuration LP relaxation for this problem. The LP relaxation exploits the pattern of demand sharing that can occur across different resources.

In this paper, we consider two geometric optimization problems:

Rectangle Coloring

problem (

RCOL

) and

Maximum Independent Set of Rectangles

(

MISR

). In

RCOL

, we are given a collection of

n

rectangles in the plane where overlapping rectangles need to be colored differently, and the goal is to find a coloring using minimum number of colors. Let

q

be the maximum clique size of the instance, i.e. the maximum number of rectangles containing the same point. We are interested in bounding the ratio

σ

(

q

) between the total number of colors used and the clique size. This problem was first raised by graph theory community in 1960 when the ratio of

σ

(

q

) ≤ 

O

(

q

) was proved. Over decades, except for special cases, only the constant in front of

q

has been improved. In this paper, we present a new bound for

σ

(

q

) that significantly improves the known bounds for a broad class of instances.

The bound

σ

(

q

) has a strong connection with the integrality gap of natural LP relaxation for

MISR

, in which the input is a collection of rectangles where each rectangle is additionally associated with non-negative weight, and our objective is to find a maximum-weight independent set of rectangles.

MISR

has been studied extensively and has applications in various areas of computer science. Our new bounds for

RCOL

imply new approximation algorithms for a broad class of

MISR

, including (i)

O

(loglog

n

) approximation algorithm for unweighted

MISR

, matching the result by Chalermsook and Chuzhoy, and (ii)

O

(loglog

n

)-approximation algorithm for the

MISR

instances arising in the

Unsplittable Flow Problem

on paths. Our technique builds on and generalizes past works.

We consider the following single-machine scheduling problem, which is often denoted 1|| ∑ 

f

j

: we are given

n

jobs to be scheduled on a single machine, where each job

j

has an integral processing time

p

j

, and there is a nondecreasing, nonnegative cost function

f

j

(

C

j

) that specifies the cost of finishing

j

at time

C

j

; the objective is to minimize

$\sum_{j=1}^n f_j(C_j)$

. Bansal & Pruhs recently gave the first constant approximation algorithm and we improve on their 16-approximation algorithm, by giving a primal-dual pseudo-polynomial-time algorithm that finds a solution of cost at most twice the optimal cost, and then show how this can be extended to yield, for any

ε

 > 0, a (2 + 

ε

)-approximation algorithm for this problem. Furthermore, we generalize this result to allow the machine’s speed to vary over time arbitrarily, for which no previous constant-factor approximation algorithm was known.

We consider the

Tree Augmentation

problem: given a graph

G

 = (

V

,

E

) with edge-costs and a tree

T

on

V

disjoint to

E

, find a minimum-cost edge-subset

F

 ⊆ 

E

such that

T

 ∪ 

F

is 2-edge-connected.

Tree Augmentation

is equivalent to the problem of finding a minimum-cost edge-cover

F

 ⊆ 

E

of a laminar set-family. The best known approximation ratio for

Tree Augmentation

is 2, even for trees of radius 2. As laminar families play an important role in network design problems, obtaining a better ratio is a major open problem in network design. We give a (1 + ln 2)-approximation algorithm for trees of constant radius. Our algorithm is based on a new decomposition of problem solutions, which may be of independent interest.

We consider the problem of identifying periodic trends in data streams. We say a signal

${\mathbf a} \in \ensuremath{\mathbb{R}} ^n$

is

p

-periodic if

a

i

 = 

a

i

 + 

p

for all

i

 ∈ [

n

 − 

p

]. Recently, Ergün et al. [4] presented a one-pass,

O

(

polylog

n

)-space algorithm for identifying the smallest period of a signal. Their algorithm required

${\mathbf a}$

to be presented in the

time-series

model, i.e.,

a

i

is the

i

th element in the stream. We present a more general linear sketch algorithm that has the advantages of being applicable to a) the

turnstile stream model

, where coordinates can be incremented/decremented in an arbitrary fashion and b) the

parallel

or

distributed

setting where the signal is distributed over multiple locations/machines. We also present sketches for (1 + 

ε

) approximating the ℓ

2

distance between

${\mathbf a}$

and the nearest

p

-periodic signal for a given

p

. Our algorithm uses

O

(

ε

− 2

polylog

n

) space, comparing favorably to an earlier time-series result that used

$O(\epsilon^{-5.5} \sqrt{p} polylog n)$

space for estimating the Hamming distance to the nearest

p

-periodic signal. Our last periodicity result is an algorithm for estimating the periodicity of a sequence in the presence of noise. We conclude with a small-space algorithm for identifying when two signals are exact (or nearly) cyclic shifts of one another. Our algorithms are based on bilinear sketches [10] and combining Fourier transforms with stream processing techniques such as ℓ

p

sampling and sketching [13, 11].

A spanning tree

T

of a graph

G

is called a

tree t-spanner

of

G

if the distance between every pair of vertices in

T

is at most

t

times their distance in

G

. In this paper, we present an algorithm which constructs for an

n

-vertex

m

-edge unweighted graph

G

: (1) a tree

$(2\lfloor\log_2 n\rfloor)$

-spanner in

O

(

m

log

n

) time, if

G

is a chordal graph; (2) a tree

$(2\rho\lfloor\log_2 n\rfloor)$

-spanner in

O

(

mn

log

2

n

) time or a tree

$(12\rho\lfloor\log_2 n\rfloor)$

-spanner in

O

(

m

log

n

) time, if

G

is a graph admitting a Robertson-Seymour’s tree-decomposition with bags of radius at most

ρ

in

G

; and (3) a tree

$(2\lceil{t/2}\rceil\lfloor\log_2 n\rfloor)$

-spanner in

O

(

mn

log

2

n

) time or a tree

$(6t\lfloor\log_2 n\rfloor)$

-spanner in

O

(

m

log

n

) time, if

G

is an arbitrary graph admitting a tree

t

-spanner. For the latter result we use a new necessary condition for a graph to have a tree

t

-spanner: if a graph

G

has a tree

t

-spanner, then

G

admits a Robertson-Seymour’s tree-decomposition with bags of radius at most ⌈

t

/2⌉ in

G

.

We give a polynomial time Turing reduction from the

$\gamma^2\sqrt{n}$

-approximate closest vector problem on a lattice of dimension

n

to a

γ

-approximate oracle for the shortest vector problem. This is an improvement over a reduction by Kannan, which achieved

$\gamma^2n^{\frac{3}{2}}$

.

The problem of finding “small” sets that meet every straight-line which intersects a given convex region was initiated by Mazurkiewicz in 1916. We call such a set an

opaque set

or a

barrier

for that region. We consider the problem of computing the shortest barrier for a given convex polygon with

n

vertices. No exact algorithm is currently known even for the simplest instances such as a square or an equilateral triangle. For general barriers, we present a

O

(

n

) time approximation algorithm with ratio

$\frac{1}{2}+ \frac{2 +\sqrt{2}}{\pi}=1.5867\ldots$

. For connected barriers, we can achieve the approximation ratio

$\frac{\pi+5}{\pi+2} =1.5834\ldots$

again in

O

(

n

) time. We also show that if the barrier is restricted to the interior and the boundary of the input polygon, then the problem admits a fully polynomial-time approximation scheme for the connected case and a quadratic-time exact algorithm for the single-arc case. These are the first approximation algorithms obtained for this problem.

We consider online and offline problems related to exploring and surveying a region by a swarm of robots with limited communication range. The minimum relay triangulation problem (MRTP) asks for placing a minimum number of robots, such that their communication graph is a triangulated cover of the region. The maximum area triangulation problem (MATP) aims at finding a placement of

n

robots such that their communication graph contains a root and forms a triangulated cover of a maximum possible amount of area. Both problems are geometric versions of natural graph optimization problems.

The offline version of both problems share a decision problem, which we prove to be NP-hard. For the online version of the MRTP, we give a lower bound of 6/5 for the competitive ratio, and a strategy that achieves a ratio of 3; for different offline versions, we describe polynomial-time approximation schemes. For the MATP we show that no competitive ratio exists for the online problem, and give polynomial-time approximation schemes for offline versions.

The Classical Secretary Problem was introduced during the 60’s of the 20

th

century, nobody is sure exactly when. Since its introduction, many variants of the problem have been proposed and researched. In the classical secretary problem, and many of its variant, the input (which is a set of secretaries, or elements) arrives in a random order. In this paper we apply to the secretary problem a simple observation which states that the random order of the input can be generated by independently choosing a random continuous arrival time for each secretary. Surprisingly, this simple observation enables us to improve the competitive ratio of several known and studied variants of the secretary problem. In addition, in some cases the proofs we provide assuming random arrival times are shorter and simpler in comparison to existing proofs. In this work we consider three variants of the secretary problem, all of which have the same objective of maximizing the value of the chosen set of secretaries given a monotone submodular function

f

. In the first variant we are allowed to hire a set of secretaries only if it is an independent set of a given partition matroid. The second variant allows us to choose any set of up to

k

secretaries. In the last and third variant, we can hire any set of secretaries satisfying a given knapsack constraint.

We study a location-routing problem in the context of capacitated vehicle routing. The input to

k

-LocVRP is a set of demand locations in a metric space and a fleet of

k

vehicles each of capacity

Q

. The objective is to

locate

k

depots, one for each vehicle, and

compute routes

for the vehicles so that all demands are satisfied and the total cost is minimized. Our main result is a constant-factor approximation algorithm for

k

-LocVRP. To achieve this result, we reduce

k

-LocVRP to the following generalization of

k

median, which might be of independent interest. Given a metric (

V

,

d

), bound

k

and parameter

ρ

 ∈ ℝ

 + 

, the goal in the

k median forest

problem is to find

S

 ⊆ 

V

with |

S

| = 

k

minimizing:

$$\sum_{u\in V} d(u,S) \quad + \quad \rho\cdot d\big(\,\mbox{MST}(V/S)\,\big),$$

where

d

(

u

,

S

) =  min

w

 ∈ 

S

d

(

u

,

w

) and

$\mbox{MST}(V/S)$

is a minimum spanning tree in the graph obtained by contracting

S

to a single vertex. We give a (3 + 

ε

)-approximation algorithm for

k

median forest, which leads to a (12 + 

ε

)-approximation algorithm for

k

-LocVRP, for any constant

ε

 > 0. The algorithm for

k

median forest is

t

-swap local search, and we prove that it has locality gap

$3+\frac2t$

; this generalizes the corresponding result for

k

median [3].

Finally we consider the

k

median forest problem when there is a different (unrelated) cost function

c

for the MST part, i.e. the objective is

$\sum_{u\in V} d(u,S) \,+ \,c (\,\mbox{MST}(V/S)\,)$

. We show that the locality gap for this problem is unbounded even under multi-swaps, which contrasts with the

c

 = 

d

case. Nevertheless, we obtain a constant-factor approximation algorithm, using an LP based approach along the lines of [12].

We study the problem where we are given a system of polynomial equations defined by multivariate polynomials over

GF

[2] of fixed constant degree

d

 > 1 and the aim is to satisfy the maximal number of equations. A random assignment approximates this problem within a factor 2

− 

d

and we prove that for any

ε

 > 0, it is NP-hard to obtain a ratio 2

− 

d

 + 

ε

. When considering instances that are perfectly satisfiable we give a probabilistic polynomial time algorithm that, with high probability, satisfies a fraction 2

1 − 

d

 − 2

1 − 2

d

and we prove that it is NP-hard to do better by an arbitrarily small constant. The hardness results are proved in the form of inapproximability results of Max-CSPs where the predicate in question has the desired form and we give some immediate results on approximation resistance of some predicates.

A central question in algorithmic mechanism design is to understand the additional difficulty introduced by truthfulness requirements in the design of approximation algorithms for social welfare maximization. In this paper, by studying the problem of single-parameter combinatorial auctions, we obtain the first black-box reduction that converts

any

approximation algorithm to a truthful mechanism with essentially the

same

approximation factor in a prior-free setting. In fact, our reduction works for the more general class of

symmetric single-parameter

problems. Here, a problem is symmetric if its allocation space is closed under permutations.

As extensions, we also take an initial step towards exploring the power of black-box reductions for general single-parameter and multi-parameter problems by showing several positive and negative results. We believe that the algorithmic and game theoretic insights gained from our approach will help better understand the tradeoff between approximability and the incentive compatibility.

We study the space and time complexity of approximating distributions of

l

-step random walks in simple (possibly directed) graphs

G

. While very efficient algorithms for obtaining

additive

ε

-approximations have been developed in the literature, no non-trivial results with multiplicative guarantees are known, and obtaining such approximations is the main focus of this paper. Specifically, we ask the following question: given a bound

S

on the space used, what is the minimum threshold

t

 > 0 such that

l

-step transition probabilities for all pairs

u

,

v

 ∈ 

V

such that

$P_{uv}^l\geq t$

can be approximated within a 1±

ε

factor? How fast can an approximation be obtained?

We show that the following surprising behavior occurs. When the bound on the space is

S

 = 

o

(

n

2

/

d

), where

d

is the minimum out-degree of

G

, no approximation can be achieved for non-trivial values of the threshold

t

. However, if an extra factor of

s

space is allowed, i.e.

$S=\tilde \Omega(sn^2/d)$

space, then the threshold

t

is

exponentially small in the length of the walk l

and even very small transition probabilities can be approximated up to a 1±

ε

factor. One instantiation of these guarantees is as follows: any almost regular directed graph can be represented in

$\tilde O(l n^{3/2+{\epsilon}})$

space such that all probabilities larger than

n

− 10

can be approximated within a (1±

ε

) factor as long as

l

 ≥ 40/

ε

2

. Moreover, we show how to estimate of such probabilities faster than matrix multiplication time.

For undirected graphs, we also give small space oracles for estimating

$P^l_{uv}$

using a notion of bicriteria approximation based on approximate distance oracles of Thorup and Zwick [STOC’01].

We settle the approximability status of the

Minimum Betweenness

problem in tournaments by designing a

polynomial time approximation scheme (PTAS)

. No constant factor approximation was previously known. We also introduce a more general class of so-called

fragile

ranking problems and construct PTASs for them. The results depend on a new technique of dealing with fragile ranking constraints and could be of independent interest.

We study several network design problems with degree constraints. For the degree-constrained 2-connected subgraph problem we obtain a factor 6 violation for the degrees with 4 approximation for the cost. This improves upon the logarithmic degree violation and no cost guarantee obtained by Feder, Motwani, and Zhu (2006). Then we consider the problem of finding an arborescence with at least

k

terminals and with minimum maximum outdegree. We show that the natural LP-relaxation has a gap of

$\Omega\left(\sqrt{k}\right)$

or

$\Omega\left(n^{1/4}\right)$

with respect to the multiplicative degree bound violation. We overcome this hurdle by a

combinatorial

$O(\sqrt{(k\log k)/\Delta^*})$

-approximation algorithm, where Δ

*

denotes the maximum degree in the optimum solution. We also give an Ω(log

n

) lower bound on approximating this problem. Then we consider the undirected version of this problem, however, with an extra diameter constraint, and give an Ω(log

n

) lower bound on the approximability of this version. Finally, we consider a closely related prize-collecting degree-constrained Steiner Network problem. We obtain several results in this direction by reducing the prize-collecting variant to the regular one.

In this paper we provide improved approximation algorithms for the Min-Max Tree Cover and Bounded Tree Cover problems. Given a graph

G

 = (

V

,

E

) with weights

w

:

E

 → ℕ

 + 

, a set

T

1

,

T

2

,…,

T

k

of subtrees of

G

is called a tree cover of

G

if

$V=\bigcup_{i=1}^k V(T_i)$

. In the Min-Max

k

-tree Cover problem we are given graph

G

and a positive integer

k

and the goal is to find a tree cover with

k

trees, such that the weight of the largest tree in the cover is minimized. We present a 3-approximation algorithm for this improving the two different approximation algorithms presented in [1,5] with ratio 4. The problem is known to have an APX-hardness lower bound of

$\frac{3}{2}$

[12]. In the Bounded Tree Cover problem we are given graph

G

and a bound

λ

and the goal is to find a tree cover with minimum number of trees such that each tree has weight at most

λ

. We present a 2.5-approximation algorithm for this, improving the 3-approximation bound in [1].

We consider two generalizations of the problem of finding a sparsest cut in a graph. The first is to find a partition of the vertex set into

m

parts so as to minimize the sparsity of the partition (defined as the ratio of the weight of edges between parts to the total weight of edges incident to the smallest

m

 − 1 parts). The second is to find a subset of minimum sparsity that contains at most a 1/

m

fraction of the vertices. Our main results are extensions of Cheeger’s classical inequality to these problems via higher eigenvalues of the graph. In particular, for the sparsest

m

-partition, we prove that the sparsity is at most

$8\sqrt{1-\lambda_m} \log m$

where

λ

m

is the

m

th

largest eigenvalue of the normalized adjacency matrix. For sparsest small-set, we bound the sparsity by

$O(\sqrt{(1-\lambda_{m^2})\log m})$

.

We study the problem of computing the minimum vertex cover on

k

-uniform

k

-partite hypergraphs when the

k

-partition is given. On bipartite graphs (

k

 = 2), the minimum vertex cover can be computed in polynomial time. For general

k

, the problem was studied by Lovász [23], who gave a

$\frac{k}{2}$

-approximation based on the standard LP relaxation. Subsequent work by Aharoni, Holzman and Krivelevich [1] showed a tight integrality gap of

$\left(\frac{k}{2} - o(1)\right)$

for the LP relaxation. While this problem was known to be NP-hard for

k

 ≥ 3, the first non-trivial NP-hardness of approximation factor of

$\frac{k}{4}-\varepsilon $

was shown in a recent work by Guruswami and Saket [13]. They also showed that assuming Khot’s Unique Games Conjecture yields a

$\frac{k}{2}-\varepsilon $

inapproximability for this problem, implying the optimality of Lovász’s result.

In this work, we show that this problem is NP-hard to approximate within

$\frac{k}{2}-1+\frac{1}{2k}-\varepsilon $

. This hardness factor is off from the optimal by an additive constant of at most 1 for

k

 ≥ 4. Our reduction relies on the

Multi-Layered PCP

of [8] and uses a gadget – based on biased Long Codes – adapted from the LP integrality gap of [1]. The nature of our reduction requires the analysis of several Long Codes with different biases, for which we prove structural properties of the so called

cross-intersecting

collections of set families – variants of which have been studied in extremal set theory.

Phylogenetic tree reconstruction is a fundamental biological problem. Quartet amalgamation - combining a set of trees over four taxa into a tree over the full set - stands at the heart of many phylogenetic reconstruction methods. However, even reconstruction from a

consistent

set of quartet trees, i.e. all quartets agree with some tree, is NP-hard, and the best approximation ratio known is 1/3. For a dense input of Θ(

n

4

) quartets (not necessarily consistent), the problem has a polynomial time approximation scheme.

When the number of taxa grows, considering such dense inputs is impractical and some sampling approach is imperative. In this paper we show that if the number of quartets sampled is at least Θ(

n

2

log

n

), there is a randomized approximation scheme, that runs in linear time in the number of quartets. The previously known polynomial approximation scheme for that problem required a very dense sample of size Θ(

n

4

). We note that samples of size Θ(

n

2

log

n

) are sparse in the full quartet set.

We study the SIR epidemic model with infections carried by

k

particles making independent random walks on a random regular graph. We give a edge-weighted graph reduction of the dynamics of the process that allows us to apply standard results of Erdős–Renyi random graphs on the particle set. In particular, we show how the parameters of the model produce two phase transitions: In the subcritical regime,

O

(ln

k

) particles are infected. In the supercritical regime, for a constant

C

determined by the parameters of the model,

Ck

get infected with probability

C

, and

O

(ln

k

) get infected with probability (1 − 

C

). Finally, there is a regime in which all

k

particles are infected. Furthermore, the edge weights give information about when a particle becomes infected. We demonstrate how this can be exploited to determine the completion time of the process by applying a result of Janson on randomly edge weighted graphs.

We study quantum algorithms for testing bipartiteness and expansion of bounded-degree graphs. We give quantum algorithms that solve these problems in time

$\tilde O(N^{1/3})$

, beating the

$\Omega(\sqrt{N})$

classical lower bound. For testing expansion, we also prove an

$\tilde\Omega(N^{1/4})$

quantum query lower bound, thus ruling out the possibility of an exponential quantum speedup. Our quantum algorithms follow from a combination of classical property testing techniques due to Goldreich and Ron, derandomization, and the quantum algorithm for element distinctness. The quantum lower bound is obtained by the polynomial method, using novel algebraic techniques and combinatorial analysis to accommodate the graph structure.

Hardness amplification results show that for every function

f

there exists a function

Amp

(

f

) such that the following holds: if every circuit of size

s

computes

f

correctly on at most a 1 − 

δ

fraction of inputs, then every circuit of size

s

′ computes

Amp

(

f

) correctly on at most a 1/2 + 

ε

fraction of inputs. All hardness amplification results in the literature suffer from “size loss” meaning that

s

′ ≤ 

ε

·

s

. In this paper we show that proofs using “non-uniform reductions” must suffer from size loss. To the best of our knowledge, all proofs in the literature are by non-uniform reductions. Our result is the first lower bound that applies to non-uniform reductions that are

adaptive

.

A reduction is an oracle circuit

R

(·)

such that when given oracle access to any function

D

that computes

Amp

(

f

) correctly on a 1/2 + 

ε

fraction of inputs,

R

D

computes

f

correctly on a 1 − 

δ

fraction of inputs. A

non-uniform

reduction is allowed to also receive a short advice string

α

that may depend on both

f

and

D

in an arbitrary way. The well known connection between hardness amplification and list-decodable error-correcting codes implies that reductions showing hardness amplification cannot be uniform for

ε

 < 1/4. A reduction is

non-adaptive

if it makes non-adaptive queries to its oracle. Shaltiel and Viola (STOC 2008) showed lower bounds on the number of queries made by non-uniform reductions that are

non-adaptive

. We show that every non-uniform reduction must make at least Ω(1/

ε

) queries to its oracle (even if the reduction is

adaptive

). This implies that proofs by non-uniform reductions must suffer from size loss.

We also prove the same lower bounds on the number of queries of non-uniform and adaptive reductions that are allowed to rely on arbitrary specific properties of the function

f

. Previous limitations on reductions were proven for “function-generic” hardness amplification, in which the non-uniform reduction needs to work for every function

f

and therefore cannot rely on specific properties of the function.

Referring to the query complexity of testing graph properties in the adjacency matrix model, we advance the study of the class of properties that can be tested non-adaptively within complexity that is inversely proportional to the proximity parameter. Arguably, this is the lowest meaningful complexity class in this model, and we show that it contains a very natural class of graph properties. Specifically, for every fixed graph

H

, we consider the set of all graphs that are obtained by a (possibly unbalanced) blow-up of

H

. We show a non-adaptive tester of query complexity

$\widetilde{O}(1/\epsilon)$

that distinguishes graphs that are a blow-up of

H

from graphs that are

ε

-far from any such blow-up.

Affine-invariant properties are an abstract class of properties that generalize some central algebraic ones, such as linearity and low-degree-ness, that have been studied extensively in the context of property testing. Affine invariant properties consider functions mapping a big field

$\mathbb{F}_{q^n}$

to the subfield

$\mathbb{F}_q$

and include all properties that form an

$\mathbb{F}_q$

-vector space and are invariant under affine transformations of the domain. Almost all the known locally testable affine-invariant properties have so-called “single-orbit characterizations” — namely they are specified by a single local constraint on the property, and the “orbit” of this constraint, i.e., translations of this constraint induced by affine-invariance. Single-orbit characterizations by a local constraint are also known to imply local testability. In this work we show that properties with single-orbit characterizations are closed under “summation”. To complement this result, we also show that the property of being an

n

-variate low-degree polynomial over

$\mathbb{F}_q$

has a single-orbit characterization (even when the domain is viewed as

$\mathbb{F}_{q^n}$

and so has very few affine transformations). As a consequence we find that the sum of any sparse affine-invariant property (properties satisfied by

q

O

(

n

)

-functions) with the set of degree

d

multivariate polynomials over

$\mathbb{F}_q$

has a single-orbit characterization (and is hence locally testable) when

q

is prime. We conclude with some intriguing questions/conjectures attempting to classify all locally testable affine-invariant properties.

Despite its many applications, to program checking, probabilistically checkable proofs, locally testable and locally decodable codes, and cryptography, “algebraic property testing” is not well-understood. A significant obstacle to a better understanding, was a lack of a concrete definition that abstracted known testable algebraic properties and reflected their testability. This obstacle was removed by [Kaufman and Sudan, STOC 2008] who considered (linear) “affine-invariant properties”, i.e., properties that are closed under summation, and under affine transformations of the domain. Kaufman and Sudan showed that these two features (linearity of the property and its affine-invariance) play a central role in the testability of many known algebraic properties. However their work does not give a complete characterization of the testability of affine-invariant properties, and several technical obstacles need to be overcome to obtain such a characterization. Indeed, their work left open the tantalizing possibility that locally testable codes of rate dramatically better than that of the family of Reed-Muller codes (the most popular form of locally testable codes, which also happen to be affine-invariant) could be found by systematically exploring the space of affine-invariant properties.

In this work we rule out this possibility and show that general (linear) affine-invariant properties are contained in Reed-Muller codes that are testable with a slightly larger query complexity. A central impediment to proving such results was the limited understanding of the structural restrictions on affine-invariant properties imposed by the existence of local tests. We manage to overcome this limitation and present a clean restriction satisfied by affine-invariant properties that exhibit local tests. We do so by relating the problem to that of studying the set of solutions of a certain nice class of (uniform, homogenous, diagonal) systems of multivariate polynomial equations. Our main technical result completely characterizes (combinatorially) the set of zeroes, or algebraic set, of such systems.

An important problem in the implementation of Markov Chain Monte Carlo algorithms is to determine the convergence time, or the number of iterations before the chain is close to stationarity. For many Markov chains used in practice this time is not known. There does not seem to be a general technique for upper bounding the convergence time that gives sufficiently sharp (useful in practice) bounds in all cases of interest. Thus, practitioners like to carry out some form of statistical analysis in order to assess convergence. This has led to the development of a number of methods known as convergence diagnostics which attempt to diagnose whether the Markov chain is far from stationarity. We study the problem of testing convergence in the following settings and prove that the problem is hard computationally:

Given a Markov chain that mixes rapidly, it is hard for Statistical Zero Knowledge (SZK-hard) to distinguish whether starting from a given state, the chain is close to stationarity by time

t

or far from stationarity at time

ct

for a constant

c

. We show the problem is in AM ∩ coAM.

Given a Markov chain that mixes rapidly it is coNP-hard to distinguish from an arbitrary starting state whether it is close to stationarity by time

t

or far from stationarity at time

ct

for a constant

c

. The problem is in coAM.

It is PSPACE-complete to distinguish whether the Markov chain is close to stationarity by time

t

or still far from stationarity at time

ct

for

c

 ≥ 1.

We study the space complexity of randomized streaming algorithms that provide one-sided approximation guarantees; e.g., the algorithm always returns an overestimate of the function being computed, and with high probability, the estimate is not too far from the true answer. We also study algorithms which always provide underestimates.

We also give lower bounds for several one-sided estimators that match the deterministic space complexity, thus showing that to get a space-efficient solution, two-sided approximations are sometimes necessary. For some of these problems, including estimating the longest increasing sequence in a stream, and estimating the Earth Mover Distance, these are the first lower bounds for randomized algorithms of any kind.

We show that for several problems, including estimating the radius of the Minimum Enclosing Ball (MEB), one-sided estimation is possible. We provide a natural function for which the space for one-sided estimation is asymptotically less than the space required for deterministic algorithms, but more than what is required for general randomized algorithms.

What if an algorithm has a one-sided approximation from both sides? In this case, we show the problem has what we call a Las Vegas streaming algorithm. We show that even for two-pass algorithms, a quadratic improvement in space is possible and give a natural problem, counting non-isolated vertices in a graph, which achieves this separation.

For a variety of reasons, a number of recent works have studied the classic communication problem

index

, and its variant

augmented-index

, from a

tradeoff

perspective: how much communication can Alice (the player holding the

n

data bits) save if Bob (the player holding the index) communicates a nontrivial amount? Recently, Magniez et al. (STOC, 2010), Chakrabarti et al. (FOCS, 2010) and Jain and Nayak gave

information cost

tradeoffs for this problem, where the amount of communication is measured as the amount of information revealed by one player to the other. The latter two works showed that reducing Alice’s communication to sublinear requires at least a constant amount of communication from Bob.

Here, we show that the above result is just one point on a more general tradeoff curve. That is, we extend the earlier result to show that, for all

b

, either Bob reveals Ω(

b

) information to Alice, or else Alice reveals

n

/2

O

(

b

)

information to Bob. This tradeoff lower bound is easily seen to be everywhere-tight, by virtue of an easy two-round deterministic protocol. Our lower bound applies to constant-error randomized protocols, with information measured under an “easy” distribution on inputs.

In a well-known result Goldreich and Trevisan (2003) showed that every testable graph property has a “canonical” tester in which a set of vertices is selected at random and the edges queried are the complete graph over the selected vertices. We define a similar-in-spirit canonical form for Boolean function testing algorithms, and show that under some mild conditions property testers for Boolean functions can be transformed into this canonical form.

Our first main result shows, roughly speaking, that every “nice” family of Boolean functions that has low noise sensitivity and is testable by an “independent tester,” has a canonical testing algorithm. Our second main result is similar but holds instead for families of Boolean functions that are closed under ID-negative minors. Taken together, these two results cover almost all of the constant-query Boolean function testing algorithms that we know of in the literature, and show that all of these testing algorithms can be automatically converted into a canonical form.

We prove new lower bounds on the likely size of the maximum independent set in a random graph with a given constant average degree. Our method is a weighted version of the second moment method, where we give each independent set a weight based on the total degree of its vertices.

We consider the problem of extracting randomness from sources that are efficiently samplable, in the sense that each output bit of the sampler only depends on some small number

d

of the random input bits. As our main result, we construct a deterministic extractor that, given any

d

-local source with min-entropy

k

on

n

bits, extracts Ω(

k

2

/

nd

) bits that are

$2^{-n^{\Omega(1)}}$

-close to uniform, provided

d

 ≤ 

o

(log

n

) and

k

 ≥ 

n

2/3 + 

γ

(for arbitrarily small constants

γ

 > 0). Using our result, we also improve a result of Viola (FOCS 2010), who proved a 1/2 − 

O

(1/log

n

) statistical distance lower bound for

o

(log

n

)-local samplers trying to sample input-output pairs of an explicit boolean function, assuming the samplers use at most

n

 + 

n

1 − 

δ

random bits for some constant

δ

 > 0. Using a different function, we simultaneously improve the lower bound to

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

and eliminate the restriction on the number of random bits.

The Frieze-Kannan regularity lemma is a powerful tool in combinatorics. It has also found applications in the design of approximation algorithms and recently in the design of fast combinatorial algorithms for boolean matrix multiplication. The algorithmic applications of this lemma require one to efficiently construct a partition satisfying the conditions of the lemma.

Williams [24] recently asked if one can construct a partition satisfying the conditions of the Frieze-Kannan regularity lemma in deterministic sub-cubic time. We resolve this problem by designing an

$\tilde O(n^{\omega})$

time algorithm for constructing such a partition, where

ω

 < 2.376 is the exponent of fast matrix multiplication. The algorithm relies on a spectral characterization of vertex partitions satisfying the properties of the Frieze-Kannan regularity lemma.

A

q

-query locally testable code (LTC) is an error correcting code that can be tested by a randomized algorithm that reads at most

q

symbols from the given word. An important question is whether there exist LTCs that have the

c

3

property:

c

onstant rate,

c

onstant relative distance, and that can be tested with a

c

onstant number of queries. Such LTCs are sometimes referred to as “asymptotically good”.

We show that

dense

LTCs cannot be

c

3

. The

density

of a tester is roughly the average number of distinct local views in which a coordinate participates. An LTC is

dense

if it has a tester with density

ω

(1).

More precisely, we show that a 3-query locally testable code with a tester of density

ω

(1) cannot be

c

3

. Furthermore, we show that a

q

-locally testable code (

q

 > 3) with a tester of density

ω

(1)

n

q

 − 2

cannot be

c

3

. Our results hold when the tester has the following two properties:

(no weights:) Every

q

-tuple of queries occurs with the same probability.

(‘last-one-fixed’:) In every

q

-query ‘test’ of the tester, the value to any

q

 − 1 of the symbols determines the value of the last symbol. (Linear codes have constraints of this type).

We also show that several natural ways to quantitatively improve our results would already resolve the general

c

3

question, i.e. also for non-dense LTCs.

Probabilistically checkable debate systems (PCDSs) are debates between two competing provers, in which a polynomial-time verifier inspects a constant number of bits of the debate. It was shown by Condon, Feigenbaum, Lund, and Shor that every language in PSPACE has a PCDS in which the debate length is polynomially bounded. Using this result, they showed that the approximation versions of some natural PSPACE-complete problems are also PSPACE-complete.

We give an improved construction of these debates: for any language

L

that has an ordinary debate system definable by uniform circuits of size

s

 = 

s

(

n

), we give a PCDS for

L

whose debate is of total bitlength

$\widetilde{O}(s)$

, with a verifier that uses only

log

2

s

 + 

log

2

(

polylog

(

s

)) bits of randomness. This yields a much tighter connection between the time complexity of natural PSPACE-complete problems and the time complexity of their approximation versions.

Our key ingredient is a novel application of error-resilient communication protocols, as developed by Schulman; we use the more recent protocol of Braverman and Rao. We show that by requiring ordinary debates to be encoded in an error-resilient fashion, we can endow them with a useful “stability” property. Stable debates can then be transformed into PCDSs, by applying efficient PCPPs (as given by Dinur). Our main technical challenge in building stable debates is to enforce error-resilient encoding by the debaters. To achieve this, we show that there is a constant-round debate system, with a very efficient verifier, to debate whether a communication transcript follows the Braverman-Rao protocol.

Partitioning oracles were introduced by Hassidim

et al.

(FOCS 2009) as a generic tool for constant-time algorithms. For any

ε

 > 0, a partitioning oracle provides query access to a fixed partition of the input bounded-degree minor-free graph, in which every component has size poly(1/

ε

), and the number of edges removed is at most

εn

, where

n

is the number of vertices in the graph.

However, the oracle of Hassidim

et al.

makes an exponential number of queries to the input graph to answer every query about the partition. In this paper, we construct an efficient partitioning oracle for graphs with constant treewidth. The oracle makes only

O

(poly(1/

ε

)) queries to the input graph to answer each query about the partition.

Examples of bounded-treewidth graph classes include

k

-outerplanar graphs for fixed

k

, series-parallel graphs, cactus graphs, and pseudoforests. Our oracle yields poly(1/

ε

)-time property testing algorithms for membership in these classes of graphs. Another application of the oracle is a poly(1/

ε

)-time algorithm that approximates the maximum matching size, the minimum vertex cover size, and the minimum dominating set size up to an additive

εn

in graphs with bounded treewidth. Finally, the oracle can be used to test in poly(1/

ε

) time whether the input bounded-treewidth graph is

k

-colorable or perfect.

We consider

natural

graph property tests, which act entirely independently of the size of the graph being tested. We introduce the notion of properties being

inflatable

— closed under taking (balanced) blowups — and show that the query complexity of natural tests for a property is related to the degree to which it is approximately hereditary and inflatable. Specifically, we show that for properties which are almost hereditary and almost inflatable, any test can be made natural, with a polynomial increase in the number of queries. The naturalization can be considered as an extension of the canonicalization due to [15], so that natural canonical tests can be described as

strongly canonical

.

Using the technique for naturalization, we restore in part the claim in [15] regarding testing hereditary properties by ensuring that a small random subgraph itself satisfies the property. This allows us to generalize the triangle-freeness lower bound result of [5]: Any lower bound, not only the currently established quasi-polynomial one, on one-sided testing for triangle-freeness holds essentially for two-sided testing as well. We also explore the relations of the notion of inflatability and other already-studied features of properties and property tests, such as one-sidedness, heredity, and proximity-oblivion.

We give an algorithm that computes the final state of certain growth models without computing all intermediate states. Our technique is based on a “least action principle” which characterizes the odometer function of the growth process. Starting from an approximation for the odometer, we successively correct under- and overestimates and provably arrive at the correct final state. The degree of speedup depends on the accuracy of the initial guess.

Determining the size of the boundary fluctuations in growth models like internal diffusion-limited aggregation (IDLA) is a long-standing open problem in statistical physics. As an application of our method, we calculate the size of fluctuations over two orders of magnitude beyond previous simulations.

We study the computational complexity of approximately counting the number of independent sets of a graph with maximum degree Δ. More generally, for an input graph

G

 = (

V

,

E

) and an activity

λ

 > 0, we are interested in the quantity

Z

G

(

λ

) defined as the sum over independent sets

I

weighted as

w

(

I

) = 

λ

|

I

|

. In statistical physics,

Z

G

(

λ

) is the partition function for the hard-core model, which is an idealized model of a gas where the particles have non-negibile size. Recently, an interesting phase transition was shown to occur for the complexity of approximating the partition function. Weitz showed an FPAS for the partition function for any graph of maximum degree Δ when Δ is constant and

$\lambda<\lambda_c(\mathbb{T}_\Delta):=(\Delta-1)^{\Delta-1}/(\Delta-2)^\Delta$

. The quantity

$\lambda_c(\mathbb{T}_\Delta)$

is the critical point for the so-called uniqueness threshold on the infinite, regular tree of degree Δ. On the other side, Sly proved that there does not exist efficient (randomized) approximation algorithms for

$\lambda_c(\mathbb{T}_\Delta)<\lambda<\lambda_c(\mathbb{T}_\Delta)+\varepsilon(\Delta)$

, unless NP=RP, for some function

ε

(Δ) > 0. We remove the upper bound in the assumptions of Sly’s result for Δ ≠ 4,5, that is, we show that there does not exist efficient randomized approximation algorithms for all

$\lambda>\lambda_c(\mathbb{T}_\Delta)$

for Δ = 3 and Δ ≥ 6. Sly’s inapproximability result uses a clever reduction, combined with a second-moment analysis of Mossel, Weitz and Wormald which prove torpid mixing of the Glauber dynamics for sampling from the associated Gibbs distribution on almost every regular graph of degree Δ for the same range of

λ

as in Sly’s result. We extend Sly’s result by improving upon the technical work of Mossel et al., via a more detailed analysis of independent sets in random regular graphs.

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). Our focus is on the case that the property is characterized by a constant number of local conditions and a rich set of invariances.

We show that, in the aforementioned models of testing graph properties, characterization by such invariant local conditions is closely related to proximity oblivious testing (as defined by Goldreich and Ron, STOC’09). In contrast to this relation, we show that, in general, characterization by invariant local conditions is neither necessary nor sufficient for proximity oblivious testing. Furthermore, we show that easy testability is

not

guaranteed even when the property is characterized by local conditions that are invariant under a 1-transitive group of permutations.

The classical family of [

n

,

k

]

q

Reed-Solomon codes over a field

$\mathbb{F}_q$

consist of the evaluations of polynomials

$f \in \mathbb{F}_q[X]$

of degree < 

k

at

n

distinct field elements. In this work, we consider a closely related family of codes, called (order

m

)

derivative codes

and defined over fields of large characteristic, which consist of the evaluations of

f

as well as its first

m

 − 1 formal derivatives at

n

distinct field elements. For large enough

m

, we show that these codes can be list-decoded in polynomial time from an error fraction approaching 1 − 

R

, where

R

 = 

k

/(

nm

) is the rate of the code. This gives an alternate construction to folded Reed-Solomon codes for achieving the optimal trade-off between rate and list error-correction radius.

Our decoding algorithm is linear-algebraic, and involves solving a linear system to interpolate a multivariate polynomial, and then solving another structured linear system to retrieve the list of candidate polynomials

f

. The algorithm for derivative codes offers some advantages compared to a similar one for folded Reed-Solomon codes in terms of efficient unique decoding in the presence of side information.

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

${\mathcal O}(\lambda)$

, and negligible probability of decoding failure, for security parameter

λ

. Hemenway and Ostrovsky gave a construction of locally decodable codes in the public-key model with constant codeword expansion and locality

${\mathcal O}(\lambda^2)$

, but their construction had two major drawbacks. The keys in their scheme were proportional to

n

, the length of the message, and their schemes were based on the Φ-hiding assumption. Our keys are of length proportional to the security parameter instead of the message, and our construction relies only on the existence of IND-CPA secure encryption rather than on specific number-theoretic assumptions. Our scheme also decreases the locality from

${\mathcal O}(\lambda^2)$

to

${\mathcal O}(\lambda)$

. Our construction can be modified to give a generic transformation of any private-key locally decodable code to a public-key locally decodable code based only on the existence of an IND-CPA secure public-key encryption scheme.

Let

X

1

,

X

2

, …,

X

n

be a set of random variables. Suppose that in addition to the prior distributions of these random variables we are also given

linear constraints relating them

. We ask for necessary and sufficient conditions under which we can efficiently sample the constrained distributions, find constrained marginal distributions for each of the random variables, etc. We give a tight characterization of the conditions under which this is possible. The problem is motivated by a number of scenarios where we have separate probabilistic inferences in some domain, but domain knowledge allows us to relate these inferences. When the joint prior distribution is a product distribution, the linear constraints have to be carefully chosen and are crucial in creating the lower bound instances. No such constraints are necessary if arbitrary priors are allowed.

The Johnson-Lindenstrauss lemma is a fundamental result in probability with several applications in the design and analysis of algorithms. Constructions of linear embeddings satisfying the Johnson-Lindenstrauss property necessarily involve randomness and much attention has been given to obtain explicit constructions minimizing the number of random bits used. In this work we give explicit constructions with an almost optimal use of randomness: For 0 < 

ε

,

δ

 < 1/2, we obtain explicit generators

G

:{0,1}

r

 → ℝ

s

×

d

for

s

 = 

O

(log(1/

δ

)/

ε

2

) such that for all

d

-dimensional vectors

w

of norm one,

$$ \Pr_{y \in_u \{0,1\}^r}[\, |\|G(y)w\|^2 -1| > \epsilon\,] \leq \delta,$$

with seed-length

$r = O\left(\log d + \log (1/\delta) \cdot \log\left(\frac{\log(1/\delta)}{\epsilon}\right)\right)$

. In particular, for

$\delta = 1/\mathop{{\rm poly}}(d)$

and fixed

ε

 > 0, we obtain seed-length

O

((log

d

) (loglog

d

)). Previous constructions required Ω(log

2

d

) random bits to obtain polynomially small error.

We also give a new elementary proof of the optimality of the JL lemma showing a lower bound of Ω(log(1/

δ

)/

ε

2

) on the embedding dimension. Previously, Jayram and Woodruff [10] used communication complexity techniques to show a similar bound.

Average-case circuit lower bounds are one of the hardest problems tackled by computational complexity, and are essentially only known for bounded-depth circits with AND,OR,NOT gates (i.e.

$\mbox{\rm AC}^0$

). Faced with this adversity, one line of research has been to gradually augment

$\mbox{\rm AC}^0$

circuits with a small number of more general gates. Most results to date give lower bounds for quasi-polynomial size

$\mbox{\rm AC}^0$

circuits augmented by a poly-logarithmic number of gates, and the correlation bounds obtained are inverse quasi-polynomial.

We continue this line of research, but restrict our attention to polynomial size

$\mbox{\rm AC}^0$

circuits. Surprisingly, we show that this restriction allows us to prove much stronger results: we can augment the

$\mbox{\rm AC}^0$

circuit with

n

1 − 

o

(1)

many gates, and still obtain inverse exponential correlation bounds. Explicitly,

1

Poly-size

$\mbox{\rm AC}^0$

circuits with

n

1 − 

o

(1)

arbitrary symmetric gates have exponentially small correlation with an explicitly given function.

2

Poly-size

$\mbox{\rm AC}^0$

circuits with

n

1/2 − 

o

(1)

threshold gates have exponentially small correlation with the same explicit function.

3

Poly-size

$\mbox{\rm AC}^0$

circuits with

n

1 − 

o

(1)

counting gates modulo

s

have exponentially small correlation with the sum of the bits modulo

q

, where

s

,

q

are co-prime.

Our proof techniques combine the meet-in-the-middle approach for circuit lower bounds with restrictions (due to Ajtai) that are tailored to polynomial-size circuits.

Colloids are binary mixtures of molecules with one type of molecule suspended in another. It is believed that at low density typical configurations will be well-mixed throughout, while at high density they will separate into clusters. We characterize the high and low density phases for a general family of discrete

interfering binary mixtures

by showing that they exhibit a “clustering property” at high density and not at low density. The clustering property states that there will be a region that has very high area to perimeter ratio and very high density of one type of molecule. A special case is mixtures of squares and diamonds on ℤ

2

which corresond to the Ising model at fixed magnetization.

The

Total Influence

(

Average Sensitivity

) of a discrete function is one of its fundamental measures. We study the problem of approximating the total influence of a monotone Boolean function

$f: \{0,1\}^n \longrightarrow \{0,1\}$

, which we denote by

I

[

f

]. We present a randomized algorithm that approximates the influence of such functions to within a multiplicative factor of (1,±

ε

) by performing

$O\left(\frac{\sqrt{n}\log n}{I[f]}{\rm poly}(1/\epsilon) \right) $

queries. We also prove a lower bound of

$\Omega\left(\frac{\sqrt{n}}{\log n \cdot I[f]}\right)$

on the query complexity of any constant-factor approximation algorithm for this problem (which holds for

I

[

f

] = Ω(1)), hence showing that our algorithm is almost optimal in terms of its dependence on

n

. For general functions we give a lower bound of

$\Omega\left(\frac{n}{I[f]}\right)$

, which matches the complexity of a simple sampling algorithm.

In this work we consider the problem of approximating the number of relevant variables in a function given query access to the function. Since obtaining a multiplicative factor approximation is hard in general, we consider several relaxations of the problem. In particular, we consider a relaxation of the property testing variant of the problem and we consider relaxations in which we have a promise that the function belongs to a certain family of functions (e.g., linear functions). In the former relaxation the task is to distinguish between the case that the number of relevant variables is at most

k

, and the case in which it is far from any function in which the number of relevant variable is more than (1 + 

γ

)

k

for a parameter

γ

. We give both upper bounds and almost matching lower bounds for the relaxations we study.

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 most a

δ

fraction of inputs, then some

f

′ related to

f

has no size

s

′ errorless circuit that outputs “don’t know” on at most a 1 − 

ε

fraction of inputs. Thus the hardness is “amplified” from

δ

to 1 − 

ε

. Unfortunately, this amplification comes at the cost of a loss in circuit size. This is because such results are proven by reductions which show that any size

s

′ errorless circuit for

f

′ that outputs “don’t know” on at most a 1 − 

ε

fraction of inputs could be used to construct a size

s

errorless circuit for

f

that outputs “don’t know” on at most a

δ

fraction of inputs. If the reduction makes

q

queries to the hypothesized errorless circuit for

f

′, then plugging in a size

s

′ circuit yields a circuit of size ≥ 

qs

′, and thus we must have

s

′ ≤ 

s

/

q

. Hence it is desirable to keep the query complexity to a minimum. The first results on errorless hardness amplification were obtained by Bogdanov and Safra (FOCS 2007). They achieved query complexity

$O\big((\frac{1}{\delta}\log\frac{1}{\epsilon})^2\cdot\frac{1}{\epsilon}\log\frac{1}{\delta}\big)$

when

f

′ is the XOR of several independent copies of

f

. We improve the query complexity (and hence the loss in circuit size) to

$O\big(\frac{1}{\epsilon}\log\frac{1}{\delta}\big)$

, which is optimal up to constant factors for nonadaptive black-box errorless hardness amplification. Bogdanov and Safra also proved a result that allows for errorless hardness amplification within NP. They achieved query complexity

$O\big(k^3\cdot\frac{1}{\epsilon^2}\log\frac{1}{\delta}\big)$

when

f

′ consists of any monotone function applied to the outputs of

k

independent copies of

f

, provided the monotone function satisfies a certain combinatorial property parameterized by

δ

and

ε

. We improve the query complexity to

$O\big(\frac{k}{t}\cdot\frac{1}{\epsilon}\log\frac{1}{\delta}\big)$

, where

t

 ≥ 1 is a certain parameter of the monotone function.