NDLI: Anti-persistence: history independent data structures

Please wait, while we are loading the content...

Clustering to minimize the sum of cluster diameters

Approximating min-sum k-clustering in metric spaces

Local search heuristic for k-median and facility location problems

Profit-earning facility location

One-dimensional quantum walks

Quantum walks on graphs

Quantum algorithms for solvable groups

Quantum mechanical algorithms for the nonabelian hidden subgroup problem

Minimax parametric optimization problems and multi-dimensional parametric searching

Algorithms for minimizing weighted flow time

Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines

Stackelberg scheduling strategies

Quantum computers that can be simulated classically in polynomial time

Interaction in quantum communication and the complexity of set disjointness

A new protocol and lower bounds for quantum coin flipping

Loss-less condensers, unbalanced expanders, and extractors

Conditions on input vectors for consensus solvability in asynchronous distributed systems

Spatial gossip and resource location protocols

(1 + εΒ)-spanner constructions for general graphs

Approximate distance oracles

Extractor codes

Excellent codes from modular curves

Sparse polynomial approximation in finite fields

Randomness efficient identity testing of multivariate polynomials

Fully-dynamic min-cut

Computing crossing numbers in quadratic time

Euler paths in series parallel graphs

Decidability of string graphs

Learning mixtures of arbitrary gaussians

Learning DNF in time

Sampling algorithms: lower bounds and applications

Testing metric properties

Testing of matrix properties

Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time

One line and ε

A tight bound for the complexity of voroni diagrams under polyhedral convex distance functions in 3D

Lower bounds for intersection searching and fractional cascading in higher dimension

Sharp threshold and scaling window for the integer partitioning problem

A sharp threshold in proof complexity

Regular resolution lower bounds for the weak pigeonhole principle

The complexity of analytic tableaux

Applications of approximation algorithms to cooperative games

Approximation algorithms for constrained for constrained node weighted steiner tree problems

A constant factor approximation for the single sink edge installation problems

Provisioning a virtual private network: a network design problem for multicommodity flow

Explicit lower bound of 4.5n - o(n) for boolena circuits

Lower bounds for matrix product, in bounded depth circuits with arbitrary gates

A read-once branching program lower bound of $Ω(2^{n/4})$ for integer multiplication using universal hashing

On the cell probe complexity of membership and perfect hashing

On the integrality ratio of semidefinite relaxations of MAX CUT

Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming

Non-approximability results for optimization problems on bounded degree instances

Colouring graphs when the number of colours is nearly the maximum degree

Data-streams and histograms

Optimal static range reporting in one dimension

Biased dictionaries with fast insert/deletes

Anti-persistence: history independent data structures

Dynamic TCP acknowledgement and other stories about e/(e-1)

The price of selfish routing

Buffer overflow management in QoS switches

Almost optimal permutation routing on hypercubes

Online server allocation in a server farm via benefit task systems

Private approximation of NP-hard functions

Concurrent and resettable zero-knowledge in poly-loalgorithm rounds

Black-box concurrent zero-knowledge requires \tilde {Ω} (logn) rounds

The round complexity of verifiable secret sharing and secure multicast

Communication preserving protocols for secure function evaluation

Some perspectives on computational complexity

A sieve algorithm for the shortest lattice vector problem

Fast computation of low rank matrix approximations

Spectral analysis of data

Optimal outlier removal in high-dimensional

Estimating true evolutionary distances between genomes

On optimal slicing of parallel programs

When is the evaluation of conjunctive queries tractable?

The complexity of maximal constraint languages

Quantitative solution of omega-regular games380872

Distribution functions of probabilistic automata

Compatible sequences and a slow Winkler percolation

Edge isoperimetry and rapid mixing on matroids and geometric Markov chains

A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries

Computing with continuous-time Liapunov systems

Complex tilings

Running time and program size for self-assembled squares

Algorithms, games, and the internet

Automata, circuits and hybrids: facets of continuous time

Anti-persistence: history independent data structures

Content Provider	ACM Digital Library
Author	Naor, Moni Teague, Vanessa
Abstract	Many data structures give away much more information than they were intended to. Whenever privacy is important, we need to be concerned that it might be possible to infer information from the memory representation of a data structure that is not available through its “legitimate” interface. Word processors that quietly maintain old versions of a document are merely the most egregious example of a general problem.We deal with data structures whose current memory representation does not reveal their history. We focus on dictionaries, where this means revealing nothing about the order of insertions or deletions. Our first algorithm is a hash table based on open addressing, allowing O(1) insertion and search. We also present a history independent dynamic perfect hash table that uses space linear in the number of elements inserted and has expected amortized insertion and deletion time O(1). To solve the dynamic perfect hashing problem we devise a general scheme for history independent memory allocation. For fixed-size records this is quite efficient, with insertion and deletion both linear in the size of the record. Our variable-size record scheme is efficient enough for dynamic perfect hashing but not for general use. The main open problem we leave is whether it is possible to implement a variable-size record scheme with low overhead.
Starting Page	492
Ending Page	501
Page Count	10
File Format	PDF
ISBN	1581133499
DOI	10.1145/380752.380844
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2001-07-06
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Privacy Algorithms Data structures History independence Anti-persistence Hash table Security
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in