All reports by Author Xiaoming Sun:

__
TR18-087
| 20th April 2018
__

Kun He, Qian Li, Xiaoming Sun, Jiapeng Zhang#### Quantum Lov{\'a}sz Local Lemma: Shearer's Bound is Tight

__
TR14-152
| 13th November 2014
__

Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo#### Tighter Relations Between Sensitivity and Other Complexity Measures

__
TR14-061
| 21st April 2014
__

Raghav Kulkarni, Youming Qiao, Xiaoming Sun#### Any Monotone Property of 3-uniform Hypergraphs is Weakly Evasive

__
TR13-110
| 12th August 2013
__

Xiaoming Sun, Marcos Villagra#### Exponential Quantum-Classical Gaps in Multiparty Nondeterministic Communication Complexity

__
TR11-116
| 17th August 2011
__

Andris Ambainis, Xiaoming Sun#### New separation between $s(f)$ and $bs(f)$

Kun He, Qian Li, Xiaoming Sun, Jiapeng Zhang

Lov{\'a}sz Local Lemma (LLL) is a very powerful tool in combinatorics and probability theory to show the possibility of avoiding all ``bad" events under some ``weakly dependent" condition. Over the last decades, the algorithmic aspect of LLL has also attracted lots of attention in theoretical computer science \cite{moser2010constructive, kolipaka2011moser, harvey2015algorithmic}. ... more >>>

Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo

Sensitivity conjecture is a longstanding and fundamental open problem in the area of complexity measures of Boolean functions and decision tree complexity. The conjecture postulates that the maximum sensitivity of a Boolean function is polynomially related to other major complexity measures. Despite much attention to the problem and major advances ... more >>>

Raghav Kulkarni, Youming Qiao, Xiaoming Sun

For a Boolean function $f,$ let $D(f)$ denote its deterministic decision tree complexity, i.e., minimum number of (adaptive) queries required in worst case in order to determine $f.$ In a classic paper,

Rivest and Vuillemin \cite{rv} show that any non-constant monotone property $\mathcal{P} : \{0, 1\}^{n \choose 2} \to ...
more >>>

Xiaoming Sun, Marcos Villagra

There are three different types of nondeterminism in quantum communication: i) $\nqp$-communication, ii) $\qma$-communication, and iii) $\qcma$-communication. In this \redout{paper} we show that multiparty $\nqp$-communication can be exponentially stronger than $\qcma$-communication. This also implies an exponential separation with respect to classical multiparty nondeterministic communication complexity. We argue that there exists ... more >>>

Andris Ambainis, Xiaoming Sun

In this note we give a new separation between sensitivity and block sensitivity of Boolean functions: $bs(f)=\frac{2}{3}s(f)^2-\frac{1}{3}s(f)$.

more >>>