Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao

We prove new cell-probe lower bounds for data structures that maintain a subset of $\{1,2,...,n\}$, and compute the median of the set. The data structure is said to handle insertions non-adaptively if the locations of memory accessed depend only on the element being inserted, and not on the contents of ... more >>>

Tom Gur, Oded Lachish

A locally decodable code (LDC) C:{0,1}^k -> {0,1}^n is an error correcting code wherein individual bits of the message can be recovered by only querying a few bits of a noisy codeword. LDCs found a myriad of applications both in theory and in practice, ranging from probabilistically checkable proofs to ... more >>>

Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang

A sunflower with $r$ petals is a collection of $r$ sets so that the

intersection of each pair is equal to the intersection of all. Erd\H{o}s and Rado proved the sunflower lemma: for any fixed $r$, any family of sets of size $w$, with at least about $w^w$ sets, must ...
more >>>