Computer Science Talks
Το Εργαστήριο Λογικής και Επιστήμης Υπολογισμών (Corelab) και το Εργαστήριο Υπολογιστικών Συστημάτων (CSLab), του Τομέα Τεχνολογίας Πληροφορικής και Υπολογιστών, της ΣΗΜΜΥ σας προσκαλούν σε μια σειρά ομιλιών από πέντε διακεκριμένους Έλληνες ερευνητές.
Οι ομιλίες αφορούν σημαντικές σύγχρονες ερευνητικές προκλήσεις στην Επιστήμη Υπολογιστών, και θα γίνουν την Τετάρτη 13 Ιανουαρίου 2021, 14:00 – 19:30, μέσω WebEx, στο link
σύμφωνα με το παρακάτω πρόγραμμα.
Η απευθείας μετάδοση θα είναι επίσης διαθέσιμη: YouTube Live Streaming Link: https://youtu.be/qncqpOn37to
14:00 – 15:00 Equilibrium Computation and the Foundations of Deep Learning
Constantinos Daskalakis, MIT
15:00 – 16:00 Designing and Deploying Secure and Efficient Distributed Ledgers at a Global Scale
Aggelos Kiayias, University of Edinburgh & IOHK
16:00 – 16:20 Σύντομο διάλειμμα
16:20 – 17:20 A Simple but Non-Convex Objective for Learning Linear Classifiers with Noise
Christos Tzamos, Univ. Wisconsin‐Madison
17:20 – 18:20 Tracking and Curing Epidemics with Uncertainty
Constantine Caramanis, Univ. Texas at Austin
18:20 – 19:20 Rethinking Operating System and Hardware Abstractions for Good and Evil
Dimitrios Skarlatos, CMU
19:20 – 19:30 Σύντομη συζήτηση
Περιλήψεις και Σύντομα Βιογραφικά Ομιλητών
- Τίτλος: Equilibrium Computation and the Foundations of Deep Learning
Περίληψη: Deep Learning has recently yielded important advances in single-agent learning challenges, much of that progress being fueled by the empirical success of gradient descent and its variants in computing local optima of non-convex optimization problems. In multi-agent learning applications, the role of single-objective optimization is played by equilibrium computation, yet our understanding of its complexity in settings that are relevant for Deep Learning remains sparse. In this talk we focus on min-max optimization of nonconvex-nonconcave objectives, which has found applications in GANs, and other adversarial learning problems. Here, not only are there no known gradient-descent based methods converging to even local and approximate min-max equilibria, but the computational complexity of identifying them remains poorly understood. We show that finding approximate local min-max equilibria of Lipschitz and smooth objectives requires a number of queries to the function and its gradient that is exponential in the relevant parameters, in sharp contrast to the polynomial number of queries required to find approximate local minima of non-convex objectives. Our oracle lower bound is a byproduct of a complexity-theoretic result showing that finding approximate local min-max equilibria is computationally equivalent to finding Brouwer fixed points, and Nash equilibria in non zero-sum games, and thus PPAD-complete.
Minimal complexity theory knowledge will be assumed in the talk. Joint work with Stratis Skoulakis and Manolis Zampetakis
Bio: Constantinos (a.k.a. “Costis”) Daskalakis is a Professor of Electrical Engineering and Computer Science at MIT. He holds a Diploma in Electrical and Computer Engineering from the National Technical University of Athens, and a PhD in Electrical Engineering and Computer Science from UC Berkeley. He works on Computation Theory and its interface with Game Theory, Economics, Probability Theory, Machine Learning and Statistics. He has resolved long-standing open problems about the computational complexity of Nash equilibrium, and the mathematical structure and computational complexity of multi-item auctions. His current work focuses on high-dimensional statistics and learning from biased, dependent, or strategic data. He has been honored with the ACM Doctoral Dissertation Award, the Kalai Prize from the Game Theory Society, the Sloan Fellowship in Computer Science, the SIAM Outstanding Paper Prize, the Microsoft Research Faculty Fellowship, the Simons Investigator Award, the Rolf Nevanlinna Prize from the International Mathematical Union, the ACM Grace Murray Hopper Award, and the Bodossaki Foundation Distinguished Young Scientists Award.
- Τίτλος: Designing and Deploying Secure and Efficient Distributed Ledgers at a Global Scale
Περίληψη: Τhe advent of blockchain protocols brought to light a number of applications that could be facilitated by large scale consensus systems. At the same time a number of significant challenges were put forth in terms of incentives, scalability, energy efficiency, privacy, and the relevant threat model that such protocols may be proven secure for. In this talk I will give an overview of recent and ongoing research in the area of designing distributed ledgers at a global scale including the Ouroboros proof of stake blockchain protocol as well as other related constructions aiming to improve the interoperability, privacy and the incentive structure of distributed ledgers.
Bio: Aggelos Kiayias is chair in Cyber Security and Privacy and director of the Blockchain Technology Laboratory at the University of Edinburgh. He is also the Chief Scientist at blockchain technology company IOHK and an associate professor at the National and Kapodistrian University of Athens. His research interests are in computer security, information security, applied cryptography and foundations of cryptography with a particular emphasis in blockchain technologies and distributed systems, e-voting and secure multiparty protocols as well as privacy and identity management. He has been the recipient of an ERC fellowship, a Marie Curie fellowship, an NSF Career Award, and a Fulbright Fellowship. He holds a Ph.D. from the City University of New York, he was a graduate student in ECE at NTUA and has an undergraduate degree in Mathematics from the University of Athens. He has over 150 publications in journals and conference proceedings in the area. He has served as the program chair of the Cryptographers’ Track of the RSA conference in 2011 and the Financial Cryptography and Data Security conference in 2017, as well as the general chair of Eurocrypt 2013. He also served as the program chair of Real World Crypto Symposium 2020 and the Public-Key Cryptography Conference 2020.
- Τίτλος: A Simple but Non-Convex Objective for Learning Linear Classifiers with Noise
Περίληψη: We study the problem of learning linear classifiers with noise in the distribution-specific PAC model. We give the first computationally efficient algorithm for learning under Massart noise with respect to a broad family of distributions, including log-concave distributions. Moreover, we show that our algorithm works even under adversarial label noise, matching the best-possible misclassification error guarantees of O(OPT)+ε in polynomial time. Our approach is simple and practical: We identify a smooth non-convex surrogate loss whose approximate stationary points give near optimal solutions. Interestingly, non-convexity is inherently necessary. We show that any convex surrogate, like the commonly used logistic loss, results in suboptimal error guarantees.
Bio: Christos Tzamos is an Assistant Professor in the Department of Computer Sciences at University of Wisconsin-Madison and a member of the Theory of Computing group. His research interests lie in the interface of Theory of Computation with Economics and Game Theory, Machine Learning, Statistics and Probability Theory. He completed his PhD in the Theory of Computation group of MIT advised by Costis Daskalakis. He studied Electrical and Computer Engineering at NTUA before his PhD, and afterwards he was a postdoctoral researcher at Microsoft Research (New England) working on Mechanism Design, Algorithms and Machine Learning. He is the recipient of a Simons Foundation award, the George M. Sprowls award, the best paper and the best student paper award in EC 2013 and of an outstanding paper award in NeurIPS 2019.
- Τίτλος: Tracking and Curing Epidemics with Uncertainty
Περίληψη: Epidemic processes can model anything that spreads. As such, they are a useful tool for studying not only human diseases, but also network attacks, the propagation of real or fake news, the spread of viral tweets, neural spikes in the brain, and other processes. In this talk, we're interested in epidemics spreading on an underlying graph.
The study of epidemics is the study of high dimensional probability on combinatorial structures. Important tools include random graph processes, and concentration inequalities for these, as well as important combinatorial properties of graphs. The first part of this talk will be a tutorial introduction to some of these models, as well as some of the tools that are used. In the second part of the talk, we'll move to some recent results from my group that have centered on what we can do in the face of uncertainty.
Currently, most theoretical research in this field assumes some form of perfect observation of the epidemic process. This is an unrealistic assumption for many real-life applications, as the recent COVID-19 pandemic tragically demonstrated: data are scarce, delayed, and/or imprecise for human epidemics, and symptoms may appear in a non-deterministic fashion and order of infection - if they appear at all. We discuss positive and negative results that arise as a consequence of uncertainty, and point to several open questions.
Bio: Constantine Caramanis is a Professor in the ECE department of The University of Texas at Austin. He received a PhD in EECS from The Massachusetts Institute of Technology, and an AB in Mathematics from Harvard University. He received the NSF CAREER award in 2011. His current research interests focus optimization and machine learning, high dimensional statistics, robustness, and stochastic networks.
- Τίτλος: Rethinking Operating System and Hardware Abstractions for Good and Evil
Περίληψη: Current hardware and operating system abstractions were conceived at a time when we had minimal security threats, scarce compute and memory resources, and limited numbers of users. These assumptions are not true today. On one hand, attacks such as Spectre and Meltdown have shown that current hardware is plagued by vulnerabilities. On the other hand, new emerging cloud paradigms like microservices and serverless computing have led to the sharing of computing resources among hundreds of users at a time. In this new era of computing, we can no longer afford to build each layer separately. Instead, we have to rethink the synergy between the operating system and hardware from the ground up.
In this talk, I will focus on rethinking the virtual memory abstraction. First, I will introduce Microarchitectural Replay Attacks, a novel family of side-channel attacks that exploit existing virtual memory mechanisms. These attacks leverage the fact that, in modern out-of-order processors, a single dynamic instruction can be forced to execute many times. Then, I will describe Elastic Cuckoo Page Tables, my proposal to rebuild the virtual memory abstraction for parallelism. Finally, I will conclude by describing ongoing and future directions towards redesigning the hardware and the operating system layers.
Bio: Dimitrios Skarlatos will start as an Assistant Professor in the Computer Science Department at Carnegie Mellon University in Fall 2021. Currently he is working on cluster management at Facebook Research. Dimitrios earned a PhD from the University of Illinois at Urbana-Champaign (UIUC), where he worked with Professor Josep Torrellas. His research lies at the intersection of computer architecture, security, and operating systems. He particularly enjoys questioning the fundamental assumptions behind computer design decisions. He builds practical solutions that improve the performance and bolster--or sometimes break--the security guarantees of computing systems. Dimitrios has earned an MS from UIUC and a BS in Electronic and Computer Engineering from the Technical University of Crete in Greece.