Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SIDDHARTH BHANDARI:
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

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


TR18-207 | 5th December 2018
Siddharth Bhandari, Prahladh Harsha, Tulasimohan Molli, Srikanth Srinivasan

On the Probabilistic Degree of OR over the Reals

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




ISSN 1433-8092 | Imprint