We define a hierarchy of complexity classes that lie between P and RP, yielding a new way of quantifying partial progress towards the derandomization of RP. A standard approach in derandomization is to reduce the number of random bits an algorithm uses. We instead focus on a model of computation ... more >>>

We propose a model called priority branching trees (pBT ) for backtracking and dynamic
programming algorithms. Our model generalizes both the priority model of Borodin, Nielson
and Rackoff, as well as a simple dynamic programming model due to Woeginger, and hence
spans a wide spectrum of algorithms. After witnessing the ... more >>>

We present a Fourier-analytic approach to list-decoding Reed-Muller codes over arbitrary finite fields. We prove that the list-decoding radius for quadratic polynomials equals $1 - 2/q$ over any field $F_q$ where $q > 2$. This confirms a conjecture due to Gopalan, Klivans and Zuckerman for degree $2$. Previously, tight bounds ... more >>>