ΘΕΜΑ: Ομιλία με θέμα: Minimizing Information for Inference: Structural and Noisy Query Models, Charalampos Tsourakakis, RelationalAI and Boston University, 8/9/2025, 12:00, K206
ΑΠΟΣΤΟΛΕΑΣ: Kalaitzaki Rena rena@xxxxxxxxxx
Title: Minimizing Information for Inference: Structural and Noisy Query Models
Speaker: Charalampos Tsourakakis, RelationalAI and Boston University
Location: “K206, Computer Science Department, University of Crete”
Date: Monday, September 8, 2025
Time: 12:00
zoom: https://uoc-gr.zoom.us/j/85149487613
Host: Yannis Tollis
Abstract:
We study two complementary paradigms of inference under limited information: one governed by deterministic structural constraints, the other by noisy, probabilistic feedback. In the first setting, we introduce the Targeted Least Cardinality Candidate Key (TCAND) problem, which seeks the smallest set of variables determining a target set under a given system of functional dependencies. This problem generalizes the long-standing classical problem of candidate key discovery. We shed new light on its computational complexity and approximability, highlighting structural challenges that arise even in natural generalizations.
In contrast, the second problem addresses joint alignment under a faulty oracle: given noisy observations of pairwise differences between discrete variables, the goal is to recover the global alignment using as few queries as possible. We design a time-optimal, non-adaptive algorithm that provably matches lower bounds on query complexity and significantly simplifies and improves upon a recent approach by Chen and Candès. Our method offers both theoretical optimality and practical simplicity, advancing the state of the art in alignment under noise.
Together, these works examine the interplay between structure, noise, and limited information access in inference problems—whether in minimizing attribute sets implied by functional dependencies or in learning latent variables through constrained, noisy observations.
This is joint work with Kasper Green Larsen, Michael Mitzenmacher, Vasileios Nakos and Hung Ngo.
Bio: Dr. Charalampos Tsourakakis earned his Ph.D. from the Algorithms, Combinatorics, and Optimization (ACO) program at Carnegie Mellon University, and subsequently held postdoctoral positions at Harvard and Brown Universities. He holds a Diploma in Electrical and Diploma Engineering from the National Technical University of Athens and a Master of Science from the Machine Learning Department at Carnegie Mellon University. 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. Currently, he is building a state-of-the-art knowledge graph system at RelationalAI, where he contributes to core innovations in query optimization, relational inference, and graph-native computation for enterprise-scale applications. His research focuses on the design of scalable algorithms and machine learning methods for analyzing large-scale datasets, with emphasis on network data, and applications across data science, finance, and computational social science.
--
Καλαϊτζάκη Ειρήνη
Προϊσταμένη Γραμματείας
Τμήμα Επιστήμης Υπολογιστών
Πανεπιστήμιο Κρήτης
Τηλ:2810393505
Rena Kalaitzaki
Head of the Secretariat
Computer Science Department
University of Crete
Tel: +302810393505
ΠΡΟΕΙΔΟΠΟΙΗΣΗ ΕΜΠΙΣΤΕΥΤΙΚΟΤΗΤΑΣ – ΑΠΟΠΟΙΗΣΗ ΕΥΘΥΝΗΣ (Confidentiality Warning - Disclaimer):
https://www.uoc.gr/DPO/EmailDisclaimer.pdf
"Οι πληροφορίες σε αυτό το ηλεκτρονικό μήνυμα και σε τυχόν συνημμένα αρχεία είναι εμπιστευτικές και προορίζονται αποκλειστικά
για την προσοχή και τη χρήση των παραληπτών. Αν δεν είστε ο παραλήπτης ή ο υπεύθυνος για την παράδοσή του στον παραλήπτη,
παρακαλώ ειδοποιήστε τον αποστολέα επειδή δεν έχετε εξουσιοδότηση και δεν πρέπει να αποκαλύψετε, να αντιγράψετε, να διανείμετε
ή να διατηρήσετε αυτό το μήνυμα ή οποιοδήποτε μέρος του.
The information in this e-mail and in any attachments is confidential and intended solely for the attention and use of the named
addressee(s). If you are not the intended recipient, or a person responsible for delivering it to the intended recipient,
please notify the sender because you are not authorized to and must not disclose, copy, distribute, or retain this message
or any part of it."