All reports by Author Jiapeng Zhang:

__
TR24-070
| 10th April 2024
__

Xinyu Mao, Guangxu Yang, Jiapeng Zhang#### Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing

__
TR24-067
| 10th April 2024
__

Mi-Ying Huang, Xinyu Mao, Guangxu Yang, Jiapeng Zhang#### Breaking Square-Root Loss Barriers via Min-Entropy

__
TR23-164
| 5th November 2023
__

Shuo Wang, Guangxu Yang, Jiapeng Zhang#### Communication Complexity of Set-Intersection Problems and Its Applications

__
TR23-159
| 31st October 2023
__

Guangxu Yang, Jiapeng Zhang#### Communication Lower Bounds for Collision Problems via Density Increment Arguments

__
TR23-137
| 10th September 2023
__

Mi-Ying Huang, Xinyu Mao, Guangxu Yang, Jiapeng Zhang#### Communication Lower Bounds of Key-Agreement Protocols via Density Increment Arguments

__
TR23-003
| 11th January 2023
__

Shachar Lovett, Jiapeng Zhang#### Streaming Lower Bounds and Asymmetric Set-Disjointness

__
TR22-107
| 20th July 2022
__

Shachar Lovett, Jiapeng Zhang#### Fractional certificates for bounded functions

__
TR22-049
| 4th April 2022
__

Xinyu Mao, Noam Mazor, Jiapeng Zhang#### Non-Adaptive Universal One-Way Hash Functions from Arbitrary One-Way Functions

Revisions: 2

__
TR22-019
| 17th February 2022
__

Guangxu Yang, Jiapeng Zhang#### Simulation Methods in Communication Lower Bounds, Revisited

__
TR20-048
| 16th April 2020
__

Shachar Lovett, Raghu Meka, Jiapeng Zhang#### Improved lifting theorems via robust sunflowers

__
TR19-137
| 24th September 2019
__

Shachar Lovett, Kewen Wu, Jiapeng Zhang#### Decision list compression by mild random restrictions

Revisions: 1

__
TR19-110
| 23rd August 2019
__

Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang#### Improved bounds for the sunflower lemma

__
TR19-028
| 1st March 2019
__

Shachar Lovett, Noam Solomon, Jiapeng Zhang#### From DNF compression to sunflower theorems via regularity

Revisions: 1

__
TR18-190
| 5th November 2018
__

Shachar Lovett, Jiapeng Zhang#### DNF sparsification beyond sunflowers

__
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

__
TR18-087
| 20th April 2018
__

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

__
TR18-082
| 21st April 2018
__

Xin Li, Shachar Lovett, Jiapeng Zhang#### Sunflowers and Quasi-sunflowers from Randomness Extractors

__
TR17-085
| 4th May 2017
__

Daniel Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang#### Active classification with comparison queries

__
TR16-161
| 26th October 2016
__

Shachar Lovett, Jiapeng Zhang#### Robust sensitivity

Revisions: 1

__
TR16-118
| 31st July 2016
__

Shachar Lovett, Jiapeng Zhang#### On the impossibility of entropy reversal, and its application to zero-knowledge proofs

__
TR16-021
| 11th February 2016
__

Shachar Lovett, Jiapeng Zhang#### Noisy Population Recovery from Unknown Noise

__
TR15-180
| 4th November 2015
__

Bo Tang, Jiapeng Zhang#### Barriers to Black-Box Constructions of Traitor Tracing Systems

__
TR14-123
| 7th October 2014
__

Shachar Lovett, Jiapeng Zhang#### Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions

__
TR11-038
| 10th March 2011
__

Jiapeng Zhang#### On the query complexity for Showing Dense Model

Xinyu Mao, Guangxu Yang, Jiapeng Zhang

The notion of query-to-communication lifting theorems is a generic framework to convert query lower bounds into two-party communication lower bounds. Though this framework is very generic and beautiful, it has some inherent limitations such as it only applies to lifted functions. In order to address this issue, we propose gadgetless ... more >>>

Mi-Ying Huang, Xinyu Mao, Guangxu Yang, Jiapeng Zhang

Information complexity is one of the most powerful tools to prove information-theoretical lower bounds, with broad applications in communication complexity and streaming algorithms. A core notion in information complexity analysis is the Shannon entropy. Though it has some convenient properties, such as chain rules, Shannon entropy still has inherent limitations. ... more >>>

Shuo Wang, Guangxu Yang, Jiapeng Zhang

Set-disjointness is one of the most fundamental and widely studied problems in the area of communication complexity. In this problem, each party $i$ receives a set $S_i\subseteq [N]$. The goal is to determine whether $\bigcap S_i$ is empty via communication between players. The decision version simply asks if the common ... more >>>

Guangxu Yang, Jiapeng Zhang

Collision problems are important problems in complexity theory and cryptography with diverse applications. Previous fruitful works have mainly focused on query models. Driven by various applications, several works by Bauer, Farshim and Mazaheri (CRYPTO 2018), Itsykson and Riazanov (CCC 2021), Göös and Jain (RANDOM 2022) independently proposed the communication version ... more >>>

Mi-Ying Huang, Xinyu Mao, Guangxu Yang, Jiapeng Zhang

Constructing key-agreement protocols in the random oracle model (ROM) is a viable method to assess the feasibility of developing public-key cryptography within Minicrypt. Unfortunately, as shown by Impagliazzo and Rudich (STOC 1989) and Barak and Mahmoody (Crypto 2009), such protocols can only guarantee limited security: any $\ell$-query protocol can be ... more >>>

Shachar Lovett, Jiapeng Zhang

Frequency estimation in data streams is one of the classical problems in streaming algorithms. Following much research, there are now almost matching upper and lower bounds for the trade-off needed between the number of samples and the space complexity of the algorithm, when the data streams are adversarial. However, in ... more >>>

Shachar Lovett, Jiapeng Zhang

A folklore conjecture in quantum computing is that the acceptance probability of a quantum query algorithm can be approximated by a classical decision tree, with only a polynomial increase in the number of queries. Motivated by this conjecture, Aaronson and Ambainis (Theory of Computing, 2014) conjectured that this should hold ... more >>>

Xinyu Mao, Noam Mazor, Jiapeng Zhang

Two of the most useful cryptographic primitives that can be constructed from one-way functions are pseudorandom generators (PRGs) and universal one-way hash functions (UOWHFs). The three major efficiency measures of these primitives are: seed length, number of calls to the one-way function, and adaptivity of these calls. Although a long ... more >>>

Guangxu Yang, Jiapeng Zhang

The notion of lifting theorems is a generic method to lift hardness of one-party functions to two-party lower bounds in communication model. It has many applications in different areas such as proof complexity, game theory, combinatorial optimization. Among many lifting results, a central idea is called Raz-McKenize simulation (FOCS 1997). ... more >>>

Shachar Lovett, Raghu Meka, Jiapeng Zhang

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

Shachar Lovett, Kewen Wu, Jiapeng Zhang

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

Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang

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

Shachar Lovett, Noam Solomon, Jiapeng Zhang

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

Shachar Lovett, Jiapeng Zhang

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

YiHsiu Chen, Mika G\"o{\"o}s, Salil Vadhan, Jiapeng Zhang

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

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

Xin Li, Shachar Lovett, Jiapeng Zhang

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

Daniel Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang

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

Shachar Lovett, Jiapeng Zhang

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

Shachar Lovett, Jiapeng Zhang

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

Shachar Lovett, Jiapeng Zhang

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

Bo Tang, Jiapeng Zhang

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

Shachar Lovett, Jiapeng Zhang

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

Jiapeng Zhang

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