Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with randomized algorithm:
TR13-012 | 16th January 2013
Hasan Abasi, Nader Bshouty

A Simple Algorithm for Undirected Hamiltonicity

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

TR17-107 | 1st June 2017
Anurag Anshu, Dmytro Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal

A Composition Theorem for Randomized Query complexity

Revisions: 1

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

TR18-179 | 31st October 2018
Dominik Scheder

PPSZ on CSP Instances with Multiple Solutions

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

TR22-103 | 15th July 2022
Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

Almost Chor--Goldreich Sources and Adversarial Random Walks

Revisions: 1

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

ISSN 1433-8092 | Imprint