CS Colloquium Series @ UCY

Department of Computer Science - University of Cyprus

The Department of Computer Science at the University of Cyprus holds research colloquiums and social hours approximately once weekly. All university students, faculty, and staff are invited to attend. Notifications about new and upcoming events are automatically disseminated to a variety of institutional lists.

If you don't receive these notifications, but want to get informed about upcoming colloquium announcements, you can do the following:

List RSS Directions

Colloquium Coordinator: Demetris Zeinalipour

Colloquium: Optimal learning of joint alignments, Dr. Charalampos E. Tsourakakis (Boston University, USA), Wednesday, December 11, 2019, 10:00-11:00 EET.

The Department of Computer Science at the University of Cyprus cordially invites you to the Colloquium entitled:

Optimal learning of joint alignments

Speaker: Dr. Charalampos E. Tsourakakis Affiliation: Boston University, USA Category: Colloquium Location: Room 148, Faculty of Pure and Applied Sciences (FST-01), 1 University Avenue, 2109 Nicosia, Cyprus (directions) Date: Wednesday, December 11, 2019 Time: 10:00-11:00 EET Host: Dr. Demetris Zeinalipour (dzeina-AT-cs.ucy.ac.cy) URL: https://www.cs.ucy.ac.cy/colloquium/index.php#cs.ucy.2019.tsourakakis

Abstract:
We consider the following problem, which is useful in applications such as joint image and shape alignment. The goal is to recover n discrete variables $g_i \in \{0, \ldots, k-1\}$ (up to some global offset) given noisy observations of a set of their pairwise differences $\{g_i - g_j \bmod k\}$; specifically, with probability $\frac{1}{k}+\delta$ for some $\delta > 0$ one obtains the correct answer, and with the remaining probability one obtains a uniformly random incorrect answer. We consider a learning-based formulation where one can perform a query to observe a pairwise difference, and the goal is to perform as few queries as possible while obtaining the exact joint alignment. We provide an easy-to-implement, time efficient algorithm that performs $O(n \lg n/\delta^2 k)$ queries, and recovers the joint alignment with high probability. We also show that our algorithm is optimal. This work improves significantly work of Chen and Candes, who view the problem as a constrained principal components analysis problem that can be solved using the power method. Our approach is simpler both in the algorithm and the analysis, and provides additional insights into the problem structure. Finally, experimentally our algorithm performs well compared to the algorithm of Chen and Candes both in terms of accuracy and running time. Joint work with Kasper Green Larsen and Michael Mitzenmacher

Short Bio:
Babis Tsourakakis is an assistant professor in computer science at Boston University and a research associate at Harvard. Tsourakakis obtained his PhD in Algorithms, Combinatorics and Optimization at Carnegie Mellon under the supervision of Alan Frieze, was a postdoctoral fellow at Brown University and Harvard under the supervision of Eli Upfal and Michael Mitzenmacher respectively. Before joining Boston University, he worked as a researcher in the Google Brain team. He won a best paper award in IEEE Data Mining, has delivered three tutorials in the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, and has designed two graph mining libraries for large-scale graph mining, one of which has been officially included in Windows Azure. His research focuses on large-scale graph mining, and machine learning.

Recording: https://www.youtube.com/watch?v=P_JL8CBn2_E&t=56s

	Web: https://www.cs.ucy.ac.cy/colloquium/
	Mailing List: https://listserv.cs.ucy.ac.cy/mailman/listinfo/cs-colloquium
	RSS: https://www.cs.ucy.ac.cy/colloquium/rss.xml
	Calendar: https://www.cs.ucy.ac.cy/colloquium/schedule/cs.ucy.2019.tsourakakis.ics