The Library
Derandomization of cell sampling
Tools
Tools
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
