Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Jiapeng Zhang:

TR20-048 | 16th April 2020
Shachar Lovett, Raghu Meka, Jiapeng Zhang

Improved lifting theorems via robust sunflowers

Lifting theorems are a generic way to lift lower bounds in query complexity to lower bounds in communication complexity, with applications in diverse areas, such as combinatorial optimization, proof complexity, game theory. Lifting theorems rely on a gadget, where smaller gadgets give stronger lower bounds. However, existing proof techniques are ... more >>>

TR19-137 | 24th September 2019
Shachar Lovett, Kewen Wu, Jiapeng Zhang

Decision list compression by mild random restrictions

Revisions: 1

A decision list is an ordered list of rules. Each rule is specified by a term, which is a conjunction of literals, and a value. Given an input, the output of a decision list is the value corresponding to the first rule whole term is satisfied by the input. Decision ... more >>>

TR19-110 | 23rd August 2019
Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang

Improved bounds for the sunflower lemma

A sunflower with $r$ petals is a collection of $r$ sets so that the
intersection of each pair is equal to the intersection of all. Erd\H{o}s and Rado proved the sunflower lemma: for any fixed $r$, any family of sets of size $w$, with at least about $w^w$ sets, must ... more >>>

TR19-028 | 1st March 2019
Shachar Lovett, Noam Solomon, Jiapeng Zhang

From DNF compression to sunflower theorems via regularity

Revisions: 1

The sunflower conjecture is one of the most well-known open problems in combinatorics. It has several applications in theoretical computer science, one of which is DNF compression, due to Gopalan, Meka and Reingold [Computational Complexity 2013]. In this paper, we show that improved bounds for DNF compression imply improved bounds ... more >>>

TR18-190 | 5th November 2018
Shachar Lovett, Jiapeng Zhang

DNF sparsification beyond sunflowers

There are two natural complexity measures associated with DNFs: their size, which is the number of clauses; and their width, which is the maximal number of variables in a clause. It is a folklore result that DNFs of small size can be approximated by DNFs of small width (logarithmic in ... more >>>

TR18-119 | 21st June 2018
YiHsiu Chen, Mika G\"o{\"o}s, Salil Vadhan, Jiapeng Zhang

A Tight Lower Bound for Entropy Flattening

Revisions: 1

We study \emph{entropy flattening}: Given a circuit $\mathcal{C}_X$ implicitly describing an $n$-bit source $X$ (namely, $X$ is the output of $\mathcal{C}_X$ on a uniform random input), construct another circuit $\mathcal{C}_Y$ describing a source $Y$ such that (1) source $Y$ is nearly \emph{flat} (uniform on its support), and (2) the Shannon ... more >>>

TR18-087 | 20th April 2018
Kun He, Qian Li, Xiaoming Sun, Jiapeng Zhang

Quantum Lov{\'a}sz Local Lemma: Shearer's Bound is Tight

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

TR18-082 | 21st April 2018
Xin Li, Shachar Lovett, Jiapeng Zhang

Sunflowers and Quasi-sunflowers from Randomness Extractors

The Erdos-Rado sunflower theorem (Journal of Lond. Math. Soc. 1960) is a fundamental result in combinatorics, and the corresponding sunflower conjecture is a central open problem. Motivated by applications in complexity theory, Rossman (FOCS 2010) extended the result to quasi-sunflowers, where similar conjectures emerge about the optimal parameters for which ... more >>>

TR17-085 | 4th May 2017
Daniel Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang

Active classification with comparison queries

We study an extension of active learning in which the learning algorithm may ask the annotator to compare the distances of two examples from the boundary of their label-class. For example, in a recommendation system application (say for restaurants), the annotator may be asked whether she liked or disliked a ... more >>>

TR16-161 | 26th October 2016
Shachar Lovett, Jiapeng Zhang

Robust sensitivity

Revisions: 1

The sensitivity conjecture is one of the central open problems in boolean complexity. A recent work of Gopalan et al. [CCC 2016] conjectured a robust analog of the sensitivity conjecture, which relates the decay of the Fourier mass of a boolean function to moments of its sensitivity. We prove this ... more >>>

TR16-118 | 31st July 2016
Shachar Lovett, Jiapeng Zhang

On the impossibility of entropy reversal, and its application to zero-knowledge proofs

Zero knowledge proof systems have been widely studied in cryptography. In the statistical setting, two classes of proof systems studied are Statistical Zero Knowledge (SZK) and Non-Interactive Statistical Zero Knowledge (NISZK), where the difference is that in NISZK only very limited communication is allowed between the verifier and the prover. ... more >>>

TR16-021 | 11th February 2016
Shachar Lovett, Jiapeng Zhang

Noisy Population Recovery from Unknown Noise

The noisy population recovery problem is a statistical inference problem, which is a special case of the problem of learning mixtures of product distributions. Given an unknown distribution on $n$-bit strings with support of size $k$, and given access only to noisy samples from it, where each bit is flipped ... more >>>

TR15-180 | 4th November 2015
Bo Tang, Jiapeng Zhang

Barriers to Black-Box Constructions of Traitor Tracing Systems

Reducibility between different cryptographic primitives is a fundamental problem in modern cryptography. As one of the primitives, traitor tracing systems help content distributors recover the identities of users that collaborated in the pirate construction by tracing pirate decryption boxes. We present the first negative result on designing efficient traitor tracing ... more >>>

TR14-123 | 7th October 2014
Shachar Lovett, Jiapeng Zhang

Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions

The noisy population recovery problem is a basic statistical inference problem. Given an unknown distribution in $\{0,1\}^n$ with support of size $k$,
and given access only to noisy samples from it, where each bit is flipped independently with probability $1/2-\eps$,
estimate the original probability up to an additive error of ... more >>>

TR11-038 | 10th March 2011
Jiapeng Zhang

On the query complexity for Showing Dense Model

A theorem of Green, Tao, and Ziegler can be stated as follows: if $R$ is a pseudorandom distribution, and $D$ is a dense distribution of $R,$ then $D$ can be modeled as a distribution $M$ which is dense in uniform distribution such that $D$ and $M$ are indistinguishable. The reduction ... more >>>

ISSN 1433-8092 | Imprint