2 citations · 3 across the 16 of their papers we have counts for
8 papers · 1 filter
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…
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…
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…
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 .…