Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR12-052 | 27th April 2012
Mohammad Mahmoody, David Xiao

Languages with Efficient Zero-Knowledge PCPs are in SZK

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

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

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

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

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

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$

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

TR09-139 | 17th December 2009
Mohammad Mahmoody, David Xiao

On the Power of Randomized Reductions and the Checkability of SAT

Revisions: 3

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

TR09-006 | 19th January 2009
David Xiao

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

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

TR06-105 | 23rd August 2006
Avi Wigderson, David Xiao

Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications

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

TR05-107 | 28th September 2005
Avi Wigderson, David Xiao

A Randomness-Efficient Sampler for Matrix-valued Functions and Applications

Revisions: 1

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

ISSN 1433-8092 | Imprint