# Colloquia and Seminars

To join the email distribution list of the cs colloquia, please visit the list subscription page.Computer Science events calendar in HTTP ICS format for of Google calendars, and for Outlook.

Academic Calendar at Technion site.

- CGGC Weekly Seminar
- Coding Theory Seminar
- Colloquia
- Hardware Security Seminar
- Pixel Club
- Theory of Data Science and Deep Learning
- Theory Seminar

## Upcoming Colloquia & Seminars

### Data Science & Deep Learning Seminar: Learning and Testing of Markov Chains: Report from the Front Lines

- Speaker:
- Aryeh Kontorovich (Ben-Gurion University)
- Date:
- Monday, 25.11.2019, 12:30
- Place:
- Taub 301 Taub Bld.

A fundamental quantity associated with a Markov chain is its mixing time. Can we estimate this quantity empirically from a single long sample path? This might appear to present an impossible circularity, since the mixing time controls our ability to infer global properties of the chain from a single path -- and this is the very unknown quantity we're trying to estimate! We present a way out of this conundrum, providing a fully empirical procedure, with efficiently computable confidence intervals.Now suppose we want to learn the full Markov chain -- that is, estimate the transition probabilities. The minimax sample complexity is well-understood in the i.i.d. case, but for Markov chains, almost nothing was known until very recently. I'll present some of our latest results in this area. Finally, suppose we wanted to test the identity of a Markov chain against a known reference chain. This problem is simpler than learning; in fact, it requires no assumptions on the unknown chain whatsoever! Here too we give minimax rates. Joint work with Daniel Hsu, Csaba SzepesvᲩ, David Levin, Yuval Peres, and Geoffrey Wolfer.

Bio:

Dr. Kontorovich is an associate professor at Computer Science Department in Ben-Gurion University. He received his B.Sc in Mathematics, Applied and Computational Mathematics from Princeton University (with Honors) and his M.Sc. in Computer Science from Carnegie Mellon University. Dr. Kontorovich received his Ph.D.in Computer Science from Carnegie Mellon University under the supervision of Prof. John Lafferty. Currently, his main area of research is theoretical machine learning: probability, statistics, Markov chains, metric spaces.### Pixel Club: Tools for Visual Expression and Communication

- Speaker:
- Ohad Fried (Stanford University)
- Date:
- Tuesday, 26.11.2019, 11:30
- Place:
- Electrical Eng. Building 1061

Photos and videos are now a main mode of communication, used to tell stories, share experiences and convey ideas. However, common media editing tools are often either too complex to master, or oversimplified and limited.

In this talk I will present my strategy towards the creation of media editing techniques that are easy to learn, yet expressive enough to reflect unique creative objectives. We will mostly discuss one specific domain --- human heads --- which are both extremely common (i.e. people care about people) and technologically challenging. I will present several works on editing video by editing text, perspective manipulation, and in-camera lighting feedback. I will also discuss exciting future opportunities related to neural rendering and digital representations of humans.

Bio:

Ohad Fried is a postdoctoral research scholar at Stanford University. His work lies in the intersection of computer graphics, computer vision, and human-computer interaction. He holds a PhD in computer science from Princeton University, and an M.Sc. in computer science and a B.Sc. in computational biology from The Hebrew University. Ohad’s research focuses on tools, algorithms, and new paradigms for photo and video editing. Ohad is the recipient of several awards, including a Siebel Scholarship and a Google PhD Fellowship. If you own a cable modem, there’s a non-negligible chance that Ohad’s code runs within it, so feel free to blame him for your slow internet connection### ceClub: Preventing (Network) Time Travel with Chronos

- Speaker:
- Neta Rozen-Schiff (The Hebrew University of Jerusalem)
- Date:
- Wednesday, 27.11.2019, 11:30
- Place:
- Electrical Eng. Building 861

The Network Time Protocol (NTP) synchronizes time across computer systems over the Internet. Unfortunately, NTP is highly vulnerable to “time shifting attacks”, in which the attacker’s goal is to shift forward/backward the local time at an NTP client. NTP’s security vulnerabilities have severe implications for time-sensitive applications and for security mechanisms, including TLS certificates, DNS and DNSSEC, RPKI, Kerberos, BitCoin, and beyond. While technically NTP supports cryptographic authentication, it is very rarely used in practice and, worse yet, timeshifting attacks on NTP are possible even if all NTP communications are encrypted and authenticated. We present Chronos, a new NTP client that achieves good synchronization even in the presence of powerful attackers who are in direct control of a large number of NTP servers. Importantly, Chronos is backwards compatible with legacy NTP and involves no changes whatsoever to NTP servers. Chronos leverages ideas from distributed computing literature on clock synchronization in the presence of adversarial (Byzantine) behavior. A Chronos client iteratively “crowdsources” time queries across multiple NTP servers and applies a provably secure algorithm for eliminating “suspicious” responses and averaging over the remaining responses. Chronos is carefully engineered to minimize communication overhead so as to avoid overloading NTP servers. We evaluate Chronos’ security and network efficiency guarantees via a combination of theoretical analyses and experiments with a prototype implementation. Our results indicate that to succeed in shifting time at a Chronos client by over 100ms from the UTC, even a powerful man-in-the-middle attacker requires over 20 years of effort in expectation.

This is a joint work with Omer Deutsch, Danny Dolev, Michael Schapira.

Bio:

Neta Rozen-Schiff is a research associate at the School of Computer Science and Engineering of the Hebrew University of Jerusalem, where she works with Prof. David Hay and Prof. Michael Schapira. Her research interests include optimization and control in datacenters, congestion control, network security, and software-defined networking. Prior to joining the Hebrew university, Neta spent a decade in the industry, working as a software engineer and as an operations researcher. Neta holds a BSc and MSc in Mathematics from Bar-Ilan University, and a PhD from the Technion, awarded in 2004, 2005, and 2011, respectively.### Theory Seminar: Local Proofs Approaching the Witness Length

- Speaker:
- Noga Ron-Zewi (Haifa University)
- Date:
- Wednesday, 27.11.2019, 12:30
- Place:
- Taub 201 Taub Bld.

Interactive oracle proofs are a hybrid between interactive proofsand probabilistically-checkable proofs, where the prover is allowed to interactwith a verifier by sending relatively long messages to the verifier, who inturn is only allowed to query a few of the bits that were sent.

In this work we construct, for any NP relation for whichmembership can be decided in polynomial-time and bounded polynomial space (e.g.,SAT, Hamiltonicity, Clique, Vertex-Cover, etc.), interactive oracle proofs inwhich the proof length approaches the witness length. The number of rounds, aswell as the number of queries made by the verifier, are constant. Our proofleverages recent constructions of high-rate locally testable tensor codes. Inparticular, we bypass the barrier imposed by the low rate of multiplicationcodes (e.g., Reed-Solomon, Reed-Muller or AG codes) - a core component in priorconstructions.

Joint work with Ron Rothblum.### Data Science & Deep Learning Seminar:

- Speaker:
- Konstantin Makarychev
- Date:
- Monday, 2.12.2019, 12:30
- Place:
- Taub 301 Taub Bld.

Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering Consider an instance of Euclidean k-means or k-medians clustering. We show that the cost of the optimal solution is preserved up to a factor of (1+ε) under a projection onto a random - dimensional subspace. Further, the cost of every clustering is preserved within (1+ε). Our bound on the dimension is nearly optimal. Additionally, our result applies to Euclidean k-clustering with the distances raised to the p-th power for any constant p.

### Degree-Bounded Polymatroids, with Applications to the Many-Visits TSP

- Speaker:
- Matthias Mnich - COLLOQUIUM LECTURE
- Date:
- Tuesday, 3.12.2019, 14:30
- Place:
- Room 337 Taub Bld.
- Affiliation:
- University of Bonn
- Host:
- Hadas Shachnai

In the Bounded Degree Matroid Basis Problem, we are given a matroid and a hypergraph on the same ground set, together with costs for the elements of that set as well as lower and upper bounds f(e) and g(e) for each hyperedge e. The objective is to find a minimum-cost basis B such that f(e) <= |B \cap e| <= g(e) for each hyperedge e. Kiraly, Lau and Singh (Combinatorica, 2012) provided an algorithm that finds a basis of cost at most the optimum value which violates the lower and upper bounds by at most 2\Delta-1, where \Delta is the maximum degree of the hypergraph. We consider an extension of the matroid basis problem to generalized polymatroids, and additionally allow element multiplicities. Building on the approach of Kiraly, Lau and Singh, we provide an algorithm for finding a solution of cost at most the optimum value having the same additive approximation guarantee. As an application, we develop a 1.5-approximation for the metric many-visits TSP, where the goal is to find a minimum-cost tour that visits each city v a positive number r_v of times. Our approach combines our algorithm for the Lower Bounded Degree Generalized Polymatroid Basis Problem with Multiplicities with the principle of Christofides' algorithm from 1976 for the (single-visit) metric TSP, whose approximation guarantee it matches. We also present a new algorithm for the general many-visits TSP without any metric assumptions on the edge cost. For this problem, Cosmadakis and Papadimitriou (SICOMP, 1984) provided an algorithm that finds an optimal tour in time and space that depends superexponentially on the number of cities. We give an improved algorithm which simultaneously improves the time complexity to single-exponential, and the space complexity to polynomial. Assuming the Exponential Time Hypothesis, the run time of our algorithm is asymptotically optimal. Our algorithm is arguably simpler than the one by Cosmadakis and Papadimitriou. (Based on joint work with Kristof Berczi, Andre Berger, Tamas Kiraly, Laszlo Kozma, Gyula Pap and Roland Vincze) Short Bio: ========== Matthias Mnich is an assistant professor of quantitative economics at Maastricht University, The Netherlands, currently on leave for research in theoretical computer science at the Rheinische Friedrich-Wilhelms Universitaet Bonn, Germany. He obtained his PhD in 2010 at Eindhoven University of Technology, for which he received the Philips Prize 2010. Since then he held positions at UC Berkeley, USA and the Max Planck Institute for Computer Science, and a visiting professorship at TU Darmstadt, Germany. His research interests are in combinatorial algorithms, social choice theory, algorithms for big data, and algorithms in artificial intelligence. ================================================== Refreshments will be served from 14:15 Lecture starts at 14:30

### MPC Beyond the Generic Model - Private Intersection Analytics

- Speaker:
- Benny Pinkas - COLLOQUIUM LECTURE
- Date:
- Tuesday, 10.12.2019, 14:30
- Place:
- Room 337 Taub Bld.
- Affiliation:
- Dept. of Computer Science, and Center for Research in Applied Cryptography and Cyber Security, Bar-Ilan University
- Host:
- Yuval Filmus

Effective data analysis often depends on data that is known to different sources, including private data whose owners cannot disclose. The task at hand is to perform effective analysis of the data while preserving its privacy. This talk will describe efficient cryptographic protocols, some of them based on variants of private set intersection (PSI), that can be applied to perform private analysis of data. Short Bio: ============ Benny Pinkas is a member of the Bar Ilan Cryptography Group and the Center for Research in Applied Cryptography and Cyber Security. His reserach focuses on computer security, privacy and cryptography, and in particular on the design of efficient security systems based on sound assumptions and solid proofs. During the 2011/2 academic year he was also on sabbatical at Google Research. He previously worked at the University of Haifa, at HP Labs in Haifa and in Princeton, and at STAR Lab, Intertrust Technologies. Before that he was a Ph.D. student of Moni Naor at the Foundations of Computer Science Group at the Department of Computer Science and Applied Math in the Weizmann Institute of Science. ========================================= Rereshments will be served from 14:15 Lecture starts at 14:30