2 papers
cs.DS2023
Cell-Probe Lower Bound for Accessible Interval Graphs
Sankardeep Chakraborty, Christian Engels, Seungbum Jo +1
We spot a hole in the area of succinct data structures for graph classes from a universe of size at most . Very often, the input graph is labeled by the user in an arbitrary a…
cs.DS2021
Lower Bounds for Sparse Oblivious Subspace Embeddings
Yi Li, Mingmou Liu
An oblivious subspace embedding (OSE), characterized by parameters , is a random matrix such that for any -dimensional subspace $T\subse…