Upcoming Events

Approximating Maximum Independent Set for Rectangles in the Plane

Algorithms Seminar
Speaker Name
Joe Mitchell
Location
The talk will be virtual on Zoom.
Date and Time
-

Given a set ${\cal R}=\{R_1,\ldots,R_n\}$ of $n$ axis-aligned rectangles in the plane, the {\em maximum independent set of rectangles} (MISR) problem seeks a maximum-cardinality subset, ${\cal R}^*\subseteq {\cal R}$, of rectangles that are {\em independent}, meaning that any two rectangles of ${\cal R}^*$ are interior-disjoint. The MISR, which is known to be NP-hard, has geometric structure that enables approximation algorithms with far better performance than is known (or even possible) for maximum independent set in a general graph.

Google Durham and Cloud Networking

Duke Computer Science Colloquium
Speaker Name
Kamala Subramaniam
Location
The talk will be virtual on Zoom.
Date and Time
-

Learn from the Google Engineering Site Lead in Durham, North Carolina about Google Cloud's hyper growth plans in Durham for engineering, followed by an introduction to some of the problems Cloud Networking in Durham is solving at scale.

Using Cognitive Machine Learning to Build Safe and Secure Internet of Things Devices

ACM-W Distinguished Speaker
Speaker Name
Heena Rathore
Location
The talk will be virtual on Zoom.
Date and Time
-

Internet of Things devices, fueled by advancements in Artificial Intelligence (AI) and 5G, use sensors, processors, and communication devices to monitor and adapt to their operating environment. While experts opine that the IoT market is poised to grow at fast rates, there is a general agreement that such devices are prone to attacks, thereby impacting the safety and security of its operation.

Streaming Algorithms for Geometric Steiner Forest

Algorithms Seminar
Speaker Name
Robert Krauthgamer
Location
The talk will be virtual on Zoom.
Date and Time
-

I will discuss the Steiner forest problem in the Euclidean plane, where the input is a multiset of points, partitioned into k color classes,  and the goal is to find a minimum-cost Euclidean graph G such that every color class is connected. We study this problem in dynamic streams,  where the input is provided by a stream of insertions and deletions of colored points from the discrete grid [\Delta]^2. 

Weaving the Next Web with Spatial Computing

Duke Electrical Computer Engineering Colloquium
Speaker Name
Anthony Rowe
Location
Zoom Registration Link: https://duke.zoom.us/meeting/register/tJYufuCvrTgoHtAcqUYZzXTySFGE1iTC6nE9
Date and Time
-

Many have predicted the future of the Web to be the integration of Web content with the real-world through technologies such as augmented reality. This overlay of virtual content on top of the physical world, called the Spatial Web (in different contexts AR Cloud, MetaVerse, Digital Twin), holds promise for dramatically changing the Internet as we see it today, and has broad applications.

Discrete Voronoi Refinement

Algorithms Seminar
Speaker Name
Don Sheehy
Location
The talk will be virtual on Zoom.
Date and Time
-

Voronoi and Delaunay refinement are standard algorithmic techniques used in surface reconstruction and mesh generation in Euclidean spaces.  For point sets, the resulting output is a triangulation of a superset of the points in which every triangle has angles larger than a user-defined constant.  This guarantees that the total complexity is linear in the number of points (even in dimensions greater than two).  These simple refinement heuristics are local updates that naturally produce asymptotically optimal size outputs.  In this talk, I will discuss how one can translate