The Library
Derandomization of cell sampling
Tools
Golonev, Alexander, Gur, Tom and Shinkar, Igor (2023) Derandomization of cell sampling. In: SIAM Symposium on Simplicity in Algorithms (SOSA23), Florence, Italy, 23-25 Jan 2023. Published in: Proceedings of the SIAM Symposium on Simplicity in Algorithms (SOSA23) (In Press)
|
PDF
WRAP-Derandomization-of-cell-sampling-Gur-2023.pdf - Accepted Version - Requires a PDF viewer. Download (249Kb) | Preview |
Abstract
Since 1989, the best known lower bound on static data structures was Siegel’s classical cell sampling lower bound. Siegel showed an explicit problem with n inputs and m possible queries such that every data structure that answers queries by probing t memory cells requires space s≥ ̃Ω(n·(mn)1/t). In this work, we improve this bound for non-adaptive data structures to s≥ ̃Ω(n·(mn)1/(t−1)) for all t≥2.
For t= 2, we give a lower bound of s > m−o(m), improving on the bound s > m/2 recently proved by Viola over F2 and Siegel’s bound s≥ ̃Ω(√mn) over other finite fields.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Computational complexity, Data structures (Computer science), Asymptotic distribution (Probability theory), Random access memory, Algorithms | ||||||
Journal or Publication Title: | Proceedings of the SIAM Symposium on Simplicity in Algorithms (SOSA23) | ||||||
Publisher: | SIAM | ||||||
Official Date: | 2023 | ||||||
Dates: |
|
||||||
Status: | Peer Reviewed | ||||||
Publication Status: | In Press | ||||||
Date of first compliant deposit: | 16 November 2022 | ||||||
Date of first compliant Open Access: | 16 November 2022 | ||||||
RIOXX Funder/Project Grant: |
|
||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | SIAM Symposium on Simplicity in Algorithms (SOSA23) | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Florence, Italy | ||||||
Date(s) of Event: | 23-25 Jan 2023 | ||||||
Related URLs: | |||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year