The Technion Theory Lunch is a seminar run by the theory group at the Department of Computer Science, Technion. The seminar holds weekly meetings in which graduate students and faculty from the Technion and other universities in Israel and abroad present recent results or other interesting topics in theoretical computer science. The seminar is open to faculty, graduate and undergraduate students interested in theory of computing.
Wednesdays, 13:00-14:00 (food starts at 12:45)
Room 401, Taub Building
If you are interested in giving a talk at the seminar, contact Omri Ben-Eliezer and/or David Wajc.
The seminar’s mailing list is used to announce our weekly meetings, and also to publicize CS theory related events, such as workshops and seminars, in Israel and abroad.
To join or leave our mailing list.
The Huge Object model is a distribution testing model in which we are given access to independent samples from an unknown distribution over the set of strings {0, 1} n, but are only allowed to query a few bits from the samples. We investigate the problem of testing whether a distribution is supported on m elements in this model. It turns out that the behavior of this property is surprisingly intricate, especially when also considering the question of adaptivity. We prove lower and upper bounds for both adaptive and non-adaptive algorithms in the one-sided and two-sided error regime. Our bounds are tight when m is fixed to a constant (and the distance parameter ε is the only variable). For the general case, our bounds are at most O(log m) apart. In particular, our results show a surprising O(log ε −1 ) gap between the number of queries required for non-adaptive testing as compared to adaptive testing. For one sided error testing, we also show that a O(log m) gap between the number of samples and the number of queries is necessary. Our results utilize a wide variety of combinatorial and probabilistic methods.
Joint with Eldar Fischer and Amit Levi (https://arxiv.org/pdf/2308.15988)
Upcoming
