2 citations · 3 across the 16 of their papers we have counts for
Showing 2018Show all
3 papers · 1 filter
cs.CC2018★ 1 cited
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…
cs.CC2018
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…
cs.CC2018
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…