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