- Colo - huji-cs listserver

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

CS Colloquium (27/05): Hagit Attiya (Technion)
by Sagie Benaim 27 May '24

27 May '24

Dear all, Next week, we have the pleasure of having Prof. Hagit Attiya give a talk in the colloquium. The seminar will be held on Monday, May 27th at 14:00. Location: C220. The title, abstract and bio appear below. Looking forward to seeing you, Sagie and Liat *Title:* Preserving Hyperproperties when Using Concurrent Objects *Abstract:* Linearizability, a consistency condition for concurrent objects, is known to preserve trace properties. This suffices for modular usage of concurrent objects in applications, deriving their safety properties from the abstract object they implement. However, other desirable properties, like average complexity and information leakage, are not trace properties. These hyperproperties are not preserved by linearizable concurrent objects, especially when randomization is used. This talk will discuss formal ways to specify concurrent objects that preserve hyperproperties and their relation with verification methods. We will show that certain concurrent objects cannot satisfy such specifications, and describe ways to mitigate these limitations. This is a joint work with Constantin Enea and Jennifer Welch. *Bio*: Hagit Attiya is a professor at the department of Computer Science at the Technion, Israel Institute of Technology, and holds the Harry W. Labov and Charlotte Ullman Labov Academic Chair. She received all her academic degrees, in Computer Science, from the Hebrew University of Jerusalem, and was a post-doctoral fellow at MIT.

1 1

CS Colloquium (20/05): Elchanan Mossel (MIT)
by Sagie Benaim 20 May '24

20 May '24

Dear all, Next week, we have the pleasure of having Prof. Elchanan Mossel give a talk in the colloquium. The seminar will be held on Monday, May 20th at 14:00. Location: C220. The title, abstract and bio appear below. Looking forward to seeing you, Sagie and Liat *Title:* Why depth? Some new perspectives on the advantages of depth in inference *Abstract:* Can theory help explain the success of deep nets on real data? One avenue to explore this question is to ask if we can find 1. Natural data models where: 2. Inference is computationally and statistically efficient, 3. Inference requires depth (or some other measure of complexity) and 4. The inference procedure can be learned efficiently from data As proving lower bounds in theoretical computer science for explicit objects is hard, perhaps the most difficult task is to establish 3. I will discuss some recent works that try to establish 1-4 for the broadcast model on the tree and where the inference procedure is belief propagation. Based on: https://arxiv.org/pdf/2402.13359 https://dl.acm.org/doi/abs/10.1145/3564246.3585155 https://proceedings.neurips.cc/paper_files/paper/2022/hash/77e6814d32a86b76… https://proceedings.mlr.press/v125/moitra20a.html https://arxiv.org/pdf/1612.09057 *Bio*: Elchanan Mossel is a professor of mathematics at the Massachusetts Institute of Technology. His primary research fields are probability theory, combinatorics, and statistical inference.

1 1

CS Colloquium (06/05): Gil Cohen (Tel Aviv University)
by Sagie Benaim 06 May '24

06 May '24

Dear all, We are resuming the colloquium with the start of the new semester. Next week, we have the pleasure of having Prof. Gil Cohen give a talk in the colloquium. The seminar will be held on Monday, May 6th at 14:00. Location: C220. The title, abstract and bio appear below. Looking forward to seeing you, Sagie and Liat *Title:* Tight Bounds for the Zig-Zag Product *Abstract:* In this talk, we will explore the Zig-Zag product, a pivotal concept in pseudorandomness introduced over two decades ago by Reingold, Vadhan, and Wigderson. We will utilize methods from free probability theory and analytic combinatorics to establish a tight bound on the spectral expansion when Zig-Zag-ing with a (vertex-transitive) graph H. Our bound incorporates H's entire spectrum, deviating from the classical, combinatorial, bound. This talk is designed for a broad audience; no prior knowledge of free probability, analytic combinatorics, or expanders for that matter, is required. This work is a collaboration with Itay Cohen and Gal Maor. *Bio*: Gil Cohen is a faculty member at the Department of Computer Science at Tel Aviv University. He is working on pseudo-randomness and derandomization, explicit constructions, and coding theory. Of particular interest are randomness extractors, derandomization of space-bounded computation, spectral graph theory, tree codes, locally decodable codes, and algebraic-geometric codes.

1 1

FILOFOCS DAY, April 4 2024
by Noam Nisan 20 Mar '24

20 Mar '24

---------- Forwarded message --------- From: Adi Rosen <umifilofocs-il(a)services.cnrs.fr> Date: Wed, Mar 20, 2024 at 3:12 PM Subject: [UMIFILOFOCS-IL] FILOFOCS DAY, April 4 2024 To: <umifilofocs-il(a)services.cnrs.fr> Cc: Rosen Adi <adi.rosen(a)irif.fr>, Yishay Mansour <mansour.yishay(a)gmail.com> Hi everyone, As annoucned, we will hold a FILOFOCS day on April 4, 2024, at Tel-Aviv University. The program can we found below, and more details including the abstracts can be found on the workshop's webpage at https://www.filofocs.org/filofocs-day-2024 . *Registration is mandatory by April 1*, but free. To register please visit the workshop’s webpage at https://www.filofocs.org/filofocs-day-2024 . *Program:* 9:00 - 9:25 *gathering, registration, and coffee* 9:25 - 9:30 *opening remarks* 9:30 - 10:00 *Moni Naor (Weizmann)* - *From Donkeys to Kings in Tournaments* 10:00 - 10:30 *Moshe Tennenholtz (Technion)* - *The Search for Stability: Learning Dynamics and the Relative Ranking Principle* 10:30 - 11:00 *Keren Censor-Hillel (Technion)* - *Distributed Subgraph Finding: Known and New* 11:00 - 11:30 *coffee break* 11:30 - 12:00 *Dan Halperin (TAU)* - *Multi-Robot Motion Planning: The Easy, the Hard and the Uncharted* 12:00 - 12:30 *Nadav Merlis (CREST, ENSAE Paris)* - *The Value of Reward Lookahead in Reinforcement Learning* 12:30 - 14:00 *Lunch (on your own)* 14:00 - 14:30 *Noam Nissan (HUJI)* - *Serial Monopoly on Blockchains* 14:30 - 15:00 * Niv Buchbinder (TAU)* - *Chasing Positive Bodies* 15:00 - 15:30 *Liat Peterfreund (HUJI)* - *From Standardization to Theory and Back* 15:30 - 16:00 *coffee break* 16:00 - 16:30 *Robert Krauthgamer (Weizmann)* - *Fully Scalable MPC Algorithms for Clustering in High Dimension* 16:30 - 17:00 *Kobbi Nissim (Georgetown)* - *A methodology for reconciling computer science and legal approaches to privacy* 17:00 - 17:30 *Joe Halpern (Cornell)* - *Language-Based Decision Theory with Causality* Hope to see you all there! Yishay Mansour and Adi Rosen

1 0

FILOFOCS workshop at Tel-Aviv University, April 4 2024
by Noam Nisan 13 Mar '24

13 Mar '24

---------- Forwarded message --------- From: Adi Rosen <umifilofocs-il(a)services.cnrs.fr> Date: Mon, Mar 11, 2024 at 12:24 PM Subject: [UMIFILOFOCS-IL] SAVE THE DATE - FILOFOCS DAY, April 4 2024 To: <umifilofocs-il(a)services.cnrs.fr> Cc: Rosen Adi <adi.rosen(a)irif.fr>, Yishay Mansour <mansour.yishay(a)gmail.com> Hi everyone, We are organizing a one day workshop of FILOFOCS at Tel Aviv University on Thursday April 4, 2024. The workshop will have multiple invited talks on various CS topics. Registration is mandatory, but free. To register please visit the workshop’s webpage at https://www.filofocs.org/filofocs-day-2024 . *Speakers:* Niv Buchbinder (TAU) Keren Censor-Hillel (Technion) Dan Halperin (TAU) Joe Halpern (Cornell) Robert Krauthgamer (Weizmann) Nadav Merlis (CREST, ENSAE Paris) Moni Naor (Weizmann) Noam Nissan (HUJI) Kobbi Nissim (Georgetown) Liat Peterfreund (HUJI) Moshe Tennenholtz (Technion) A detailed program will follow. Hope to see you all there! Yishay Mansour and Adi Rosen

1 0

CS Colloquium (11/03): Irit Dinur (Weizmann)
by Sagie Benaim 11 Mar '24

11 Mar '24

Dear all, Next week, we have the pleasure of having Prof. Irit Dinur give a talk in the colloquium. The seminar will be held on Monday, March 11th at 14:00. Location: C220. The title, abstract and bio appear below. Looking forward to seeing you, Sagie and Liat *Title:* Coboundary expansion and applications *Abstract:* Coboundary expansion is a topological notion introduced by Linial and Meshulam, and by Gromov. Kaufman and Lubotzky observed its relation to "Property testing", and in recent years it has found several applications in theoretical computer science, including for error correcting codes (both classical and quantum), for PCP agreement tests, and even for studying polarization in social networks. In the talk I will introduce this notion and some of its applications. No prior knowledge is assumed, of course. *Bio*: Irit Dinur is a professor of computer science at the Weizmann Institute of Science. Her research is in Foundations of Computer Science and in Combinatorics, especially Probabilistically Checkable Proofs, hardness of approximation, and most recently high dimensional expanders.

1 1

2024

2023

Colo ----- 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