All reports by Author Siddharth Bhandari:

__
TR19-164
| 6th November 2019
__

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

__
TR18-207
| 5th December 2018
__

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

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