6 papers
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…