Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorKannan, Sampathen
dc.contributor.authorMossel, Elchananen
dc.contributor.authorSanyal, Swagatoen
dc.contributor.authorYaroslavtsev, Grigoryen
dc.identifier.citationKannan, S., Mossel, E., Sanyal, S., & Yaroslavtsev, G. (2018). Linear sketching over F2. Leibniz International Proceedings in Informatics, 102, 8-. doi:10.4230/LIPIcs.CCC.2018.8en
dc.description.abstractWe initiate a systematic study of linear sketching over F_2. For a given Boolean function treated as f : F_2^n -> F_2 a randomized F_2-sketch is a distribution M over d x n matrices with elements over F_2 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 F_2-sketching and a two-player one-way communication game for the corresponding XOR-function. We conjecture that F_2-sketching is optimal for this communication game. Our results confirm this conjecture for multiple important classes of functions: 1) low-degree F_2-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 F_2-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 F_2 can be constructed as F_2-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 O(n) constructed through uniformly random updates.en
dc.description.sponsorshipNRF (Natl Research Foundation, S’pore)en
dc.format.extent37 p.en
dc.relation.ispartofseriesLeibniz International Proceedings in Informaticsen
dc.rights© 2018 Sampath Kannan, Elchanan Mossel, Swagato Sanyal, and Grigory Yaroslavtsev; licensed under Creative Commons License CC-BY.en
dc.subjectLinear Sketchen
dc.subjectStreaming Algorithmsen
dc.titleLinear sketching over F2en
dc.typeJournal Articleen
dc.contributor.schoolSchool of Physical and Mathematical Sciencesen
dc.description.versionPublished versionen
item.fulltextWith Fulltext-
Appears in Collections:SPMS Journal Articles
Files in This Item:
File Description SizeFormat 
Linear Sketching over F_2.pdf796.91 kBAdobe PDFThumbnail

Citations 20

checked on Aug 31, 2020

Citations 50

checked on Sep 17, 2020

Page view(s) 20

checked on Sep 25, 2020

Download(s) 50

checked on Sep 25, 2020

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.