Michal Parnas, Dana Ron, Alex Samorodnitsky

We consider the problem of determining whether a given

function f : {0,1}^n -> {0,1} belongs to a certain class

of Boolean functions F or whether it is far from the class.

More precisely, given query access to the function f and given

a distance parameter epsilon, we would ...
more >>>

Philippe Moser

We strengthen an earlier notion of

resource-bounded Baire's categories, and define

resource bounded Baire's categories on small complexity classes such as P, QP, SUBEXP

and on probabilistic complexity classes such as BPP.

We give an alternative characterization of meager sets via resource-bounded

Banach Mazur games.

We show that the class ...
more >>>

Michael Alekhnovich, Eli Ben-Sasson

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

Beatrice List, Markus Maucher, Uwe Schöning, Rainer Schuler

The worst-case complexity of an implementation of Quicksort depends

on the random number generator that is used to select the pivot

elements. In this paper we estimate the expected number of

comparisons of Quicksort as a function in the entropy of the random

source. We give upper and lower bounds ...
more >>>

Nir Ailon, Bernard Chazelle

In general property testing, we are given oracle access to a function $f$, and we wish to randomly test if the function satisfies a given property $P$, or it is $\epsilon$-far from having that property. In a more general setting, the domain on which the function is defined is equipped ... more >>>

Tobias Riege, Jörg Rothe

NP-complete problems cannot have efficient algorithms unless P = NP. Due to their importance in practice, however, it is useful to improve the known exponential-time algorithms for NP-complete problems. We survey some of the recent results on such improved exponential-time algorithms for the NP-complete problems satisfiability, graph colorability, and the ... more >>>

Luis Rademacher, Santosh Vempala

How much can randomness help computation? Motivated by this general question and by volume computation, one of the few instances where randomness provably helps, we analyze a notion of dispersion and connect it to asymptotic convex geometry. We obtain a nearly quadratic lower bound on the complexity of randomized volume ... more >>>

Jeffrey C. Jackson, Homin Lee, Rocco Servedio, Andrew Wan

We give an algorithm that with high probability properly learns random monotone t(n)-term

DNF under the uniform distribution on the Boolean cube {0, 1}^n. For any polynomially bounded function t(n) <= poly(n) the algorithm runs in time poly(n, 1/eps) and with high probability outputs an eps accurate monotone DNF ...
more >>>

Dmitry Itsykson

We study class AvgBPP that consists of distributional problems that can be solved in average polynomial time (in terms of Levin's average-case complexity) by randomized algorithms with bounded error. We prove that there exists a distributional problem that is complete for AvgBPP under polynomial-time samplable distributions. Since we use deterministic ... more >>>

Oded Goldreich

The aim of this article is to introduce the reader to the study

of testing graph properties, while focusing on the main models

and issues involved. No attempt is made to provide a

comprehensive survey of this study, and specific results

are often mentioned merely as illustrations of general ...
more >>>

Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel

The area of derandomization attempts to provide efficient deterministic simulations of randomized algorithms in various algorithmic settings. Goldreich and Wigderson introduced a notion of "typically-correct" deterministic simulations, which are allowed to err on few inputs. In this paper we further the study of typically-correct derandomization in two ways.

First, we ... more >>>

eran gat , shafi goldwasser

In this paper we introduce a new type of probabilistic search algorithm, which we call the

{\it Bellagio} algorithm: a probabilistic algorithm which is guaranteed to run in expected polynomial time,

and to produce a correct and {\it unique} solution with high probability.

We argue the applicability of such algorithms ...
more >>>

Peyman Afshani, Manindra Agrawal, Doerr Benjamin, Winzen Carola, Kasper Green Larsen, Kurt Mehlhorn

We study the $\leadingones$ game, a Mastermind-type guessing game first

regarded as a test case in the complexity theory of randomized search

heuristics. The first player, Carole, secretly chooses a string $z \in \{0,1\}^n$ and a

permutation $\pi$ of $[n]$.

The goal of the second player, Paul, is to ...
more >>>

Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs

In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized

query complexity for a total boolean function is given by the function $f$ on $n=2^k$ bits defined by a complete binary tree

of NAND gates of depth $k$, which achieves $R_0(f) = O(D(f)^{0.7537\ldots})$. ...
more >>>

Dmytro Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs

Let $f:\{0,1\}^n \rightarrow \{0,1\}$ be a Boolean function. The certificate complexity $C(f)$ is a complexity measure that is quadratically tight for the zero-error randomized query complexity $R_0(f)$: $C(f) \leq R_0(f) \leq C(f)^2$. In this paper we study a new complexity measure that we call expectational certificate complexity $EC(f)$, which is ... more >>>

Dominik Scheder

PPSZ, for long time the fastest known algorithm for k-SAT, works by going through the variables of the input formula in random order; each variable is then set randomly to 0 or 1, unless the correct value can be inferred by an efficiently implementable rule (like small-width resolution; or being ... more >>>

Zhenjian Lu, Igor Carboni Oliveira, Marius Zimand

The classical coding theorem in Kolmogorov complexity states that if an $n$-bit string $x$ is sampled with probability $\delta$ by an algorithm with prefix-free domain then K$(x) \leq \log(1/\delta) + O(1)$. In a recent work, Lu and Oliveira [LO21] established an unconditional time-bounded version of this result, by showing that ... more >>>