Showing cs.CCShow all
2 papers · 1 filter
cs.CC2025
An Invariance Principle for the Multi-slice, with Applications
Mark Braverman, Subhash Khot, Noam Lifshitz +1
Given an alphabet size thought of as a constant, and whose entries sum of up , the -multi-slice is the set of vectors $x\i…
cs.CC2024
A New Information Complexity Measure for Multi-pass Streaming with Applications
Mark Braverman, Sumegha Garg, Qian Li +3
We introduce a new notion of information complexity for multi-pass streaming problems and use it to resolve several important questions in data streams. In the coin problem, one se…