Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim

The efficient construction of Hitting Sets for non trivial classes

of boolean functions is a fundamental problem in the theory

of derandomization. Our paper presents a new method to efficiently

construct Hitting Sets for the class of systems of boolean linear

functions. Systems of boolean linear functions ...
more >>>

Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan

We consider the task of locally correcting, and locally list-correcting, multivariate linear functions over the domain $\{0,1\}^n$ over arbitrary fields and more generally Abelian groups. Such functions form error-correcting codes of relative distance $1/2$ and we give local-correction algorithms correcting up to nearly $1/4$-fraction errors making $\widetilde{\mathcal{O}}(\log n)$ queries. This ... more >>>