Event Archive

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.

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.

Please 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.

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.

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.

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.

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.

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.

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.  

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.

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?

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!  

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.

A 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.

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.

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.

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.

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.

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?

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.