All reports by Author Siddharth Bhandari:

__
TR22-075
| 21st May 2022
__

Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, Srikanth Srinivasan#### Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes

Revisions: 1

__
TR21-163
| 19th November 2021
__

Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, A. Shankar#### Algorithmizing the Multiplicity Schwartz-Zippel Lemma

Revisions: 1

__
TR19-164
| 6th November 2019
__

Siddharth Bhandari, Sayantan Chakraborty#### Improved bounds for perfect sampling of $k$-colorings in graphs

Revisions: 1

__
TR18-207
| 5th December 2018
__

Siddharth Bhandari, Prahladh Harsha, Tulasimohan Molli, Srikanth Srinivasan#### On the Probabilistic Degree of OR over the Reals

Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, Srikanth Srinivasan

We study the following natural question on random sets of points in $\mathbb{F}_2^m$:

Given a random set of $k$ points $Z=\{z_1, z_2, \dots, z_k\} \subseteq \mathbb{F}_2^m$, what is the dimension of the space of degree at most $r$ multilinear polynomials that vanish on all points in $Z$?

We ... more >>>

Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, A. Shankar

The multiplicity Schwartz-Zippel lemma asserts that over a field, a low-degree polynomial cannot vanish with high multiplicity very often on a sufficiently large product set. Since its discovery in a work of Dvir, Kopparty, Saraf and Sudan [DKSS13], the lemma has found nu- merous applications in both math and computer ... more >>>

Siddharth Bhandari, Sayantan Chakraborty

We present a randomized algorithm that takes as input an undirected $n$-vertex graph $G$ with maximum degree $\Delta$ and an integer $k > 3\Delta$, and returns a random proper $k$-coloring of $G$. The

distribution of the coloring is perfectly uniform over the set of all proper $k$-colorings; ...
more >>>

Siddharth Bhandari, Prahladh Harsha, Tulasimohan Molli, Srikanth Srinivasan

We study the probabilistic degree over reals of the OR function on $n$ variables. For an error parameter $\epsilon$ in (0,1/3), the $\epsilon$-error probabilistic degree of any Boolean function $f$ over reals is the smallest non-negative integer $d$ such that the following holds: there exists a distribution $D$ of polynomials ... more >>>