2 citations · 3 across the 16 of their papers we have counts for
16 papers
A Top-Down Depth-Four Circuit Lower Bound for Majority
Hao Wu, Yaqiao Li
We present a top-down depth-four circuit lower bound for Majority function by extending recent work of Göös, Riazanov, Sofronova, and Sokolov (FOCS 2023), who gave a top-down proof…
Undecidability of Polynomial Inequalities in Subset Densities and Additive Energies
Yaqiao Li
Many results in extremal graph theory can be formulated as certain polynomial inequalities in graph homomorphism densities. Answering fundamental questions raised by Lov{á}sz, Szeg…
Diversity-seeking swap games in networks
Yaqiao Li, Lata Narayanan, Jaroslav Opatrny +1
Schelling games use a game-theoretic approach to study the phenomenon of residential segregation as originally modeled by Schelling. Inspired by the recent increase in the number o…
Lifting query complexity to time-space complexity for two-way finite automata
Shenggen Zheng, Yaqiao Li, Minghua Pan +2
Time-space tradeoff has been studied in a variety of models, such as Turing machines, branching programs, and finite automata, etc. While communication complexity as a technique ha…
Online Vector Bin Packing and Hypergraph Coloring Illuminated: Simpler Proofs and New Connections
Yaqiao Li, Denis Pankratov
This paper studies the online vector bin packing (OVBP) problem and the related problem of online hypergraph coloring (OHC). Firstly, we use a double counting argument to prove an…
Perspective on complexity measures targetting read-once branching programs
Yaqiao Li, Pierre McKenzie
A model of computation for which reasonable yet still incomplete lower bounds are known is the read-once branching program. Here variants of complexity measures successful in the s…
Online Coloring and a New Type of Adversary for Online Graph Problems
Yaqiao Li, Vishnu V. Narayan, Denis Pankratov
We introduce a new type of adversary for online graph problems. The new adversary is parameterized by a single integer , which upper bounds the number of connected components th…
Chang's lemma via Pinsker's inequality
Lianna Hambardzumyan, Yaqiao Li
Extending the idea in [Impagliazzo, R., Moore, C. and Russell, A., An entropic proof of Chang's inequality. SIAM Journal on Discrete Mathematics, 28(1), pp.173-176.] we give a shor…
Human Motion Prediction via Pattern Completion in Latent Representation Space
Yi Tian Xu, Yaqiao Li, David Meger
Inspired by ideas in cognitive science, we propose a novel and general approach to solve human motion understanding via pattern completion on a learned latent representation space.…
Conflict complexity is lower bounded by block sensitivity
Yaqiao Li
We show conflict complexity of every total Boolean function, recently introduced in [Swagato Sanyal. A composition theorem via conict complexity. arXiv preprint arXiv:1801.03285, 2…
Trading information complexity for error II: the case of a large error and external information complexity
Yaqiao Li
Two problems are studied in this paper. (1) How much external or internal information cost is required to compute a Boolean-valued function with an error at most for a smal…
A note on the tight example in On the randomised query complexity of composition
Yaqiao Li
We make two observations regarding a recent tight example for a composition theorem for randomized query complexity: (1) it implies general randomized query-to-communication liftin…
Information complexity of the AND function in the two-Party, and multiparty settings
Yuval Filmus, Hamed Hatami, Yaqiao Li +1
In a recent breakthrough paper [M. Braverman, A. Garg, D. Pankratov, and O. Weinstein, From information to exact communication, STOC'13] Braverman et al. developed a local characte…
Trading information complexity for error
Yuval Dagan, Yuval Filmus, Hamed Hatami +1
We consider the standard two-party communication model. The central problem studied in this article is how much one can save in information complexity by allowing an error of .…
A characterization of functions with vanishing averages over products of disjoint sets
Hamed Hatami, Pooya Hatami, Yaqiao Li
Given , we characterize all integrable functions satisfying for any collection of disjoint…
The winning property of mixed badly approximable numbers
Yaqiao Li
For any pair of real numbers with and , we prove that the set of -adic mixed -badly approximable numbers $\bad_p(i, j)$ is 1/2-winning in the sen…