All reports by Author Sivaramakrishnan Natarajan Ramamoorthy:

__
TR19-143
| 25th October 2019
__

Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian#### Equivalence of Systematic Linear Data Structures and Matrix Rigidity

__
TR19-026
| 28th February 2019
__

Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff#### Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits

Revisions: 1

__
TR17-040
| 4th March 2017
__

Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao#### Non-Adaptive Data Structure Lower Bounds for Median and Predecessor Search from Sunflowers

Revisions: 2

__
TR16-167
| 1st November 2016
__

Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao#### New Randomized Data Structure Lower Bounds for Dynamic Graph Connectivity

Revisions: 1

__
TR15-055
| 13th April 2015
__

Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao#### How to Compress Asymmetric Communication

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 >>>

Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff

There are various notions of balancing set families that appear in combinatorics and computer science. For example, a family of proper non-empty subsets $S_1,\ldots,S_k \subset [n]$ is balancing if for every subset $X \subset \{1,2,\ldots,n\}$ of size $n/2$, there is an $i \in [k]$ so that $|S_i \cap X| = ... more >>>

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 >>>

Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao

The problem of dynamic connectivity in graphs has been extensively studied in the cell probe model. The task is to design a data structure that supports addition of edges and checks connectivity between arbitrary pair of vertices. Let $w, t_q, t_u$ denote the cell width, expected query time and worst ... more >>>

Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao

We study the relationship between communication and information in 2-party communication protocols when the information is asymmetric. If $I^A$ denotes the number of bits of information revealed by the first party, $I^B$ denotes the information revealed by the second party, and $C$ is the number of bits of communication in ... more >>>