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

Manik Dhar will present his FPO "Beyond the polynomial method: Kakeya sets over finite rings and high dimensional variants" on Friday, June 30, 2023 at 12pm in CS 105.
by Nicki Mahler 01 Jun '23

01 Jun '23

Manik Dhar will present his FPO "Beyond the polynomial method: Kakeya sets over finite rings and high dimensional variants" on Friday, June 30, 2023 at 12pm in CS 105. The members of his committee are as follows: Readers: Ran Raz and Huacheng Yu; Examiners: Zeev Dvir (adviser), Bernard Chazelle, and Noga Alon (Math Department) All are welcome to attend. Abstract follows below: A Kakeya Set in Fn is a set that contains a line in every direction. It has been known for over a decade that such sets must be large. This goes back to Dvir’s proof of the finite field Kakeya conjecture as posed by Wolff. Dvir’s proof uses the polynomial method to solve this problem. The problem over finite fields also has applications in psuedorandomness and is crucially used in the construction of currently state-of-the-art seeded mergers and extractors. Wolff’s motivation was to pose a possibly simpler problem whose resolution might help with solving the notoriously difficult Euclidean Kakeya conjecture. The Euclidean Kakeya problem also has many connections with analysis, PDEs, and combinatorics. This thesis will look at two generalizations of the finite field Kakeya problem. One where Fq is replaced by the ring Z/N Z and another where we look at higher dimensional analogues of this problem. In both cases, the polynomial method does not work - as over Z/N Z polynomials do not represent all functions and in the other case a degree d polynomial can have much larger than d roots over a higher dimensional affine flat. We will cover a series of results that solve these problems by extending and in some cases going beyond the polynomial method. We will also cover recent applications of the higher dimensional Kakeya problem to give a tight analysis of the behaviour of linear hashes. At a high level, we show that if we pick subspaces of large enough dimension in comparison to the size of a set then for a large fraction of them their every shift intersects with the set in close to the expected number of points.

1 1

Wei Zhan will present his FPO, "Randomness and Quantumness in Space-Bounded Computation" on Friday, June 23, 2023at 10am in CS 105.
by Gradinfo 30 May '23

30 May '23

Wei Zhan will present his FPO, "Randomness and Quantumness in Space-Bounded Computation" on Friday, June 23, 2023 at 10am in CS 105. The members of his committee are as follows: Examiners: Ran Raz (adviser), Gillat Kol and Mark Braverman; Readers: Huacheng Yu and Zeev Dvir. In the field of computational complexity theory, we study the power and limits of dif- ferent computational resources and the interplay between them. The constraints on space complexity provide a natural and interesting setting, that is often more tractable than the time-restricted counterparts. In this dissertation, we specifically study how randomness and quantumness interact with space complexity. All are welcome to attend. Please see below for abstract. In the field of computational complexity theory, we study the power and limits of different computational resources and the interplay between them. The constraints on space complexity provide a natural and interesting setting, that is often more tractable than the time-restricted counterparts. In this dissertation, we specifically study how randomness and quantumness interact with space complexity. Our results consist of two parts. In the first part, we present our algorithmic results. We show that randomness used for BPL algorithms can be reduced to logarithmic with the access to untrusted random bits. Consequentially, every BPL algorithm can be certifiably derandomized using presumably hard functions. For quantum computing, we show how to eliminate intermediate measurement in logspace quantum circuits, and simulate general quantum algorithms in BQL with only unitaries. In the second part, we present our lower bound results. For decision problems, we propose the coupon-collector model where one receives random coordinates of the input, and prove a quadratic time-space tradeoff lower bound in the model. For computing multi-output functions, we prove the first polynomial separation between randomized and deterministic oblivious computation for total functions. And for learning, we prove an exponential time lower bound against classical-quantum hybrid learners with sub-quadratic classical memory and sublinear quantum memory.

1 0

Systems lunch with Charles E. Leiserson, tomorrow May 25 at 12:00pm
by Emily C. Lawrence 24 May '23

24 May '23

Systems lunch g uest speaker Charles E. Leiserson t omorrow @ 12noon in CS 105 with food provided. Speaker: Charles E. Leiserson, Professor of Computer Science and Engineering at MIT CSAIL Title: The Resurgence of Software Performance Engineering Abstract: Today, most application developers write code without much regard for how quickly it will run. Moreover, once the code is written, it is rare for it to be reengineered to run faster. But the end of Moore's Law has instigated a resurgence of interest in software performance engineering, the art/science of making code run fast. Moore's Law is the technology trend that has, until recently, relentlessly doubled the number of transistors on a semiconductor chip every two years. With the attenuation of this major source of computing performance, application programmers will increasingly find themselves turning to software performance engineering in order to develop innovative products and applications.

1 0

[LOCATION CHANGE] RE: Xiao Li will present her General Exam "Optical Optical Neural Network Achieved by Metalens Camera " on Tuesday, May 16, 2023 at 12:15 PM in 192 Nassau St & via Zoom.
by Louis Riehl 15 May '23

15 May '23

Please note, the location of this has moved to 192 Nassau St. (The Zoom link should still be active.) From: talks-bounces(a)lists.cs.princeton.edu <talks-bounces(a)lists.cs.princeton.edu> On Behalf Of Louis W. Riehl Sent: Monday, May 15, 2023 4:23 PM To: talks <talks(a)lists.cs.princeton.edu> Subject: [talks] Xiao Li will present her General Exam "Optical Optical Neural Network Achieved by Metalens Camera " on Tuesday, May 16, 2023 at 12:15 PM in 192 Nassau St & via Zoom. Xiao Li will present her General Exam "Optical Optical Neural Network Achieved by Metalens Camera" on Tuesday, May 16, 2023 at 12:15 PM in 192 Nassau St & via Zoom. Zoom Link: https://princeton.zoom.us/j/6770732042 Committee Members: Felix Heide (advisor), Szymon Rusinkiewicz, Jason Fleischer Abstract: The explosive growth of computation and energy cost of artificial intelligence has spurred strong interests in new computing modalities in lieu of conventional electronic processors. Photonic processors that execute operations using photons instead of electrons, have promised to enable optical neural networks with ultra-low latency and power consumption. Existing optical neural networks, limited by the underlying network designs, have achieved image recognition accuracy much lower than state-of-the-art electronic neural networks. In this work, we close this gap by introducing a large-kernel spatially-varying convolutional neural network learned via low-dimensional reparameterization techniques. Such a network possesses superior representation capability and can be naturally implemented by wave optics. We experimentally instantiate the network with a compact optical system that consists of an array of metasurface devices designed to induce angle-dependent responses. Combined with an extremely lightweight electronic backend with no more than 1K parameters, we are developing a nanophotonic neural network that can potentially outperform the first modern digital neural network -- AlexNet with 61M parameters, on the blind test classification accuracy on CIFAR-10 dataset, bringing optical neural network into modern deep learning era. Reading List: https://docs.google.com/document/d/1FOSU9a1SpHoamck8aYtqsf0Akb8fThxNwPBYHan… Everyone is invited to attend the talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Louis Riehl Graduate Administrator Computer Science Department, CS213 Princeton University (609) 258-8014

1 0

Xiao Li will present her General Exam "Optical Optical Neural Network Achieved by Metalens Camera " on Tuesday, May 16, 2023 at 12:15 PM in CS 301 & via Zoom.
by Louis W. Riehl 15 May '23

15 May '23

Xiao Li will present her General Exam "Optical Optical Neural Network Achieved by Metalens Camera" on Tuesday, May 16, 2023 at 12:15 PM in CS 301 & via Zoom. Zoom Link: [ https://princeton.zoom.us/j/6770732042 | https://princeton.zoom.us/j/6770732042 ] Committee Members: Felix Heide (advisor), Szymon Rusinkiewicz, Jason Fleischer Abstract: The explosive growth of computation and energy cost of artificial intelligence has spurred strong interests in new computing modalities in lieu of conventional electronic processors. Photonic processors that execute operations using photons instead of electrons, have promised to enable optical neural networks with ultra-low latency and power consumption. Existing optical neural networks, limited by the underlying network designs, have achieved image recognition accuracy much lower than state-of-the-art electronic neural networks. In this work, we close this gap by introducing a large-kernel spatially-varying convolutional neural network learned via low-dimensional reparameterization techniques. Such a network possesses superior representation capability and can be naturally implemented by wave optics. We experimentally instantiate the network with a compact optical system that consists of an array of metasurface devices designed to induce angle-dependent responses. Combined with an extremely lightweight electronic backend with no more than 1K parameters, we are developing a nanophotonic neural network that can potentially outperform the first modern digital neural network -- AlexNet with 61M parameters, on the blind test classification accuracy on CIFAR-10 dataset, bringing optical neural network into modern deep learning era. Reading List: [ https://docs.google.com/document/d/1FOSU9a1SpHoamck8aYtqsf0Akb8fThxNwPBYHan… | https://docs.google.com/document/d/1FOSU9a1SpHoamck8aYtqsf0Akb8fThxNwPBYHan… ] Everyone is invited to attend the talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Louis Riehl Graduate Administrator Computer Science Department, CS213 Princeton University (609) 258-8014

1 0

Christina Shatford will present her General Exam "Simultaneous Pattern and Detector Optimization for Visual Tags" on Thursday, May 18, 2023 at 3:00 PM in CS 402.
by Louis W. Riehl 15 May '23

15 May '23

Christina Shatford will present her General Exam "Simultaneous Pattern and Detector Optimization for Visual Tags" on Thursday, May 18, 2023 at 3:00 PM in CS 402. Committee Members: Szymon Rusinkiewicz (advisor), Ryan Adams, Olga Russakovsky Abstract: Accurate and robust object localization has been a long studied problem in computer vision. In this work, I present a new approach for localizing visual tags in images. Instead of optimizing a detector to locate a tag with a static pattern, this approach involves the simultaneous optimization of both the detector and the pattern of the visual tag. I will show how this joint learning leads to increased localization accuracy when compared to only training the detector and using a QR code or AprilTag, two standard static tags. In addition, I will discuss how pivoting away from tags in general, to an approach that uses steganography inspired techniques to hide a payload in the spatial domain of images, has its own host of useful applications. Reading List: [ https://docs.google.com/document/d/1_h9vNeeefjGkkD1FueUpRXBuLvTfGZrR2r6eX46… | https://docs.google.com/document/d/1_h9vNeeefjGkkD1FueUpRXBuLvTfGZrR2r6eX46… ] Everyone is invited to attend the talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Louis Riehl Graduate Administrator Computer Science Department, CS213 Princeton University (609) 258-8014

1 0

Alexander Wettig will present his General Exam "Towards a Better Understanding of Language Pre-training and Fine-tuning" on Thursday, May 18, 2023 at 3:00 PM in FC 114 and via zoom.
by Louis W. Riehl 15 May '23

15 May '23

Alexander Wettig will present his General Exam "Towards a Better Understanding of Language Pre-training and Fine-tuning" on Thursday, May 18, 2023 at 3:00 PM in FC 114 and via zoom. Zoom link: [ https://princeton.zoom.us/j/93571660087 | https://princeton.zoom.us/j/93571660087 ] Committee Members: Danqi Chen (advisor), Karthik Narasimhan, Sanjeev Arora Abstract: The paradigm of pre-training and fine-tuning has become a cornerstone in Natural Language Processing (NLP) and has achieves state-of-the-art performance on a wide range of tasks. In this talk, we will delve into key aspects of masked language model (MLM) pre-training and fine-tuning dynamics. In the first part, we will challenge the conventional wisdom surrounding the masking rate in MLM pre-training. Traditionally, a 15% masking rate has been widely adopted, but we show that this is not universally optimal, and 40% can outperform 15% under an efficient pre-training recipe. Surprisingly, even an 80% masking rate can still maintain 95% fine-tuning performance and acquire non-trivial linguistic features. We explore how the masking rate depends on the model size and the masking strategies, and shed light on the distinct effects of increasing the masking rate on task difficulty and optimization. In the second part, we will investigate whether kernel-based dynamics can describe the fine-tuning dynamics of a pre-trained language models, particularly in the few-shot settings. Inspired by the Neural Tangent Kernel (NTK), our analysis characterizes the conditions under which gradient features can solve the fine-tuning updates. We conduct experiments across 14 NLP tasks and demonstrate that formulating the downstream task as a masked word prediction problem through prompting often induces kernel-based dynamics during fine-tuning. The kernel view also provides an explanation for the success of parameter-efficient subspace-based fine-tuning methods. Reading List: [ https://docs.google.com/document/d/1HCyyShO_2ilodDbv9ibG2_84m3tkvatKHOlavLo… | https://docs.google.com/document/d/1HCyyShO_2ilodDbv9ibG2_84m3tkvatKHOlavLo… ] Everyone is invited to attend the talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Louis Riehl Graduate Administrator Computer Science Department, CS213 Princeton University (609) 258-8014

1 0

Alexander Raistrick will present his General Exam "Procedural Synthetic Data for Computer Vision" on Wednesday, May 17, 2023 at 3:00 PM in CS 301.
by Louis W. Riehl 12 May '23

12 May '23

Alexander Raistrick will present his General Exam "Procedural Synthetic Data for Computer Vision" on Wednesday, May 17, 2023 at 3:00 PM in CS 301. Committee Members: Jia Deng (advisor), Szymon Rusinkiewicz, Felix Heide Abstract: Data, especially large scale labeled data, has been a critical driver of progress in computer vision. At the same time, many tasks remain starved of high-quality data. Synthetic data from computer graphics is a promising solution to this data challenge, but sees limited use, which we hypothesize is due to limited diversity of assets. We propose a synthetic data generator which can produce infinite photorealistic 3D scenes of the natural world. Our system is entirely procedural: every asset, from shape to texture, is generated from scratch via randomized mathematical rules. This results in a limitless variety of 3D assets, with rich compositionality and pixel-level 3D detail. Moreover, it means that all assets are original, relying on no external source, and can be released for free as open source code. We provide such procedural rules for a wide range of natural objects and scenes, including plants, animals, terrain and lighting. Procedural modeling requires significant programming effort, and generating full scenes poses a large computational challenge. To this end, we provide tools and frameworks to accelerate procedural rule creation, and enable large-scale rendering of complex procedurally generated scenes. In all, anyone can freely use our system to generate unlimited high-quality training data for a wide range of computer vision tasks, including object detection, semantic segmentation, optical flow and 3D reconstruction. We expect this to be a useful tool for computer vision research and beyond. Reading List: [ https://docs.google.com/document/d/1N5spwmoIOqaErKy4X0B4l3TvM3m8S6rhGSRHFYz… | https://docs.google.com/document/d/1N5spwmoIOqaErKy4X0B4l3TvM3m8S6rhGSRHFYz… ] Everyone is invited to attend the talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Louis Riehl Graduate Administrator Computer Science Department, CS213 Princeton University (609) 258-8014

1 0

Jihoon Chung will present his General Exam "Enabling Detailed Action Recognition Evaluation Through Video Dataset Augmentation" on Wednesday, May 17, 2023 at 10:15 AM in CS 302 .
by Louis W. Riehl 12 May '23

12 May '23

Jihoon Chung will present his General Exam "Enabling Detailed Action Recognition Evaluation Through Video Dataset Augmentation" on Wednesday, May 17, 2023 at 10:15 AM in CS 302 . Committee Members: Olga Russakovsky (advisor), Jia Deng, Felix Heide Abstract: Human action recognition is the task of automatically classifying a video according to the action of the person depicted in the video. Despite the overall high accuracy on current benchmarks, it is well-known in the video understanding community that human action recognition models suffer from background bias, i.e., over-relying on scene cues in making their predictions. However, it is difficult to quantify this effect using existing evaluation frameworks. We introduce the Human-centric Analysis Toolkit (HAT), which enables the evaluation of learned background bias without the need for new manual video annotation. It does so by automatically generating synthetically manipulated videos and leveraging the recent advances in image segmentation and video inpainting. Using HAT we perform an extensive analysis of 74 action recognition models trained on the Kinetics dataset. We confirm that all these models focus more on the scene background than on the human motion; further, we demonstrate that certain model design decisions (such as training with fewer frames per video or using dense as opposed to uniform temporal sampling) appear to worsen the background bias. We open-source HAT to enable the community to design more robust and generalizable human action recognition models. Reading List: [ https://docs.google.com/document/d/1FQEQrX3HcM0E9bBPEcoVPSy19o7IV77KvyirxVd… | https://docs.google.com/document/d/1FQEQrX3HcM0E9bBPEcoVPSy19o7IV77KvyirxVd… ] Everyone is invited to attend the talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Louis Riehl Graduate Administrator Computer Science Department, CS213 Princeton University (609) 258-8014

1 0

Madelyne Xiao will present her General Exam "Machine Learning Approaches for Automated Misinformation Detection" on Tuesday, May 16, 2023 at 3:00 PM in Sherrerd 008 and via zoom.
by Louis W. Riehl 11 May '23

11 May '23

Madelyne Xiao will present her General Exam "Machine Learning Approaches for Automated Misinformation Detection" on Tuesday, May 16, 2023 at 3:00 PM in Sherrerd 008 and via zoom. Zoom link: [ https://princeton.zoom.us/my/madelyne.x | https://princeton.zoom.us/my/madelyne.x ] Committee Members: Jonathan Mayer (advisor), Arvind Narayanan, Andrew Guess Abstract: The spread of misinformation, disinformation, and false news on social media platforms in recent years has triggered a corresponding proliferation of automated misinformation detection methods. We present a systematic review and analysis of existing machine learning-driven approaches to the automated detection of misinformation. Across 248 well-cited papers in the field, we develop a taxonomy of five different information “scopes” for which numerous automated methods have been developed: claims, news articles, social media posts, users/authors, and whole websites. Having established this framework, we identify errors in ML-driven misinformation detection methods, with a focus on errors in corpus curation and model development. In particular, we find that methods that rely solely on textual features suffer from a lack of information context, such as reader response and source reputation. As a result, these methods are especially susceptible to text-specific dependencies (e.g., narrowly-defined subject domains and stylistic idiosyncrasies) that interfere with actual signals for misinformative content. Meanwhile, methods that consider extra-textual features (user behavior, social media platform-specific UI elements, knowledge networks) suffer from errors common to the “curse of dimensionality”: poor feature selection and mismanagement of data proxies. We support these findings with three replication studies, whose results highlight serious issues of data availability, reproducibility, and method generalizability within the existing misinformation detection literature. In view of the results of our literature analysis and replication studies, we conclude that existing ML-based methods for automated misinformation detection fall far short of what might be reasonably expected of methods deployable in a real world setting. As such, we make recommendations for proactive misinformation interventions beyond automated ML detection methods. Reading List: [ https://docs.google.com/document/d/1J80hwND6Jiw29ohiuEizjT7AchNNOtZFLH2ySTE… | https://docs.google.com/document/d/1J80hwND6Jiw29ohiuEizjT7AchNNOtZFLH2ySTE… ] Everyone is invited to attend the talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Louis Riehl Graduate Administrator Computer Science Department, CS213 Princeton University (609) 258-8014

1 0