Linear sketching over F<inf>2</inf>
© Sampath Kannan, Elchanan Mossel, Swagato Sanyal, and Grigory Yaroslavtsev; licensed under Creative Commons License CC-BY 33rd Computational Complexity Conference (CCC 2018). We initiate a systematic study of linear sketching over F2. For a given Boolean function treated as f: F2 → F 2 a randomized...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2021
|
| Online Access: | https://hdl.handle.net/1721.1/138105 |
| _version_ | 1826217603937337344 |
|---|---|
| author | Kannan, Sampath Mossel, Elchanan Sanyal, Swagato Mossel, Elchanan |
| author2 | Massachusetts Institute of Technology |
| author_facet | Massachusetts Institute of Technology Kannan, Sampath Mossel, Elchanan Sanyal, Swagato Mossel, Elchanan |
| author_sort | Kannan, Sampath |
| collection | MIT |
| description | © Sampath Kannan, Elchanan Mossel, Swagato Sanyal, and Grigory Yaroslavtsev; licensed under Creative Commons License CC-BY 33rd Computational Complexity Conference (CCC 2018). We initiate a systematic study of linear sketching over F2. For a given Boolean function treated as f: F2 → F 2 a randomized F2-sketch is a distribution M over d × n matrices with elements over F2 such that Mx suffices for computing f(x) with high probability. Such sketches for d << n can be used to design small-space distributed and streaming algorithms. Motivated by these applications we study a connection between F2-sketching and a two-player one-way communication game for the corresponding XOR-function. We conjecture that F2-sketching is optimal for this communication game. Our results confirm this conjecture for multiple important classes of functions: 1) low-degree F2-polynomials, 2) functions with sparse Fourier spectrum, 3) most symmetric functions, 4) recursive majority function. These results rely on a new structural theorem that shows that F2-sketching is optimal (up to constant factors) for uniformly distributed inputs. Furthermore, we show that (non-uniform) streaming algorithms that have to process random updates over F2 can be constructed as F2-sketches for the uniform distribution. In contrast with the previous work of Li, Nguyen and Woodruff (STOC'14) who show an analogous result for linear sketches over integers in the adversarial setting our result does not require the stream length to be triply exponential in n and holds for streams of length Õ(n) constructed through uniformly random updates. |
| first_indexed | 2024-09-23T17:06:19Z |
| format | Article |
| id | mit-1721.1/138105 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T17:06:19Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | mit-1721.1/1381052022-10-03T10:26:24Z Linear sketching over F<inf>2</inf> Kannan, Sampath Mossel, Elchanan Sanyal, Swagato Mossel, Elchanan Massachusetts Institute of Technology © Sampath Kannan, Elchanan Mossel, Swagato Sanyal, and Grigory Yaroslavtsev; licensed under Creative Commons License CC-BY 33rd Computational Complexity Conference (CCC 2018). We initiate a systematic study of linear sketching over F2. For a given Boolean function treated as f: F2 → F 2 a randomized F2-sketch is a distribution M over d × n matrices with elements over F2 such that Mx suffices for computing f(x) with high probability. Such sketches for d << n can be used to design small-space distributed and streaming algorithms. Motivated by these applications we study a connection between F2-sketching and a two-player one-way communication game for the corresponding XOR-function. We conjecture that F2-sketching is optimal for this communication game. Our results confirm this conjecture for multiple important classes of functions: 1) low-degree F2-polynomials, 2) functions with sparse Fourier spectrum, 3) most symmetric functions, 4) recursive majority function. These results rely on a new structural theorem that shows that F2-sketching is optimal (up to constant factors) for uniformly distributed inputs. Furthermore, we show that (non-uniform) streaming algorithms that have to process random updates over F2 can be constructed as F2-sketches for the uniform distribution. In contrast with the previous work of Li, Nguyen and Woodruff (STOC'14) who show an analogous result for linear sketches over integers in the adversarial setting our result does not require the stream length to be triply exponential in n and holds for streams of length Õ(n) constructed through uniformly random updates. 2021-11-10T13:46:21Z 2021-11-10T13:46:21Z 2018-06 2019-11-18T12:59:39Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/138105 Kannan, Sampath, Mossel, Elchanan, Sanyal, Swagato and Mossel, Elchanan. 2018. "Linear sketching over F<inf>2</inf>." en http://dx.doi.org/10.4230/LIPIcs.CCC.2018.8 Creative Commons Attribution 4.0 International license https://creativecommons.org/licenses/by/4.0/ application/pdf DROPS |
| spellingShingle | Kannan, Sampath Mossel, Elchanan Sanyal, Swagato Mossel, Elchanan Linear sketching over F<inf>2</inf> |
| title | Linear sketching over F<inf>2</inf> |
| title_full | Linear sketching over F<inf>2</inf> |
| title_fullStr | Linear sketching over F<inf>2</inf> |
| title_full_unstemmed | Linear sketching over F<inf>2</inf> |
| title_short | Linear sketching over F<inf>2</inf> |
| title_sort | linear sketching over f inf 2 inf |
| url | https://hdl.handle.net/1721.1/138105 |
| work_keys_str_mv | AT kannansampath linearsketchingoverfinf2inf AT mosselelchanan linearsketchingoverfinf2inf AT sanyalswagato linearsketchingoverfinf2inf AT mosselelchanan linearsketchingoverfinf2inf |