Event Archive

Random graph matching at Otter's tree-counting threshold via counting chandeliers

Algorithms Seminar
Speaker Name
Sophie Yu
Location
LSRC D344 or Zoom https://duke.zoom.us/j/96428761111
Date and Time
-

Given a pair of graphs, the problem of graph matching or network alignment refers to finding the underlying vertex correspondence that maximally aligns the edges. This is a ubiquitous problem arising in a variety of applications across diverse fields such as network privacy, computational biology, computer vision, and natural language processing. Graph matching is an instance of the notoriously difficult quadratic assignment problem (QAP), which is NP-hard to solve or approximate.

Online Learning and Bandits with Queried Hints

Algorithms Seminar
Speaker Name
Kamesh Munagala
Location
LSRC D344 or Zoom
Date and Time
-

We consider the classic online learning and stochastic multi-armed bandit (MAB) problems, when at each step, the online policy can probe and find out which of a small number (k) of choices has better reward (or loss) before making its choice. In this model, we derive algorithms whose regret bounds have  exponentially better dependence on the time horizon compared to the classic regret bounds. In particular, we show that probing with k=2 suffices to achieve time-independent regret bounds for online linear and convex optimization.

Computer Science Department Holiday Party

Special Event
Location
Karsh Alumni and Visitor Center
Date and Time
-

Duke CS Holiday Party 2022Please join us for the Computer Science Department's holiday party and annual meeting. This will be the first holiday celebration held since 2019! We hope you will join us, meet new people in the Department, and reacquaint yourselves with friends and colleagues.

Choiceless Computation

Algorithms Seminar
Speaker Name
Benjamin Rossman
Location
LSRC D344 or Zoom
Date and Time
-

In computer science, we are not accustomed to thinking of “choice” as a computational resource, alongside time, space, randomness, etc.  This is because, in standard model of computation (Turing machines, circuits, etc.), discrete structures such as graphs are encoded by strings.  Any encoding necessarily imposes a linear order on elements (and hence a choice function on subsets), which algorithms are free to exploit.  Consider, for example, the augmenting paths algorithm for bipartite matching, which greedily picks the *first* unmatched vertex at each step.

The Laws of Boolean Algebra

Duke Computer Science Colloquium
Speaker Name
Connor McMahon
Location
LSRC D106
Date and Time
-

Boolean algebra is a foundational tool of hardware design and is often one of the first topics introduced to students in their hardware courses. This mock lecture will introduce the laws of Boolean algebra through the use of collaborative examples which incrementally culminate towards the reduction of a complex Boolean expression. In the second half of the talk, Connor will discuss her teaching philosophy and future teaching plans.

Decoding Graduate CS Programs: Duke-UNC-NCSU Collaborative Event

Special Event
Speaker Name
Duke, UNC, and NCSU Computer Science Graduate Programs Faculty, PhD students, & staff
Location
Zoom - Registration required
Date and Time
-


Register Now
Interested in Computer Science graduate school? Have questions? Faculty, PhD students, and representatives from the computer science programs at Duke, NC State, and UNC will come together to help demystify the grad school process. Hear first-hand accounts about applying to graduate schools, path to graduation, and career opportunities.

Revenue maximization with non-obligatory inspection

Algorithms Seminar
Speaker Name
Ali Makhdoumi
Location
LSRC D344 or Zoom
Date and Time
-

We consider the problem of selling a single item to n unit-demand buyers to maximize revenue, where the buyers' values are independently distributed (not necessarily identical) according to publicly known distributions but unknown to the buyers themselves, with the option of allowing buyers to inspect the item at a cost. We present an approximation mechanism that achieves 1/2 of the optimal revenue. The proposed mechanism generalizes to the case of selling k units of an item to unit-demand buyers, obtaining 1-1/\sqrt{k+3} of the optimal revenue in expectation.

Recipes for ResistanCSe

Identity & Computing Lecture Series
Speaker Name
The Papaya Project
Location
Virtual, registration is required
Date and Time
-

CS and CSEd are fields with a hegemonic center of power, making it especially difficult for those who identify as Black, Indigenous, disabled, or otherwise minoritized to ‘make their mark’ when they have less access to the social capital necessary for doing so. Those at the center of power can provide significant contributions to the field, but their continued recognition as “the only” speakers and experts contributes to the continued inaccessibility of social capital for minoritized individuals.

How to approach debugging; Fostering student engagement using active learning and DEI practices

Duke Computer Science Colloquium
Speaker Name
Yesenia Velasco
Location
LSRC D106
Date and Time
-

Promoting student engagement and inclusion is a complex and multi-dimensional process. Numerous research studies have shown that active learning techniques drive inclusive teaching by promoting multiple engagement methods that benefit all students, including those from marginalized groups. Furthermore, this student-centered approach to teaching can be integrated at all levels of the Computer Science curriculum to promote higher-order thinking and skills.  

Theory for Generative Models

Duke Computer Science Colloquium
Speaker Name
Sitan Chen
Location
LSRC D106
Date and Time
-

Generative models like diffusion models and GANs have exploded in popularity as powerful ways of modeling real-world data and form the backbone of technologies like DALL-E 2. Yet when it comes to provable guarantees, we know very little about why these frameworks are so effective or how to articulate what it is they are accomplishing. In this talk I'll describe some recent progress in this direction.

Online Integer Covering in Random Order

Algorithms Seminar
Speaker Name
Gregory Kehne
Location
LSRC D344 or Zoom
Date and Time
-

Abstract: In online set cover, constraints are revealed one-at-a-time and must be satisfied upon their arrival. For adversarial instances and arrival orders, an algorithm due to Alon et al. obtains a competitive ratio of O(log m log n), and this is essentially the best possible. Is this separation from the O(log n) ratio attainable offline due to the adversarially chosen instance, the adversarial arrival order, or both?

Change of Base as a Change of Pace

Duke Computer Science Colloquium
Speaker Name
Kate O'Hanlon
Location
LSRC D106
Date and Time
-

Student engagement in courses is key; if you are not paying attention, you will not learn! In the first part of this talk, a mock lecture, we will cover change of base operations. Student feedback has indicated that change of base is helpful in multiple computer science courses, yet the topic can be done in a short time frame such as this. This portion will include discussion with your “classmates,” so be prepared to chat!  

Shading Languages and the Emergence of Programmable Graphics Systems

Triangle Computer Science Distinguished Lecturer Series
Speaker Name
Pat Hanrahan
Location
The talk will be virtual on Zoom.
Date and Time
-

A major challenge in using computer graphics for movies and games is to create a rendering system that can create realistic pictures of a virtual world. The system must handle the variety and complexity of the shapes, materials, and lighting that combine to create what we see every day. The images must also be free of artifacts, emulate cameras to create depth of field and motion blur, and compose seamlessly with photographs of live action.

Optimal Size Multiplicative Spanners of Weighted Graphs

Distinguished Computer Science Alumni Lecture
Speaker Name
Sandeep Sen
Location
LSRC D106
Date and Time
-

spanner is a sparse subgraph that preserves pairwise distances within some pre-specified dilation. We describe a simple randomized algorithm for constructing a family of optimal sized stretch 2k-1 spanner of weighted graphs that runs in linear expected time.  The underlying construction and techniques are quite elementary and accessible even to upper level undergraduate students. Joint work with Surender Baswana.

 

Medicine, Humanities, and Business Celebration

Special Event
Speaker Name
Dr. Quinn Wang
Location
Fitzpatrick Center Schiciano Auditorium
Date and Time
-

Dr. Quinn Wang, Co-Founder and CEO of Quadrant Eye will be speaking at Duke's Fall 2022 Medicine, Humanities, and Business (MHB) Celebration on Saturday, November 5th from 6pm-8pm in Penn Pavilion. Dr. Wang is a Duke and UCSF trained comprehensive ophthalmologist and Y-Combinator venture startup founder. She graduated from Duke University in 2010 with a BA in English Literature and with an MD from the Duke University School of Medicine in 2015. Dr.

Connecting Students to Computer Science

Duke Computer Science Colloquium
Speaker Name
Spencer Yoder
Location
LSRC D106
Date and Time
-

I will give a 25-minute mock lecture teaching recursion using an example algorithm which generates images of snowflakes. This lecture will be partially interactive and include group programming. I will then discuss the lack of connection in computer science education: between students and the material, between students and instructors, and between computer science and other disciplines. Finally, I will discuss how I intend to improve this connection as an educator at Duke.

Discovering “Interesting” Test Cases in Programming Assignments

Duke Computer Science Colloquium
Speaker Name
Ryan Patrick
Location
LSRC D106
Date and Time
-

A great deal of research has been done on generating hints designed to direct students towards correctly solving programming problems in introductory classes. Systems designed for that task operate on the assumption that the programming language that students use is predetermined and that the problems being solved can have their solutions segmented into defined way points. In more advanced classes, problems become complex; students are given more freedom; and proposed solutions become more varied.

Geometry of Bias Mitigation Techniques for Word Representations

Duke Computer Science Colloquium
Speaker Name
Jeff M. Phillips
Location
LSRC D106
Date and Time
-

Vectorized representation of textual data has revolutionized natural language processing, first with methods like Word2Vec and GloVe and then with contextual variants like BERT and RoBERTa. Similar representations are useful for learning on other structured data types like images, trajectories, business transactions, and many more. However, as these are trained on enormous quantities of real-world data -- in the case of language, large amounts of text from the internet, they encode some of the biases from that text.

Athena Seminar: Do Simpler Machine Learning Models Exist and How Can We Find Them?

Special Talk
Speaker Name
Cynthia Rudin
Location
Wilkinson 017 and Zoom - registration required
Date and Time
-

While the trend in machine learning has tended towards building more complicated (black box) models, such models are not as useful for high stakes decisions - black box models have led to mistakes in bail and parole decisions in criminal justice, flawed models in healthcare, and inexplicable loan decisions in finance. Simpler, interpretable models would be better. Thus, we consider questions that diametrically oppose the trend in the field: for which types of datasets would we expect to get simpler models at the same level of accuracy as black box models?

Provable Exploration in Bandit Problems: From Optimality to Efficiency

Duke Computer Science Colloquium
Speaker Name
Pan Xu
Location
LSRC D106
Date and Time
-

A bandit problem is a succinct mathematical formulation of sequential decision-making in an uncertain environment, where an agent learns to maximize its expected cumulative reward by repeatedly interacting with an unknown environment. At the core of any bandit algorithm lies the dilemma between exploiting the good actions it has learned in the past to obtain high rewards and exploring uncertain actions for making better decisions in the future.