Event Archive

Sensor arrays and multi-channel systems play a central role in the activities of everyday society.  Cell phones, tablets, and laptops are now commonly fitted with numerous sensors; and many commercial and defense systems such as communication base stations, satellites, airborne surveillance radars, and sea bottom-mounted passive sonars all use various types of sensors arrays.

In this talk we focus on ML aided Online Algorithms. Traditionally, online algorithms assume a pessimistic viewpoint i.e. worst-case scenario for the future. A popular line of recent research incorporates ML advice in the design of online algorithms to improve their performance. However, these works treat the Machine Learning paradigm as a black-box, and redesign online algorithms to take advantage of such predictions.

Synchronous consensus protocols, by definition, have a worst-case commit latency that depends on the bounded network delay. The notion of optimistic responsiveness was recently introduced to allow synchronous protocols to commit instantaneously when some optimistic conditions are met. In this work, we revisit this notion of optimistic responsiveness and present optimal latency results.

Duke TechConnect brings students and employers together for networking, education and connections. At TechConnect for fall 2020, employers will connect with Engineering and Computer Science students in a virtual networking environment powered by CareerEco.

We study a stochastic optimization problem called prophet inequalities, where a principal allocates items to agents arriving online, given only statistical knowledge about how much each agent values the items.  We give a framework for designing prophet inequalities for combinatorial welfare maximization.

Let P(k,n) denote the problem of computing the product of k n-by-n permutation matrices.  This problem is complete for complexity classes NC^1 when n = O(1) (Barrington’s Theorem) and Logspace when k = n.  A super-polynomial lower bound on the *formula complexity* of P(k,n) would separate NC^1 and Logspace (one of the major questions in theoretical computer science).  In this talk, I will discuss some recent results:

The min-cut problem in undirected graphs asks for a minimum (weight) subset of edges whose removal disconnects the graph. In the 1990s, Karger developed several randomized (Monte Carlo) algorithms for this problem, leading to an eventual running time bound of \tilde{O}(m). At the time, the best deterministic algorithms for the problem, from the early 1990s, were much slower and ran in \tilde{O}(mn) time. This led him to ask whether the min-cut problem can be solved in \tilde{O}(m) time deterministically as well.

Join Duke CS Professor of the Practice Nicki Washington and other panelists for this Center for Minorities and People with Disabilities in IT (CMD-IT) discussion from 2:30-3:30 pm EDT on Friday, August 7. Panelists will examine racial injustice from the perspective of Black professionals in computing, sharing their stories about overcoming racial injustices to get to where they are today. They will also share advice and insights about systemic changes needed for equity and inclusion.

Join us for an online expo to celebrate the results of over 180 talented Duke students who participated on projects in ccomputer science, big data, mobile app and web development this summer through summer projects in Computer Science, Data+, and Code+. Learn more about this event.

Registration Required:
Register Now

Join us for an online expo to celebrate the results of over 180 talented Duke students who participated on projects in ccomputer science, big data, mobile app and web development this summer through summer projects in Computer Science, Data+, and Code+. Learn more about this event.

Registration Required:
Register Now

Join us for an online expo to celebrate the results of over 180 talented Duke students who participated on projects in ccomputer science, big data, mobile app and web development this summer through summer projects in Computer Science, Data+, and Code+. Learn more about this event.

Registration Required:
Register Now

The recent emergence of new successful two-sided online platforms has transformed the concept of a marketplace. Numerous two-sided mechanism design problems are motivated by these platforms. There are unique features to a two-sided market, such as supply uncertainty and the need for ensuring budget balance, that make these problems particularly challenging. In this talk, we design models to capture the two-sidedness, identify the challenges, and use algorithmic techniques to solve these problems.

Given n red points and n blue points in d-dimensional space and a
distance function, the geometric bipartite matching problem is to find a
matching of red points to blue points, such that the sum of distances
between the matched pairs is minimized. The general graph problem,
minimum cost bipartite matching, can be solved in polynomial time using
the classical Hungarian algorithm, which leads to a cubic algorithm for
the geometric matching problem. We present several algorithms for

Query processing is an important problem in many research fields including database systems, data mining, and geometric computing. The goal is to preprocess input data into an index to efficiently answer queries. With the data sets becoming increasingly large and complex, queries are also becoming complex, therefore new challenging problems have emerged in the area of query processing. This talk focuses on two broad themes: data uncertainty and data summarization.

Learn from Dr. Kristin Stephens-Martinez how to:

• Design formative assessments

• Understand a wide variety of questions types

• Introduce formative assessments into your class

Dr. Stephens-Martinez will also share an example of her own process for designing formative assessments and how she uses it in her introductory computer science course.

• With widespread use of machine learning, there have been serious societal consequences from using black box models for high-stakes decisions, including flawed bail and parole decisions in criminal justice. Explanations for black box models are not reliable, and can be misleading.

Please register for this special seminar and the zoom link will be sent to you then.

Register Now

Temporal data is ubiquitous in our everyday life, but tends to be noisy and often exhibits transient patterns. To make better decisions with data, we must avoid jumping to conclusions based on certain particular query results or observations. Instead, a useful perspective is to consider "durability'', or, intuitively speaking, finding results that are robust and stand "the test of time''. This thesis studies durability queries on temporal data that return durable results efficiently and effectively.

The taxation principle guarantees that any single-agent mechanism can be interpreted as a menu-based mechanism (one that offers each buyer a menu: a mapping from their payment to their (expected) allocation) without loss of generality. What loss in welfare does one incur in designing multiagent menu-based mechanisms in prior-free environments? We study this question for general single-dimensional valuations and give tight characterizations of the loss in welfare as a function of natural parameters governing the evolution of value profile across rounds.