Events

Filters
Export this event to calendar
iCal
RSS
RSS
Close X

Filter by:

Limit to events where the first date of the event:
Date range
Limit to events where the first date of the event:
Limit to events where the title matches:
Limit to events where the type is one or more of:
Limit to events tagged with one or more of:
Limit to events where the audience is one or more of:
Wednesday, August 15, 2018 1:30 pm - 1:30 pm EDT (GMT -04:00)

Master’s Thesis Presentation • Algorithms and Complexity — The Complexity of Network Design for s-t Effective Resistance

Pak Hay Chan, Master’s candidate
David R. Cheriton School of Computer Science

We consider a new problem of designing a network with small $s$-$t$ effective resistance. In this problem, we are given an undirected graph $G=(V,E)$ where each edge $e$ has a cost $c_e$ and a resistance $r_e$, two designated vertices $s,t \in V$, and a cost budget $k$.

Friday, August 17, 2018 1:00 pm - 1:00 pm EDT (GMT -04:00)

Master’s Thesis Presentation • Quantum Information and Computation — Concentration Bounds from Parallel Repetition Theorems: Symmetric Key

Taylor Hornby, Master’s candidate
David R. Cheriton School of Computer Science

This thesis contributes to two areas. The first is the study of parallel repetition theorems and concentration bounds for nonlocal games and quantum interactive proofs. 

We make the following contributions:

Wednesday, August 29, 2018 1:30 pm - 1:30 pm EDT (GMT -04:00)

Seminar • Algorithms and Complexity — Counting Subwords and Regular Languages

Finn Lidbetter, Master’s candidate
David R. Cheriton School of Computer Science

Let x and y be words. We consider the languages whose words z are those for which the numbers of occurrences of x and y, as subwords of z, are the same (resp., the number of x's is less than the number of y's, resp., is less than or equal). In this talk we will give a necessary and sufficient condition on x and y for these languages to be regular, and we show how to check this condition efficiently.