Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > DATA STRUCTURES:
Reports tagged with data structures:
TR95-062 | 14th December 1995
Amir M. Ben-Amram, Zvi Galil

#### On Data Structure Tradeoffs and an Application to Union-Find

Consider a problem involving updates and queries of a data structure.
Assume that there exists a family of algorithms which exhibit a
tradeoff between query and update time. We demonstrate a general
technique of constructing from such a family
a single algorithm with best amortized time. We indicate some ... more >>>

TR98-028 | 28th May 1998
Paul Beame, Faith Fich

#### On Searching Sorted Lists: A Near-Optimal Lower Bound

We obtain improved lower bounds for a class of static and dynamic
data structure problems that includes several problems of searching
sorted lists as special cases.

These lower bounds nearly match the upper bounds given by recent
striking improvements in searching algorithms given by Fredman and
Willard's ... more >>>

TR09-079 | 21st September 2009
Victor Chen, Elena Grigorescu, Ronald de Wolf

#### Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation

Revisions: 1

We construct efficient data structures that are resilient against a constant fraction of adversarial noise. Our model requires that the decoder answers most queries correctly with high probability and for the remaining queries, the
decoder with high probability either answers correctly or declares don't know.'' Furthermore, if there is no ... more >>>

TR10-115 | 17th July 2010
Shachar Lovett, Emanuele Viola

#### Bounded-depth circuits cannot sample good codes

We study a variant of the classical circuit-lower-bound problems: proving lower bounds for sampling distributions given random bits. We prove a lower bound of $1-1/n^{\Omega(1)}$ on the statistical distance between (i) the output distribution of any small constant-depth (a.k.a.~$\mathrm{AC}^0$) circuit $f : \{0,1\}^{\mathrm{poly}(n)} \to \{0,1\}^n$, and (ii) the uniform distribution ... more >>>

TR15-156 | 21st September 2015
Tim Roughgarden

#### Communication Complexity (for Algorithm Designers)

This document collects the lecture notes from my course Communication Complexity (for Algorithm Designers),'' taught at
Stanford in the winter quarter of 2015. The two primary goals of the course are:

1. Learn several canonical problems that have proved the most useful for proving lower bounds (Disjointness, Index, Gap-Hamming, etc.). ... more >>>

TR16-167 | 1st November 2016
Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao

#### New Randomized Data Structure Lower Bounds for Dynamic Graph Connectivity

Revisions: 1

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

TR17-047 | 10th March 2017
Kasper Green Larsen, Omri Weinstein, Huacheng Yu

#### Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds

This paper proves the first super-logarithmic lower bounds on the cell probe complexity of dynamic \emph{boolean} (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds.

We introduce a new method for proving dynamic cell probe lower bounds and use it to prove a $\tilde{\Omega}(\log^{1.5} ... more >>> TR17-170 | 6th November 2017 Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay #### Simulation Beats Richness: New Data-Structure Lower Bounds We develop a technique for proving lower bounds in the setting of asymmetric communication, a model that was introduced in the famous works of Miltersen (STOC'94) and Miltersen, Nisan, Safra and Wigderson (STOC'95). At the core of our technique is a novel simulation theorem: Alice gets a$p \times n$... more >>> TR18-188 | 7th November 2018 Zeev Dvir, Alexander Golovnev, Omri Weinstein #### Static Data Structure Lower Bounds Imply Rigidity Revisions: 2 We show that static data structure lower bounds in the group (linear) model imply semi-explicit lower bounds on matrix rigidity. In particular, we prove that an explicit lower bound of$t \geq \omega(\log^2 n)$on the cell-probe complexity of linear data structures in the group model, even against arbitrarily small ... more >>> TR19-143 | 25th October 2019 Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian #### Equivalence of Systematic Linear Data Structures and Matrix Rigidity 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 >>> TR20-057 | 20th April 2020 Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein #### Polynomial Data Structure Lower Bounds in the Group Model Proving super-logarithmic data structure lower bounds in the static \emph{group model} has been a fundamental challenge in computational geometry since the early 80's. We prove a polynomial ($n^{\Omega(1)}$) lower bound for an explicit range counting problem of$n^3$convex polygons in$\R^2$(each with$n^{\tilde{O}(1)}\$ facets/semialgebraic-complexity), against linear storage arithmetic ... more >>>

ISSN 1433-8092 | Imprint