Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with memory checking:
TR06-034 | 9th March 2006
Moni Naor, Guy Rothblum

The Complexity of Online Memory Checking

Suppose you want to store a large file on a remote and unreliable server. You would like to verify that your file has not been corrupted, so you store a small private (randomized)``fingerprint'' of the file on your own computer. This is the setting for the well-studied authentication problem, and ... more >>>

TR10-076 | 18th April 2010
Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor

Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition

Revisions: 1

This paper makes three main contributions to the theory of communication complexity and stream computation. First, we present new bounds on the information complexity of AUGMENTED-INDEX. In contrast to analogous results for INDEX by Jain, Radhakrishnan and Sen [J. ACM, 2009], we have to overcome the significant technical challenge that ... more >>>

TR24-014 | 28th January 2024
Elette Boyle, Ilan Komargodski, Neekon Vafa

Memory Checking Requires Logarithmic Overhead

We study the complexity of memory checkers with computational security and prove the first general tight lower bound.

Memory checkers, first introduced over 30 years ago by Blum, Evans, Gemmel, Kannan, and Naor (FOCS '91, Algorithmica '94), allow a user to store and maintain a large memory on a remote ... more >>>

ISSN 1433-8092 | Imprint