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
  1. The generating matrix defining a linear code for min-distance decoding (or a basis of a lattice for the Closest Vector Problem);
  2. The encryption-key corresponding to a ciphertext encrypted under a PKE scheme;
  3. The combinatorial structure (e.g., graph) of combinatorial optimization problem with weights;
  4. 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.