One Approx'14 invited talk and eight Random'14 un-invited talks
(Credit for the expression "un-invited talks" is due to L. Levin)
The proceedings volume of APPROX/RANDOM'14 appears as volume 28
of LIPIcs and is available
HERE.
Uri Feige (invited talk): Preprocessing NP-Hard Problems.
Can NP-Hard problems be solved efficiently given partial information
that is obtained by a free preprocessing of a "preview" or "skeleton"
of the instance? A meaningful phrasing of this question is rather
problem dependent and refers to a natural notion of a skeleton.
Natural examples include
- The generating matrix defining a linear code for min-distance
decoding (or a basis of a lattice for the Closest Vector Problem);
- The encryption-key corresponding to a ciphertext encrypted
under a PKE scheme;
- The combinatorial structure (e.g., graph) of combinatorial
optimization problem with weights;
- A "factor graph" of a CSP instance that specifies for each clause
the set of variables that are associated with the clause.
The aforementioned question may refer to decision problems,
optimization problems, or approximation problems.
Note that the preprocessing can always generate a non-uniform advice string.
The initial results obtained in this study (conducted with Shlomo Jozeph)
include an efficient sqrt(n)-factor approximation for weighted MIS
that uses an NP-hard preprocessing of the underlying graph
(as opposed to the NP-hardness of obtaining almost linear approximation
factor without such a preprocessing) as well as a hardness result
for obtaining some $n^Omega(1)$ factor approximation given a preprocessing.
A related paper of Shlomo Jozeph (in these proceedings) refers to CSP.
It shows that every NP-hard Boolean constraint satisfaction problem
(except for an easy to characterize set of natural exceptions)
has "universal factor graphs": A sequence of graphs, one for each size, such that the problem restricted to instances that have a factor graph from
this family cannot be solved in polynomial time, unless NP is contained in P/poly.
Improved Lower Bounds for Testing Triangle-freeness in Boolean Functions
via Fast Matrix Multiplication by Hu Fu and Robert Kleinberg
What is actually shown is that "Unique Solution Puzzles",
which were previously used to introduce record-holding
upper bounds on the exponent of Matrix Multiplication,
yield improved lower bounds on the query complexity
of testing "triangle-freeness of Boolean functions".
Hence, results on the very same notion (of Unique Solution Puzzles)
imply both upper bound on matrix multiplication
and lower bounds on the complexity of testing
(a natural affine-invariant property that is not linear).
Space Pseudorandom Generators by Communication Complexity Lower Bounds
by Anat Ganor and Ran Raz
The starting point of this work is the observation that the BNS reduction
of (Number Of Forehead) multi-party communication complexity to
the (violation of the) pseudorandomness of a certain generator
with respect to log-space is a major overkill in the sense that
this reduction supports a much more restricted model
of commutation complexity, which in turn admits better lower bounds.
The bottom-line of this work is an alternative construction of a PRG
with respect to log-space that meets Nisan's parameters
(i.e., seed length log-square).
Communication Complexity of Set-Disjointness for All Probabilities
Mika Goos and Thomas Watson
The issue at hand is communication complexity protocols with very
low acceptance probability. That is, each YES-instance is accepted
with probability at least $a(n)$, whereas each NO-instance is accepted
with probability at most $b(n)The Information Complexity of Hamming Distance
by Eric Blais, Joshua Brody and Badih Ghazi
Using the Information Complexity measure and techniques,
it is shown that the randomized communication complexity
of GapHamming is $\Omega(\min(\log{n\choose d}, d\log(1/\eps))$.
This implies that $\eps$-testing $k$-linearity (and $k$-junta)
is $\Omega(k\cdot\min(log n,\log(1/\eps))$,
which improves over the known $\Omega(k)$ bound.
This seems to support the conjecture that the
actual bound is $\Omega(\log{n\choose k})$.
Sampling a Uniform Solution of a Quadratic Equation Modulo a Prime Power
by Chandan Dubey and Thomas Holenstein
Unfortunately, the talk and paper do not discuss the failure of simple
attempts to extend the naive algorithm for the case of a prime moduli.
Ditto regarding discussing the issues that lead them to their current approach.
But the result seems interesting and leads to finding such solutions
modulo any composite number, with given factorization, via the CRT.
Recall that knowledge of factorization is required in some cases
(cf., Rabin'79) but not in others (cf. Pollard and Schnorr).
That is, given an $n$-variate quadratic equation over the ring $Z_m$,
the problem is to generate a uniformly distributed solution.
The paper deals with the case of $m=p^k$, where $p$ is a prime,
and neglects discussing the case of $k=1$.
Two Sides of the Coin Problem
by Gil Cohen, Anat Ganor and Ran Raz
This work considers the question of whether weak computational devices,
which cannot compute majority, can distinguish small deviations of
an input sequence from the uniform distribution, where each bit in the sequence
has a polylogarithmically small bias (of $b = 1/poly(\log n)$).
The first result refers to small width read-once Branching Programs
and Santha-Vazirani sources, whereas the second result refers to AC0
and independent tosses of the same biased coin.
Indeed, a begging question concerns AC0 and Santha-Vazirani sources.
Pseudorandomness and Fourier Growth Bounds for Width 3 Branching Programs
by Thomas Steinke, Salil Vadhan and Andrew Wan
It is known
(see Sec 1.3.2 in Yoav Tzur's thesis)
that Nisan's generator is not resilent to reordering of its output bits.
This work presents the first PRG with polylogarithmic seed
that is resilient to read-once branching programs (ROBP)
of width three that read the input in arbitrary order
(i.e., the order is fixed after the PRG is fixed).
(Note that Tzur's distinguisher uses constant-width ROBP,
but this constant is larger than three.)
Local Algorithms for Sparse Spanning Graphs
by Reut Levi, Dana Ron and Ronitt Rubinfeld
Given oracle access to a graph $G$,
one seeks to provide an oracle access
to a $\Pi$-substructure $S$ of $G$
(where the predetermined $\Pi$ specifies
the type of desired substructure).
Here, one seeks a spanning subgraph of $G$
with a small number of edges
(e.g., $1+\eps$ times the spanning tree).
The paper provides a lower bound of $\Omega(\sqrt(n))$,
also when the graph is a strong expander,
and provides an almost matching upper bound in this case.
On the other hand, when the graph is extremely non-expanding
(i.e., hyper-finite), a different algorithm establishes
an upper bound that is independent of the size of the graph.
A begging question is whether an algorithm of sublinear complexity
exists in the general case.
Back to
list of Oded's choices.