Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian

Recently, Dvir, Golovnev, and Weinstein have shown that sufficiently strong lower bounds for linear data structures would imply new bounds for rigid matrices. However, their result utilizes an algorithm that requires an $NP$ oracle, and hence, the rigid matrices are not explicit. In this work, we derive an equivalence between ... more >>>

Giuseppe Persiano, Kevin Yeo

In this paper, we study the static cell probe complexity of non-adaptive data structures that maintain a subset of $n$ points from a universe consisting of $m=n^{1+\Omega(1)}$ points. A data structure is defined to be non-adaptive when the memory locations that are chosen to be accessed during a query depend ... more >>>

Young Kun Ko

The main motivation for studying linear data structures and circuits is the intuition that non-linear advice cannot help in computing a linear operator. Jukna and Schnitger formalized this as a conjecture which states that all circuits computing a linear operator can be ``linearized," with only a constant size blow-up. We ... more >>>