Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Random walk:
TR04-016 | 3rd March 2004
Michael Alekhnovich, Eli Ben-Sasson

Linear Upper Bounds for Random Walk on Small Density Random 3CNFs

We analyze the efficiency of the random walk algorithm on random 3CNF instances, and prove em linear upper bounds on the running time
of this algorithm for small clause density, less than 1.63. Our upper bound matches the observed running time to within a multiplicative factor. This is the ... more >>>

TR15-111 | 8th July 2015
Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky

Low Distortion Embedding from Edit to Hamming Distance using Coupling

Revisions: 1

The Hamming and the edit metrics are two common notions of measuring distances between pairs of strings $x,y$ lying in the Boolean hypercube. The edit distance between $x$ and $y$ is defined as the minimum number of character insertion, deletion, and bit flips needed for converting $x$ into $y$. ... more >>>

TR18-155 | 8th September 2018
Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal

Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates

A recent work of Chattopadhyay et al. (CCC 2018) introduced a new framework for the design of pseudorandom generators for Boolean functions. It works under the assumption that the Fourier tails of the Boolean functions are uniformly bounded for all levels by an exponential function. In this work, we design ... more >>>

ISSN 1433-8092 | Imprint