[Theory] TODAY: 12/4 Young Researcher Seminar Series: Meghal Gupta, UC Berkeley

[Mary Marre via Theory]

*When:*        Wednesday, December 4, 2024 at* 11:00** am** CT   *


*Where:       *Talk will be given *live, in-person* at

                   TTIC, 6045 S. Kenwood Avenue

                   5th Floor, Room 530


*Virtually:*   *via panopto: **livestream*
<https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=5e0c8d50-c0f3-4d13-80f5-b23a014e312e>





*Who: *         Meghal Gupta, UC Berkeley



*Title*:          Optimal Quantile Estimation: Beyond the Comparison Mode

*Abstract: *Estimating the median of a stream is one of the most basic
problems in data sketching. Precisely, given a stream x1, x2, x3, …, xn of
elements from some universe of size U and an accuracy ε, the goal is to
give a space/time-efficient algorithm that outputs an element with rank
between (1/2-ε)n and (1/2+ε)n. Estimating arbitrary quantiles has the same
space/time complexity as estimating the median.

The simplest approach to quantile (or median) estimation stores every
element individually, requiring nlogU memory. However, numerous algorithms
have been developed that achieve significantly better bounds. Despite
these results, the optimal algorithm was not known prior to this work. In
this talk, we will describe an optimal deterministic quantile sketch that
uses O(ε-1·(logn+logU)) bits of memory. This improves upon the previous
best deterministic algorithm (Greenwald and Khanna 2003) and even upon the
best randomized algorithm (Karnin, Lang, and Libery 2016).

This is joint work with Mihir Singhal and Hongxun Wu.

*Bio: *Hi! My name is Meghal, and I'm a 3rd year graduate student at UC
Berkeley. My interests lie primarily in streaming algorithms and
error-correcting codes, but I like working on most combinatorial areas of
TCS. I'm fortunate to be advised by Professor Venkatesan Guruswami.

*Host: **Avrim Blum* <avrim at ttic.edu> and *Siddharth Bhandari*
<siddharth at ttic.edu>




Mary C. Marre
Faculty Administrative Support
*Toyota Technological Institute*
*6045 S. Kenwood Avenue, Rm 517*
*Chicago, IL  60637*
*773-834-1757*
*mmarre at ttic.edu <mmarre at ttic.edu>*


On Tue, Dec 3, 2024 at 2:28 PM Mary Marre <mmarre at ttic.edu> wrote:

> *When:*        Wednesday, December 4, 2024 at* 11:00** am** CT   *
>
>
> *Where:       *Talk will be given *live, in-person* at
>
>                    TTIC, 6045 S. Kenwood Avenue
>
>                    5th Floor, Room 530
>
>
> *Virtually:*   *via panopto: **livestream*
> <https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=5e0c8d50-c0f3-4d13-80f5-b23a014e312e>
>
>
>
>
>
> *Who: *         Meghal Gupta, UC Berkeley
>
>
>
> *Title*:          Optimal Quantile Estimation: Beyond the Comparison Mode
>
> *Abstract: *Estimating the median of a stream is one of the most basic
> problems in data sketching. Precisely, given a stream x1, x2, x3, …, xn of
> elements from some universe of size U and an accuracy ε, the goal is to
> give a space/time-efficient algorithm that outputs an element with rank
> between (1/2-ε)n and (1/2+ε)n. Estimating arbitrary quantiles has the same
> space/time complexity as estimating the median.
>
> The simplest approach to quantile (or median) estimation stores every
> element individually, requiring nlogU memory. However, numerous algorithms
> have been developed that achieve significantly better bounds. Despite
> these results, the optimal algorithm was not known prior to this work. In
> this talk, we will describe an optimal deterministic quantile sketch that
> uses O(ε-1·(logn+logU)) bits of memory. This improves upon the previous
> best deterministic algorithm (Greenwald and Khanna 2003) and even upon the
> best randomized algorithm (Karnin, Lang, and Libery 2016).
>
> This is joint work with Mihir Singhal and Hongxun Wu.
>
> *Bio: *Hi! My name is Meghal, and I'm a 3rd year graduate student at UC
> Berkeley. My interests lie primarily in streaming algorithms and
> error-correcting codes, but I like working on most combinatorial areas of
> TCS. I'm fortunate to be advised by Professor Venkatesan Guruswami.
>
> *Host: **Avrim Blum* <avrim at ttic.edu> and *Siddharth Bhandari*
> <siddharth at ttic.edu>
>
>
>
>
> Mary C. Marre
> Faculty Administrative Support
> *Toyota Technological Institute*
> *6045 S. Kenwood Avenue, Rm 517*
> *Chicago, IL  60637*
> *773-834-1757*
> *mmarre at ttic.edu <mmarre at ttic.edu>*
>
>
> On Mon, Dec 2, 2024 at 2:22 PM Mary Marre <mmarre at ttic.edu> wrote:
>
>> *When:*         Wednesday, December 4, 2024 at* 11:00** am** CT   *
>>
>>
>> *Where:       *Talk will be given *live, in-person* at
>>
>>                    TTIC, 6045 S. Kenwood Avenue
>>
>>                    5th Floor, Room 530
>>
>>
>> *Virtually:*   *via panopto: **livestream*
>> <https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=5e0c8d50-c0f3-4d13-80f5-b23a014e312e>
>>
>>
>>
>>
>>
>> *Who: *         Meghal Gupta, UC Berkeley
>>
>>
>>
>> *Title*:          Optimal Quantile Estimation: Beyond the Comparison Mode
>>
>> *Abstract: *Estimating the median of a stream is one of the most basic
>> problems in data sketching. Precisely, given a stream x1, x2, x3, …, xn of
>> elements from some universe of size U and an accuracy ε, the goal is to
>> give a space/time-efficient algorithm that outputs an element with rank
>> between (1/2-ε)n and (1/2+ε)n. Estimating arbitrary quantiles has the same
>> space/time complexity as estimating the median.
>>
>> The simplest approach to quantile (or median) estimation stores every
>> element individually, requiring nlogU memory. However, numerous algorithms
>> have been developed that achieve significantly better bounds. Despite
>> these results, the optimal algorithm was not known prior to this work. In
>> this talk, we will describe an optimal deterministic quantile sketch that
>> uses O(ε-1·(logn+logU)) bits of memory. This improves upon the previous
>> best deterministic algorithm (Greenwald and Khanna 2003) and even upon the
>> best randomized algorithm (Karnin, Lang, and Libery 2016).
>>
>> This is joint work with Mihir Singhal and Hongxun Wu.
>>
>> *Bio: *Hi! My name is Meghal, and I'm a 3rd year graduate student at UC
>> Berkeley. My interests lie primarily in streaming algorithms and
>> error-correcting codes, but I like working on most combinatorial areas of
>> TCS. I'm fortunate to be advised by Professor Venkatesan Guruswami.
>>
>> *Host: **Avrim Blum* <avrim at ttic.edu> and *Siddharth Bhandari*
>> <siddharth at ttic.edu>
>>
>>
>>
>>
>>
>> Mary C. Marre
>> Faculty Administrative Support
>> *Toyota Technological Institute*
>> *6045 S. Kenwood Avenue, Rm 517*
>> *Chicago, IL  60637*
>> *773-834-1757*
>> *mmarre at ttic.edu <mmarre at ttic.edu>*
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20241204/383c2ed7/attachment-0001.html>