All reports by Author David Xiao:

__
TR13-015
| 18th January 2013
__

Iordanis Kerenidis, Mathieu Laurière, David Xiao#### New lower bounds for privacy in communication protocols

__
TR12-052
| 27th April 2012
__

Mohammad Mahmoody, David Xiao#### Languages with Efficient Zero-Knowledge PCPs are in SZK

__
TR12-038
| 6th April 2012
__

Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jérémie Roland, David Xiao#### Lower bounds on information complexity via zero-communication protocols and applications

__
TR10-192
| 8th December 2010
__

Frederic Magniez, Ashwin Nayak, Miklos Santha, David Xiao#### Improved bounds for the randomized decision tree complexity of recursive majority

Revisions: 1

__
TR10-001
| 30th December 2009
__

Iftach Haitner, Mohammad Mahmoody, David Xiao#### A New Sampling Protocol and Applications to Basing Cryptographic Primitives on the Hardness of $NP$

__
TR09-139
| 17th December 2009
__

Mohammad Mahmoody, David Xiao#### On the Power of Randomized Reductions and the Checkability of SAT

Revisions: 3

__
TR09-006
| 19th January 2009
__

David Xiao#### On basing ZK != BPP on the hardness of PAC learning

__
TR06-105
| 23rd August 2006
__

Avi Wigderson, David Xiao#### Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications

__
TR05-107
| 28th September 2005
__

Avi Wigderson, David Xiao#### A Randomness-Efficient Sampler for Matrix-valued Functions and Applications

Revisions: 1

Iordanis Kerenidis, Mathieu Laurière, David Xiao

Communication complexity is a central model of computation introduced by Yao in 1979, where

two players, Alice and Bob, receive inputs x and y respectively and want to compute $f(x; y)$ for some fixed

function f with the least amount of communication. Recently people have revisited the question of the ...
more >>>

Mohammad Mahmoody, David Xiao

A Zero-Knowledge PCP (ZK-PCP) is a randomized PCP such that the view of any (perhaps cheating) efficient verifier can be efficiently simulated up to small statistical distance. Kilian, Petrank, and Tardos (STOC '97) constructed ZK-PCPs for all languages in $NEXP$. Ishai, Mahmoody, and Sahai (TCC '12), motivated by cryptographic applications, ... more >>>

Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jérémie Roland, David Xiao

We show that almost all known lower bound methods for communication complexity are also lower bounds for the information complexity. In particular, we define a relaxed version of the partition bound of Jain and Klauck and prove that it lower bounds the information complexity of any function. Our relaxed partition ... more >>>

Frederic Magniez, Ashwin Nayak, Miklos Santha, David Xiao

We consider the randomized decision tree complexity of the recursive 3-majority function. For evaluating a height $h$ formulae, we prove a lower bound for the $\delta$-two-sided-error randomized decision tree complexity of $(1-2\delta)(5/2)^h$, improving the lower bound of $(1-2\delta)(7/3)^h$ given by Jayram et al. (STOC '03). We also state a conjecture ... more >>>

Iftach Haitner, Mohammad Mahmoody, David Xiao

We investigate the question of what languages can be decided efficiently with the help of a recursive collision-finding oracle. Such an oracle can be used to break collision-resistant hash functions or, more generally, statistically hiding commitments. The oracle we consider, $Sam_d$ where $d$ is the recursion depth, is based on ... more >>>

Mohammad Mahmoody, David Xiao

The closure of complexity classes is a elicate question and the answer varies depending on the type of reduction considered. The closure of most classes under many-to-one (Karp) reductions is clear, but the question becomes complicated when oracle (Cook) reductions are allowed, and even more so when the oracle reductions ... more >>>

David Xiao

Learning is a central task in computer science, and there are various

formalisms for capturing the notion. One important model studied in

computational learning theory is the PAC model of Valiant (CACM 1984).

On the other hand, in cryptography the notion of ``learning nothing''

is often modelled by the simulation ...
more >>>

Avi Wigderson, David Xiao

Ahlswede and Winter introduced a Chernoff bound for matrix-valued random variables, which is a non-trivial generalization of the usual Chernoff bound for real-valued random variables. We present an efficient derandomization of their bound using the method of pessimistic estimators (see Raghavan). As a consequence, we derandomize a construction of Alon ... more >>>

Avi Wigderson, David Xiao

In this paper we give a randomness-efficient sampler for matrix-valued functions. Specifically, we show that a random walk on an expander approximates the recent Chernoff-like bound for matrix-valued functions of Ahlswede and Winter, in a manner which depends optimally on the spectral gap. The proof uses perturbation theory, and is ... more >>>