May 2024 - talks - lists.cs.princeton.edu

Shreyas Gandlur will present his general exam "How security and privacy research engages with law and policy: analysis and recommendations" on May 17, 2024 at 3pm via zoom.
by Nicki Mahler 10 May '24

10 May '24

Shreyas Gandlur will present his general exam "How security and privacy research engages with law and policy: analysis and recommendations" on May 17, 2024 at 3pm via zoom. Zoom link: https://princeton.zoom.us/my/sgandlur?pwd=dHhEZEZTZXBsSy9YaWlaZ0V3MDcvZz09 Committee members: Jonathan Mayer(adviser), Peter Henderson, and Andrés Monroy-Hernández Abstract and Reading List: [ https://docs.google.com/document/d/1h7WfeTn4PaVV85wL0eiRGHSO7Be-ws0qJykdcW9… | https://docs.google.com/document/d/1h7WfeTn4PaVV85wL0eiRGHSO7Be-ws0qJykdcW9… ]

1 0

Varun Nagaraj Rao will present his General Exam "Studying the Societal Impacts of AI on Labor" on Wednesday, May 15, 2024 at 3:00 PM in Sherrerd 008 and via zoom.
by CS Grad Department 10 May '24

10 May '24

Varun Nagaraj Rao will present his General Exam " Studying the Societal Impacts of AI on Labor " on Wednesday, May 15, 2024 at 3:00 PM in Sherrerd 008 and via zoom. Zoom link: https://princeton.zoom.us/j/97776899839 Committee Members: Andrés Monroy-Hernández (advisor), Arvind Narayanan , Peter Henderson Abstract: AI systems are increasingly mediating interactions on digital labor marketplaces, reshaping the nature of work and impacting billions of lives through opaque decisions. In this talk, I will explore the societal impact of AI on labor through the lens of rideshare and social media job ads. In the case of rideshare, through a unique mixed methods study design blending worker interviews with large scale LLM-assisted analysis of over 1 million driver comments on Reddit, we thickly characterize transparency-related harms, mitigation strategies, and worker needs. Motivated by our findings we propose an outline of the first rideshare transparency report. In the case of job ads on social media, our analysis of the Facebook Ad Library reveals a new form of discrimination through the selective use of demographic-specific images in job ads, affecting applicant demographics and reinforced by the ad delivery algorithm. Taken together, my research shows that AI-mediated platforms substantially shape job access for many through opaque, centralized decision-making which restricts user agency. Policy solutions mandating greater transparency may help with the decentralization of some platform power. Reading List: https://docs.google.com/document/d/1QQxG67c8qGV0rj1KRABONK8IJTY6emAECBUC8EA… Everyone is invited to attend the talk, and those faculty wishing to remain for the oral exam following are welcome to do so.

1 0

Elena Gribelyuk will present her General Exam "Lower Bounds for Adversarially Robust Streaming" on 5/17/2024 at 8am in CS 302 and Zoom.
by Nicki Mahler 10 May '24

10 May '24

Elena Gribelyuk will present her General Exam "Lower Bounds for Adversarially Robust Streaming" on 5/17/2024 at 8am in CS 302 and Zoom. Zoom link: [ https://princeton.zoom.us/j/2559568276 | https://princeton.zoom.us/j/2559568276 ] Committee members: Huacheng Yu (adviser), Alex Lombardi, and Gillat Kol Reading list and abstract: [ https://docs.google.com/document/d/1II1zg-GOCtRX2CZDaO3XebeeHy5XkNnOquyiTpp… | https://docs.google.com/document/d/1II1zg-GOCtRX2CZDaO3XebeeHy5XkNnOquyiTpp… ] Abstract: The majority of streaming problems are defined and analyzed in a static setting, where the data stream is fixed in advance to be a fixed sequence of insertions and deletions. However, many real world applications require a more flexible model, where an adaptive adversary may select future stream elements after observing the previous outputs of the algorithm. Over the last few years, there has been increased interest in proving lower bounds for natural problems in the adaptive streaming model. In this work, we give the first known adaptive attack against linear sketches for the well-studied L0-estimation problem over turnstile, integer streams. For any linear streaming algorithm which uses an integer r x n sketching matrix A, this attack makes O(r^8) queries and succeeds with high constant probability in breaking the sketch. Additionally, we give an adaptive attack against linear sketches for the L0-estimation problem over finite fields F_p, which requires a smaller number of O(r^3) queries. Our results provide an exponential improvement over the previous number of adaptive queries known to break an L0-estimation

1 0

Simran Kaur will present her General Exam "Skill-Mix: A Flexible And Expandable Family Of Evaluations For Ai Models" on Wednesday, May 15, 2024 at 2:00 PM in CS 105 and via zoom.
by CS Grad Department 10 May '24

10 May '24

Simran Kaur will present her General Exam "Skill-Mix: A Flexible And Expandable Family Of Evaluations For Ai Models" on Wednesday, May 15, 2024 at 2:00 PM in CS 105 and via zoom. Zoom link: https://princeton.zoom.us/my/skaur Committee Members: Sanjeev Arora (advisor), Elad Hazan, Danqi Chen Abstract: Existing LLM evaluations inadequately assess the originality of a model’s text productions and are susceptible to training-set contamination. Motivated by recent work (Arora & Goyal, 2023) that gives a mathematical model for skill emergence via LLM scaling, we present (a) Skill-Mix, a flexible and expandable family of LLM evaluations that tests for a form of compositional generalization; (b) probability calculations to evaluate whether LLMs surpass "stochastic parrot" behavior, i.e., whether an LLM can produce novel text pieces that were not encountered in the training corpus; and, (c) an investigation into synthetic data generation via Skill-Mix, which can be a more efficient alternative to raw human data for enhancing model capabilities. Reading List: https://docs.google.com/document/d/1N9ic4kFkVC07Fkrz_Vh5e774swk5Kq9FaEFMAJ6… Everyone is invited to attend the talk, and those faculty wishing to remain for the oral exam following are welcome to do so.

1 0

Pachara Sawettamalya will present his general exam "Towards the XOR Lemmas for Communication and Information Complexity” on May 16th, 2024 at 2pm in Friend 016
by Gradinfo 10 May '24

10 May '24

Please see revised title: Pachara Sawettamalya will present his general exam "Towards the XOR Lemmas for Communication and Information Complexity” on May 16th, 2024 at 2pm in Friend 016 Committee members: Huacheng Yu (adviser), Gillat Kol, and Ran Raz Abstract & Reading list: [ https://docs.google.com/document/d/1547EUIb5r8H1p6Lb83DDnRAHftifuC25IVf6Xzj… | https://docs.google.com/document/d/1547EUIb5r8H1p6Lb83DDnRAHftifuC25IVf6Xzj… ] [ https://docs.google.com/document/d/1V98QO3O7MT59um7f-tP5dqlX4sHm-P90uEjQpYL… | https://docs.google.com/document/d/1V98QO3O7MT59um7f-tP5dqlX4sHm-P90uEjQpYL… ]

1 0

Pachara Sawettamalya will present his general exam "Parallel Repetition and Applications to Dynamic Data Structures Lower Bounds" on May 16th, 2024 at 2pm in Friend 016
by Nicki Mahler 10 May '24

10 May '24

Pachara Sawettamalya will present his general exam "Parallel Repetition and Applications to Dynamic Data Structures Lower Bounds" on May 16th, 2024 at 2pm in Friend 016 Committee members: Huacheng Yu(adviser), Gillat Kol, and Ran Raz Abstract & Reading list: [ https://docs.google.com/document/d/1547EUIb5r8H1p6Lb83DDnRAHftifuC25IVf6Xzj… | https://docs.google.com/document/d/1547EUIb5r8H1p6Lb83DDnRAHftifuC25IVf6Xzj… ] [ https://docs.google.com/document/d/1V98QO3O7MT59um7f-tP5dqlX4sHm-P90uEjQpYL… | https://docs.google.com/document/d/1V98QO3O7MT59um7f-tP5dqlX4sHm-P90uEjQpYL… ]

1 0

Eric Xue will present his General Exam "Settling the competition complexity of additive buyers over independent items" on May 15th, 2024 at 1:30pm in Friend 005.
by Gradinfo 10 May '24

10 May '24

Eric Xue will present his General Exam "Settling the competition complexity of additive buyers over independent items" on May 15th, 2024 at 1:30pm in Friend 005. Committee members: Mark Braverman ( adviser), Matt Weinberg, and Huacheng Yu Abstract: Settling the competition complexity of additive buyers over independent items Committee: Mark Braverman, Matt Weinberg, Huacheng Yu Abstract: Auction design studies how to sell items to bidders in a way that incentives truthful participation. The goal of revenue maximization—as its name suggests—is to extract as much revenue as possible while doing so. In single-dimensional settings, e.g., selling a single item to multiple bidders, the seminal work of Myerson completely characterizes the revenue optimal auction, showing that it is structurally quite simple. In stark contrast, the revenue optimal auction for selling multiple items remains elusive, and for the settings that the literature understands, it has been shown that the revenue optimal auction can be extremely complex and deeply unintuitive. To circumvent this barrier, the literature has adopted two main approaches. The first is to approximate the revenue of the optimal auction via a simple auction, such as selling each item separately or posting a price on each item. This line of work has been fruitful, but there are times in practice when approximate revenue guarantees are not enough or it is costly to know the prior—the distribution from which bidders come—so that an auction which achieves these approximations can be designed. The resource augmentation approach addresses these concerns: this approach seeks to sell items in a prior-independent way but guarantee as much revenue as the optimal auction for the original set of bidders by recruiting sufficiently many additional bidders so that economic competition itself drives up revenue. For a given auction environment, the minimum number of bidders needed to do so is termed its competition complexity. We show that the competition complexity of selling m independent items to n additive bidders when m < n is precisely \Theta(\sqrt{nm}). More specifically, prior work demonstrated an O(\sqrt{nm}) upper bound on the competition complexity for this setting. We prove a matching \Omega(\sqrt{nm}) lower bound by explicitly constructing a Bayesian incentive compatible auction for selling m items to n additive bidders with values drawn iid from the Equal Revenue distribution truncated at \sqrt{nm} that obtains at least as much revenue as optimally selling each item separately to n + \Omega(\sqrt{nm}) bidders. Abstract & Reading List: [ https://docs.google.com/document/d/1VQ9_0ffiQGxtun3CaG5tdDbH_A15IX_XLx-JVXA… | https://docs.google.com/document/d/1VQ9_0ffiQGxtun3CaG5tdDbH_A15IX_XLx-JVXA… ]

1 0

Fengchen Gong will present her General Exam "Constrained Network Telemetry Imputation" on Wednesday, 5/15/24 at 2pm in CS 302.
by Gradinfo 10 May '24

10 May '24

Fengchen Gong will present her General Exam "Zooming Into Network Monitoring: Knowledge-Augmented Transformer for Imputing Fine-Grained Telemetry" on Wednesday, 5/15/24 at 2pm in CS 302 Zoom link: https://princeton.zoom.us/j/98048355515 The members of the committee are as follows: Maria Apostolaki (adviser), Aarti Gupta, Amit Levy Link to Abstract: [ https://docs.google.com/document/d/1pYSfiFvnMXJ3_EJqEBbiC8PETvjnXHnoKrg-sXM… | https://docs.google.com/document/d/1pYSfiFvnMXJ3_EJqEBbiC8PETvjnXHnoKrg-sXM… ] Link to Reading List: https://docs.google.com/document/d/1pYSfiFvnMXJ3_EJqEBbiC8PETvjnXHnoKrg-sXM…

1 0

Zhongtian He will present the General Exam "On the Network Coding Conjecture" on 5/13/24 at 1:30pm in CS 401.
by Nicki Mahler 09 May '24

09 May '24

Zhongtian He will present the General Exam "On the Network Coding Conjecture" on 5/13/24 at 1:30pm in CS 401. Committee Members: Mark Braverman(adviser). Huacheng Yu, and Ran Raz Abstract and Reading list can be found here: [ https://docs.google.com/document/d/11OJHqPsG2Su3-Kv-cASw1h7kPu34W2RxRXkPhh8… | https://docs.google.com/document/d/11OJHqPsG2Su3-Kv-cASw1h7kPu34W2RxRXkPhh8… ] While it's recognized that the utilization of network coding can greatly enhance the throughput of directed networks, an enduring open problem remains as to whether coding provides any advantage over the multicommodity flow (MCF) rate in undirected networks. It was conjectured by Li and Li in 2004 that the answer is ‘no’. We will present our recent progress on the conjecture.

1 0

Christopher Branner-Augmon will present his General Exam "Multidispatch Strict Serializability" on May 13, 2024 at 10am in CS 302.
by Gradinfo 09 May '24

09 May '24

Christopher Branner-Augmon will present his General Exam "Multidispatch Strict Serializability" on May 13, 2024 at 10am in CS 302. The members of his committee are as follows: Amit Levy (adviser), Wyatt Lloyd (adviser), and Mae Milano All are welcome to attend. Link to Abstract & Reading List: [ https://docs.google.com/document/d/17tl_RVhAsbMn5ybUWr26wDSpEvQwHNtwBhbRpze… | https://docs.google.com/document/d/17tl_RVhAsbMn5ybUWr26wDSpEvQwHNtwBhbRpze… ] [ https://docs.google.com/document/d/17Am6ooY9jXDuhJ_es8aiggFagC2aSMjN9P28fEp… | https://docs.google.com/document/d/17Am6ooY9jXDuhJ_es8aiggFagC2aSMjN9P28fEp… ]

2 1