- talks - lists.cs.princeton.edu

Ariel Schvartzman Cohenca will present his FPO "Circumventing Lower Bounds in Mechanism and Tournament Design" on May 13, 2020 at 1:30pm via Zoom
by Nicki Mahler 05 May '20

05 May '20

Ariel Schvartzman Cohenca will present his FPO "Circumventing Lower Bounds in Mechanism and Tournament Design" on May 13, 2020 at 1:30pm via Zoom. Zoom link: [ https://princeton.zoom.us/j/94615499699 | https://princeton.zoom.us/j/94615499699 ] The members of his committee are as follows: Matthew Weinberg (adviser), Readers: Gillat Kol and Elad Hazan; Examiners: Matthew Weinberg, Ran Raz, and Mark Braverman A copy of his thesis, is available upon request. Please email ngotsis(a)cs.princeton if you would like a copy of the thesis. Everyone is invited to attend his talk. Abstract follows below. How should a seller price multiple items in order to maximize their revenue from a single buyer? This question has been key in connecting research done by computer scientists and economists to applications such as online ad auctions and spectrum auctions. It was shown almost 40 years ago that if the buyer only cares for one item it is optimal for the seller to offer the buyer the item at a take-it-or-leave-it price [74]. This elegant solution, however, may be far from optimal even for the case with a single buyer interested in just two items. Optimal auction design for two or more items is intricate for a number of reasons: the auctions may be bizarre, computationally hard to find or simply too complex to present to a bidder [34, 52, 56, 68]. Numerous results suggest that (under reasonable complexity assumptions) efficiently finding optimal auctions, even in some simple settings, is impossible [27, 33]. In this thesis, I will present numerous ways in which we try to circumvent these impossibility results in order to recover positive results. These include the study of different multi-item models and beyond-worst case analysis for mechanism design. I will also discuss recent advances in tournament design, a field at the intersection of mechanism design and social choice theory. For problems in this field we get around known impossibility results via approximations in order to find approximately strategyproof tournament rules.

1 0

Fangyin Wei will present her General Exam "Learning to Manipulate 3D Shapes" on May 13, 2020 at 3pm via Zoom
by Nicki Mahler 05 May '20

05 May '20

Fangyin Wei will present her General Exam "Learning to Manipulate 3D Shapes" on May 13, 2020 at 3pm via Zoom. Zoom Link: [ https://princeton.zoom.us/j/5929951382 | https://princeton.zoom.us/j/5929951382 ] The members of her committee are as follows: Szymon Rusinkiewicz (adviser), Thomas Funkhouser (adviser), and Felix Heide Abstract and Reading List: [ https://docs.google.com/document/d/1NLok_Q5Hlc2sLiuFRK8uzvXvn8UgfSGEpqoOxr4… | https://docs.google.com/document/d/1NLok_Q5Hlc2sLiuFRK8uzvXvn8UgfSGEpqoOxr4… ] 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

Jordan Holland will present his General Exam "Packets as Pictures: A General Spatial Representation for Network Traffic" on May 13, 2020 at 10am via zoom
by Nicki Mahler 05 May '20

05 May '20

Jordan Holland will present his General Exam "Packets as Pictures: A General Spatial Representation for Network Traffic" on May 13, 2020 at 10am via zoom Zoom meeting: [ https://uchicago.zoom.us/j/373623135 | https://uchicago.zoom.us/j/373623135 ] The members of his committee are as follows: Nick Feamster (adviser), Prateek Mittal, and Jonathan Mayer Links to Abstract and Reading List: [ https://docs.google.com/document/d/13a4jSNclD9rgaS5lvmS5qqwj4Ljkpag-3wqesCb… | https://docs.google.com/document/d/13a4jSNclD9rgaS5lvmS5qqwj4Ljkpag-3wqesCb… ] [ https://docs.google.com/document/d/12eHB4uvOoRKfo6d_cetGWPFZN76I_pejztVYDES… | https://docs.google.com/document/d/12eHB4uvOoRKfo6d_cetGWPFZN76I_pejztVYDES… ] 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

Benjamin Kaiser will present his General Exam "Effectively Warning Users about Online Disinformation" on May 12, 2020 at 10am via zoom
by Nicki Mahler 04 May '20

04 May '20

Benjamin Kaiser will present his General Exam "Effectively Warning Users about Online Disinformation" on May 12, 2020 at 10am via zoom. Zoom link: [ https://princeton.zoom.us/j/545902219 | https://princeton.zoom.us/j/545902219 ] The members of his committee are as follows: Jonathan Mayer (adviser), Arvind Naryanan, and Andy Guess Link to Abstract and Reading List: [ https://docs.google.com/document/d/1Mh6RW_va_Y-_fpJscNeqUhZNKzevMGn16JPidEK… | https://docs.google.com/document/d/1Mh6RW_va_Y-_fpJscNeqUhZNKzevMGn16JPidEK… ] 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

Linda Cai will present her MSE talk "Novel Behaviors in Combinatorial Auctions" on Friday, May 8, 2020 at 4pm via Zoom.
by Nicki Mahler 04 May '20

04 May '20

Linda Cai will present her MSE talk "Novel Behaviors in Combinatorial Auctions" on Friday, May 8, 2020 at 4pm via Zoom. Link to Zoom: [ https://us04web.zoom.us/j/5668379247 | https://us04web.zoom.us/j/5668379247 ] The members of her committee are as follows: Matt Weinberg (adviser) and Mark Braverman (reader) Understanding the power and limitations of efficient combinatorial auctions in various settings is a problem at the heart of modern day algorithmic game theory. There are two main notions of efficiency, computational efficiency (running the auction requires low computational power) and communication efficiency (a small number of bits need to be exchanged during the auction). For truthful combinatorial auctions with submodular valuation functions, these two notions of efficiency differ doubly exponentially in the approximation guarantees they can provide, and this distinction stems from the fact that demand queries are communication efficient but hard to even approximate in a computationally efficient way. We suggest a mild and natural relaxation of truthfulness under which this distinction disappears. Under our relaxation, we define a notion of demand queries, called bicriterion approximate demand queries, that can be computed in polynomial time. We use these demand queries to design computationally efficient combinatorial auctions satisfying our relaxed notion of truthfulness with approximation guarantees matching those known for communication efficient auctions. We also briefly discuss the problem of revenue maximization in repeated auctions when bidders are using mean-based no regret learning algorithms.

1 0

Molly Pan will present her MSE talk, "Memory-Efficient Membership Encoding in Switches" on Tuesday, May 5, 2020 at 3pm via Zoom
by Nicki Mahler 04 May '20

04 May '20

Molly Pan will present her MSE talk, "Memory-Efficient Membership Encoding in Switches" on Tuesday, May 5, 2020 at 3pm via Zoom. Link to Zoom: [ https://princeton.zoom.us/j/7979634003 | https://princeton.zoom.us/j/7979634003 ] The members of her committee are as follows: Jennifer Rexford (adviser), and Wyatt Lloyd (reader). All are invited to attend. The talk abstract follows below. Network applications often define policies to manage network traffic based on its attributes. For example, service chaining forwards traffic to reach the middleboxes it wants to visit, and access control restricts traffic by checking the permission flags it carries. These policies match against packets' attributes in switches before being applied. However, the prior works of attribute encoding all incur a high memory cost to identify the attributes in the data plane. This paper presents MEME, an encoding scheme that clusters the attributes which tend to appear together in the traffic to reduce the memory usage. Naive clustering would still fail since it is ineffective when a cluster contains an excessive number of attributes. To tackle this, MEME breaks the clusters into smaller ones by encoding a minimal number of attributes separately and by taking advantage of the special structures within the attributes. MEME also leverages match-action tables and reconfigurable parsers on modern hardware switches to achieve a final 87.7% lower memory usage, and applies an approximate graph algorithm to achieve 1-2 orders of magnitude faster compilation time than the prior state of the art. These performance gains pave the way for deployment of a real traffic management system desired by the world's largest Internet Exchange Points.

1 0

Suriya Kodeswaran will present his MSE talk "Tracking P4 Program Execution in the Data Plane" on Friday, May 8, 2020 at 1pm via Zoom.
by Nicki Mahler 01 May '20

01 May '20

Suriya Kodeswaran will present his MSE talk "Tracking P4 Program Execution in the Data Plane" on Friday, May 8, 2020 at 1pm via Zoom. Zoom link: [ https://princeton.zoom.us/j/3304136967 | https://princeton.zoom.us/j/3304136967 ] The members of his committee are as follows: Jennifer Rexford (adviser) and Andrew APpel (reader). All are welcome to attend. Abstract follows below. While programmable switches provide operators with much needed control over the network, they also increase the potential sources of packet-processing errors. Bugs can happen anywhere: in the P4 program, the controller installing rules into tables, or the compiler that maps the P4 program into the resource-constrained switch pipelines. Most of these bugs manifest themselves after certain sequences of packets with certain combinations of rules in the tables. Tracking each packet’s execution path through the P4 program, i.e., the sequence of tables hit and the actions applied, directly in the data plane is useful in localizing such bugs as they occur in real time. The fact that programmable data planes require P4 programs to be loop-free and can perform simple integer arithmetic operations make them amenable to Ball-Larus encoding, a well-known technique in profiling execution paths in software programs that can efficiently encode all N paths in a single ⌈loд(N)⌉-bit variable. However, for real-world P4 programs, the path variable can get quite large, making it inefficient for integer arithmetic at line rate. Moreover, the encoding could require a subset of tables, that would otherwise have no data dependency, to update the same variable. By carefully breaking up the P4 program into disjoint partitions and tracking each partition’s execution path separately, we show how to minimally augment P4 programs to track the execution path of each packet. With this system in place, we then provide intuition towards using the tracked path to detect and localize bugs in P4 programs.

1 0

Joseph Eichenhofer will present his MSE talk "Voiceover: Censorship-Circumventing Protocol Tunnels with Generative Modelling" on Thursday May 7, 2020 at 11am via Zoom.
by Nicki Mahler 30 Apr '20

30 Apr '20

Joseph Eichenhofer will present his MSE talk "Voiceover: Censorship-Circumventing Protocol Tunnels with Generative Modelling" on Thursday May 7, 2020 at 11am via Zoom. Zoom Link: [ https://princeton.zoom.us/j/92944512708 | https://princeton.zoom.us/j/92944512708 ] The members of his committee are as follows: Prateek Mittal (adviser), and Arvind Narayanan (reader). All are welcome to attend. Abstract: Censorship regimes are continuously adopting and deploying state-of-the-art techniques to detect and prosecute open communication on the internet. Multimedia protocol tunneling seeks to disguise covert data communication by processing it directly through a legitimate audio/video communication system. Systems like VoIP and video streaming services use variable bitrate encoding schemes, which leak characteristics of the content they carry through packet sizes and timing. In what we call a content mismatch attack, censors can distinguish between a channel carrying the legitimate media content and one carrying covert data content. We address content mismatch attacks by introducing a novel traffic shaping technique that models the normal media content and applies its properties to the covert content. We constructed a generative machine learning model to restrict covert data transmission such that its timing properties match properties learned from real two-person conversations. Our evaluation finds that modeling the timing properties in the application layer content reduces distinguishing features in the encrypted network traffic. This mitigates content mismatch attacks on coarse-grained timing properties.

1 0

Haochen Li will present his MSE Talk "Emergence of race and gender in face recognition systems" on Thursday May 7th, 2020 at 2pm via Zoom
by Nicki Mahler 29 Apr '20

29 Apr '20

Haochen Li will present his MSE Talk " Emergence of race and gender in face recognition systems" on Thursday May 7th, 2020 at 2pm. The talk will take place via Zoom: [ https://princeton.zoom.us/j/96991086598 | https://princeton.zoom.us/j/96991086598 ] The members of his committee are Arvind Narayanan (adviser) and Olga Russakovsky (reader). Everyone is invited to attend his talk. His abstract follows below. Abstract: Can computer vision recover attributes such as gender and race(or some approximation thereof) from facial images without being trained for such classification? We show that face recognition systems accurately reproduce human categorizations of race and gender in photos of faces, despite receiving no training labels for such classification. We show race and gender categorization both in FaceNet, a state-of-the-art vector embedding, and Microsoft’s Bing Face API, a deployed black-box system. Given that deployed AI systems today use facial expressions to make decisions about people, our work shows that withholding sensitive attributes from the model does not ensure that the models have no access to them.

1 0

Anastasiya Kravchuk-Kirilyuk will present her MSE talk "The B+-tree Index as a Verified Software Unit" on May 7th, 2020 at 1:30 pm via Zoom.
by Nicki Mahler 29 Apr '20

29 Apr '20

Anastasiya Kravchuk-Kirilyuk will present her MSE talk "The B+-tree Index as a Verified Software Unit" on May 7th, 2020 at 1:30 pm via Zoom. Zoom Link: [ https://princeton.zoom.us/j/9432858291 | https://princeton.zoom.us/j/9432858291 ] The members of her committee are as follows: Andrew Appel (adviser) and Lennart Beringer (reader) Everyone is invited to attend her talk. Please see below for talk abstract. Ordered indexes are used in relational databases to allow for a faster retrieval of records. An ordered index can be implemented using a variety of data structures, and the query planner can later decide which implementation to use for optimal performance. This means the implementation details of an ordered index need not be exposed to the user. In this work, we define an API that any instance of an ordered index should implement. Then, we show that a particular instance of an ordered index, the B+-tree with cursors, satisfies this general interface. Finally, we present the B+-tree index instance as a Verified Software Unit, a VST-verified module with explicitly defined sets of imported and exported functions. That is, a B+-tree implementation verified for functional correctness to a B+-tree specification in previous work, is formally proved to be functionally correct w.r.t. the abstract specification of an ordered index. We verify our code using the Coq proof assistant, the Verified Software Toolchain (VST), and CompCert.

1 0