Upcoming Events

Digital contact-tracing is a tantalizing new tool for helping governments and public-health agencies slow the spread of COVID-19. This talk will recount the history of the technology, outline its fundamental privacy-utility trade-offs, and describe Washington State's experience deploying Apple and Google's Exposure Notifications system.

Consider the problem of computing the majority of a stream of n i.i.d. uniformly random bits. This problem, known as the coin problem, is central to a number of counting problems in different data stream models. We show that any streaming algorithm for solving this problem with large constant advantage (over the uniform distribution) must use Ω(log n) bits of space. Previously, it was known that computing the majority on every input with a constant probability takes Ω(log n) space.

Algorithmic recommendation systems impact the choices of millions of consumers daily; these systems exist for a wide variety of markets, including both consumable and durable goods, as well as digital and physical goods. After a recommendation system is in place, it will need to be periodically updated to incorporate new users, new items, and new observed interactions between users and items. These observed data, however, are algorithmically confounded: they are the result of a feedback loop between human choices and the existing algorithmic recommendation system.

The generation of synthetic data is useful in multiple aspects, from testing applications to benchmarking to privacy preservation. Generating the links between relations, subject to cardinality constraints (CCs) and integrity constraints(ICs) is an important aspect of this problem.

FOCS 2020, the IEEE Symposium on Foundations of Computer Science, is the flagship conference sponsored by the IEEE Computer Society Technical Committee on the Mathematical Foundations of Computing (TCMF) and covers a broad range of theoretical computer science as you can see in the Program and in the Accepted Papers. FOCS is held annually and is hosted virtually in 2020 by Duke!