June 2024 - Colo - huji-cs listserver

CS Colloquium (01/07): Yael Amsterdamer (Bar-Ilan University)
by Sagie Benaim 01 Jul '24

01 Jul '24

Dear all, Next week, we have the pleasure of having Prof. Yael Amsterdamer give a talk in the colloquium. The seminar will be held on Monday, July 1st at 14:00. Location: C221. The title, abstract and bio appear below. Looking forward to seeing you, Sagie and Liat *Title:* Active Data Cleaning *Abstract:* We take an active approach to the cleaning of uncertain databases, by proposing a set of tools to guide the cleaning process. We start with a database whose tuple correctness is uncertain, and with some means of resolving this uncertainty, e.g., crowdsourcing, experts, a trained ML model or external sources. Guided by a query that defines what part of the data is of importance, our goal is to select tuples whose cleaning would effectively resolve uncertainty in query results. In other words, we develop a query-guided process for the resolution of uncertain data. Our approach combines techniques from different fields, including the use of provenance information to capture the propagation of errors to query results, Boolean interactive evaluation to decide which input tuples to clean based on their role in output derivation, and active learning to estimate the probability of errors. *Bio*: Yael Amsterdamer is a Professor at the Department of Computer Science, Bar-Ilan University, and the head of the Data Management Lab. She received her Ph.D. in Computer Science from Tel-Aviv University, and has been a visiting Scholar at the University of Pennsylvania, Philadelphia, PA and jointly at Télécom Paris and INRIA institute (Paris, France). Her research is in the field of interactive data management spanning topics such as crowd-powered data management, interactive summarization and data cleaning. Her research was awarded multiple competitive grants including the Israeli Science Foundation (ISF) personal grants, the Israeli Ministry of Science (MOST) grant, and the BIU Center for Research in Applied Cryptography and Cyber Security Personal Grant. Her research is published in top venues of her field and she continually serves in roles such as area chair and demo track chair for ICDE, DEI chair for SIGMOD, PC chair for aiDM and others.

1 1

CS Colloquium (24/06): Yannai A. Gonczarowski (Harvard University)
by Sagie Benaim 24 Jun '24

24 Jun '24

Dear all, Next week, we have the pleasure of having Prof. Yannai A. Gonczarowski give a talk in the colloquium. The seminar will be held on Monday, June 24th at 14:00. Location: C221. The title, abstract and bio appear below. Looking forward to seeing you, Sagie and Liat *Title:* Strategyproofness-Exposing Mechanism Descriptions *Abstract:* A menu description presents a mechanism to player i in two steps. Step (1) uses the reports of other players to describe i's menu: the set of i's potential outcomes. Step (2) uses i's report to select i's favorite outcome from her menu. Can menu descriptions better expose strategyproofness, without sacrificing simplicity? We propose a new, simple menu description of Deferred Acceptance. We prove that—in contrast with other common matching mechanisms—this menu description must differ substantially from the corresponding traditional description. We demonstrate, with an incentivized lab experiment, the promise and challenges of menu descriptions. Based upon joint works with Ori Heffetz, Guy Ishai, and Clayton Thomas. *Bio*: Yannai A. Gonczarowski is an Assistant Professor of Economics and of Computer Science at Harvard University—the first faculty member at Harvard to have been appointed to both of these departments. Interested in both economic theory and theoretical computer science, Yannai explores computer-science-inspired economics: he harnesses approaches, aesthetics, and techniques traditionally originating in computer science to derive economically meaningful insights. Yannai received his PhD from the Departments of Mathematics and Computer Science, and the Center for the Study of Rationality, at the Hebrew University of Jerusalem. Yannai is also a professionally-trained opera singer, having acquired a bachelor’s degree and a master’s degree in Classical Singing at the Jerusalem Academy of Music and Dance. Yannai's doctoral dissertation was recognized with several awards, including the Michael B. Maschler Prize of the Israeli Chapter of the Game Theory Society and the ACM SIGecom Doctoral Dissertation Award. For the design and implementation of the National Matching System for Gap-Year Programs in Israel, he was awarded the inaugural INFORMS AMD Michael H. Rothkopf Junior Researcher Paper Prize (first place). Yannai was also the recipient of the inaugural ACM SIGecom Award for Best Presentation by a Student or Postdoctoral Researcher. His first textbook, "Mathematical Logic through Python" (Gonczarowski and Nisan), which introduces a new approach to teaching the material of a basic Logic course to Computer Science students, tailored to the unique intuitions and strengths of this cohort of students, was published by Cambridge University Press.

1 1

CS Colloquium (17/06): Scott Aaronson (UT Austin and OpenAI)
by Sagie Benaim 17 Jun '24

17 Jun '24

Dear all, Next week, we have the pleasure of having Prof. Scott Aaronson give a talk in the colloquium. The seminar will be held on Monday, June 17th at 14:00. Location: C221. The title, abstract and bio appear below. Looking forward to seeing you, Sagie and Liat *Title:* AI Safety and Theoretical Computer Science *Abstract:* Progress on AI safety and alignment, like the current AI revolution more generally, has been almost entirely empirical. In this talk, however, I'll survey a few areas where I think theoretical computer science can contribute to AI safety, including: - How can we robustly watermark the outputs of Large Language Models and other generative AI systems, to help identify academic cheating, deepfakes, and AI-enabled fraud? I'll explain my proposal and its basic mathematical properties, as well as what remains to be done. - Can one insert undetectable cryptographic backdoors into neural nets, for good or ill? In what senses can those backdoors also be unremovable? How robust are they against fine-tuning? - Should we expect neural nets to be "generically" interpretable? I'll discuss a beautiful formalization of that question due to Paul Christiano, along with some initial progress on it, and an unexpected connection to quantum computing. *Bio*: Scott Aaronson is Schlumberger Chair of Computer Science at the University of Texas at Austin, and founding director of its Quantum Information Center, currently on leave at OpenAI to work on theoretical foundations of AI safety. He received his bachelor's from Cornell University and his PhD from UC Berkeley. Before coming to UT Austin, he spent nine years as a professor in Electrical Engineering and Computer Science at MIT. Aaronson's research in theoretical computer science has focused mainly on the capabilities and limits of quantum computers. His first book, Quantum Computing Since Democritus, was published in 2013 by Cambridge University Press. He received the National Science Foundation’s Alan T. Waterman Award, the United States PECASE Award, the Tomassoni-Chisesi Prize in Physics, and the ACM Prize in Computing, and is a Fellow of the ACM and the AAAS.

1 1

Fwd: The 34th Advanced School in Economic Theory
by Noam Nisan 16 Jun '24

16 Jun '24

---------- Forwarded message --------- מאת: Keren Goldberg <kerengoldb(a)savion.huji.ac.il> ‪Date: יום ב׳, 10 ביוני 2024, 11:36‬ Subject: [Ratio-cen-all] The 34th Advanced School in Economic Theory To: ratio-cen-all(a)sympa.huji.ac.il <ratio-cen-all(a)sympa.huji.ac.il>, ratio-guests(a)sympa.huji.ac.il <ratio-guests(a)sympa.huji.ac.il> Dear all, This is a reminder that the summer school in economic theory will take place *23.6-27.6* . The topic this year is Economic Theory and Computer Science. Attached is the program of the school. Elchanan

1 0

CS Colloquium (10/06): Moran Feldman (University of Haifa)
by Sagie Benaim 10 Jun '24

10 Jun '24

Dear all, Next week, we have the pleasure of having Prof. Moran Feldman give a talk in the colloquium. The seminar will be held on Monday, June 10th at 14:00. Location: C221. The title, abstract and bio appear below. Looking forward to seeing you, Sagie and Liat *Title:* Parameterization in Submodular Maximization *Abstract:* Submodular maximization problems have gained importance over the last two decades due to a lucky combination of theoretical breakthroughs and emerging machine learning applications. Traditionally, the input in such problems is characterized by binary properties that the input is assumed to obey such as monotonicity and down-closed constraints. Recent works have started to replace these binary properties with continuous parameters. In other words, instead of algorithms that work when the property hold, and fail otherwise, we now have algorithms whose performance smoothly deteriorates as the function becomes farther from obeying the property. This has hugely increased the range of problems to which submodular maximization techniques apply, and produced more tailored results for specific problems. In this talk, I will survey some of the main results underlying this exciting development. *Bio*: Moran Feldman obtained his Ph.D. degree in Computer Science from the Technion in 2013 under the supervision of Prof. Seffi Naor. Over the years, he was an intern at Yahoo! Research, Google and Microsoft Research, and completed a postdoc at EPFL in 2015 (hosted by Prof. Ola Svensson). Moran was previously a faculty member and Alon Fellowship recipient in the Open University of Israel, and since 2019 he is a faculty member in the University of Haifa. His research focuses on combinatorial optimization, with an emphasis on submodular maximization.

1 1

CS Colloquium (03/06): Orr Dunkelman (University of Haifa)
by Sagie Benaim 03 Jun '24

03 Jun '24

Dear all, Next week, we have the pleasure of having Prof. Orr Dunkelman give a talk in the colloquium. The seminar will be held on Monday, June 3rd at 14:00. Location: C221. The title, abstract and bio appear below. Looking forward to seeing you, Sagie and Liat *Title:* The Hunt for High Probability Statistical Impurities in Cryptographic Primitives *Abstract:* Computer security relies on cryptographic primitives such as block ciphers and hash functions. The security of these primitives is usually not proved in a reduction-style proof, but rather argued based on claims of the form - this block cipher has no statistical property of some type (e.g., differential) with high enough probability. However, how do we know that there are no such statistical properties in a given n-bit cryptographic primitive? When *n* is small (e.g., an 8-bit S-box), this is easy to do. However, for large values of *n*, the only practical way to find such statistical properties was to exploit the internal structure of the primitive and to speed up the search with a variety of heuristic rules of thumb. However, such bottom-up techniques can miss many properties, especially in cryptosystems which are designed to have hidden trapdoors. In this work we consider the top-down version of the problem in which the cryptographic primitive is given as a structureless black box, and reduce the complexity of the best known techniques for finding all its significant differential and linear properties by a large factor of 2^{n/2}. Our main new tool is the idea of using *surrogate differentiation*. In the context of finding differential properties, it enables us to simultaneously find information about all the differentials of the form f(x) \oplus f(x \oplus \alpha) in all possible directions by differentiating *f* in a single randomly chosen direction \gamma (which is unrelated to the \alpha’s). In the context of finding linear properties, surrogate differentiation can be combined in a highly effective way with the Fast Fourier Transform. For 64-bit cryptographic primitives, this technique makes it possible to automatically find in about 2^64 time all their differentials with probability larger than 2^{-32} and all their linear approximations with bias larger than 2^{-16}; previous algorithms for these problems required at least 2^{96} time. This is a joint work with Itai Dinur, Nathan Keller, Eyal Ronen, and Adi Shamir. *Bio*: Orr Dunkelman is a full professor in the Computer Science Department at the University of Haifa. He has held post-doctoral research positions at the Weizmann Institute of Science, Ecole Normale Superieure, and Katholieke Universiteit Leuven. He earned his Ph.D. from the Technion under the supervision of Prof. Eli Biham.

1 2

2024

2023

Colo June 2024

2024

2023

Colo June 2024 ----- 2024 ----- November 2024 October 2024 September 2024 August 2024 July 2024 June 2024 May 2024 April 2024 March 2024 February 2024 January 2024 ----- 2023 ----- December 2023 November 2023

Colo June 2024