Elizaveta Okol'nishnikova

The method of obtaining lower bounds on the complexity

of Boolean functions for nondeterministic branching programs

is proposed.

A nonlinear lower bound on the complexity of characteristic

functions of Reed--Muller codes for nondeterministic

branching programs is obtained.

Venkatesan Guruswami, Chaoping Xing

We give a length-efficient puncturing of Reed-Muller codes which preserves its distance properties. Formally, for the Reed-Muller code encoding $n$-variate degree-$d$ polynomials over ${\mathbb F}_q$ with $q \ge \Omega(d/\delta)$, we present an explicit (multi)-set $S \subseteq {\mathbb F}_q^n$ of size $N=\mathrm{poly}(n^d/\delta)$ such that every nonzero polynomial vanishes on at most ... more >>>

Ofer Grossman, Dana Moshkovitz

We present techniques for decreasing the error probability of randomized algorithms and for converting randomized algorithms to deterministic (non-uniform) algorithms. Unlike most existing techniques that involve repetition of the randomized algorithm, and hence a slowdown, our techniques produce algorithms with a similar run-time to the original randomized algorithms.

The ... more >>>