Ομιλία με θέμα: Minimizing Information for Inference: Structural and Noisy Query Models, Charalampos Tsourakakis, RelationalAI and Boston University, 8/9/2025, 12:00, K206
8 Σεπτεμβρίου@12:00 μμ-2:00 μμ
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.
Newsletter
Το Πανεπιστήμιο Κρήτης στα 40 χρόνια λειτουργίας του έχει αναδειχθεί σε ένα έντονα εξωστρεφές και καινοτόμο εκπαιδευτικό και ερευνητικό Ίδρυμα με σημαντικές επιστημονικές διακρίσεις και ξεχωριστή παρουσία στις διεθνείς κατατάξεις.
Χρήσιμοι Σύνδεσμοι
Copyright © 2024 – Με την υποστήριξη της Μ.Ψ.Δ.
