Hasan Abasi, Nader Bshouty

We develop a new algebraic technique that gives a simple randomized algorithm for the simple $k$-path problem with the same complexity $O^*(1.657^k)$ as in [A. Bj\"orklund. Determinant Sums for Undirected Hamiltonicity. FOCS 2010, pp. 173--182, (2010). A. Bj\"orklund, T. Husfeldt, P. Kaski, M. Koivisto. Narrow sieves for parameterized paths and ... more >>>

Anurag Anshu, Dmytro Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal

Let the randomized query complexity of a relation for error probability $\epsilon$ be denoted by $\R_\epsilon(\cdot)$. We prove that for any relation $f \subseteq \{0,1\}^n \times \mathcal{R}$ and Boolean function $g:\{0,1\}^m \rightarrow \{0,1\}$, $\R_{1/3}(f\circ g^n) = \Omega(\R_{4/9}(f)\cdot\R_{1/2-1/n^4}(g))$, where $f \circ g^n$ is the relation obtained by composing $f$ and $g$. ... more >>>

Dominik Scheder

We study the success probability of the PPSZ algorithm on $(d,k)$-CSP formulas. We greatly simplify the analysis of Hertli, Hurbain, Millius, Moser, Szedlak, and myself for the notoriously difficult case that the input formula has more than one satisfying assignment.

more >>>Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

A Chor--Goldreich (CG) source [CG88] is a sequence of random variables $X = X_1 \circ \ldots \circ X_t$, each $X_i \sim \{0,1 \{^d$, such that each $X_i$ has $\delta d$ min-entropy for some constant $\delta > 0$, even conditioned on any fixing of $X_1 \circ \ldots \circ X_{i-1}$. We typically ... more >>>