# 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.

- Bioinformatics Forum
- BizTEC Forum
- ceClub
- CGGC Weekly Seminar
- Coding Theory Seminar
- Colloquia
- Haifux, Haifa Linux Club
- Hardware Security Seminar
- Pixel Club
- Theory Seminar

## Upcoming Colloquia & Seminars

### A Generic Sharding Scheme for Blockchain Protocols

- Speaker:
- Zuphit Fidelman, M.Sc. Thesis Seminar
- Date:
- Monday, 25.3.2019, 13:30
- Place:
- Taub 601
- Advisor:
- Prof. R. Friedman

Blockchain protocols are notoriously bad at scaling. Most protocols do work reasonably well when used in a small scale. Yet, as the network size grows, resources are added and overall computing power increases, most protocols simply do not scale. This is largely due to the fact that the entire process is fully replicated by all participants. Surpassing some desired redundancy threshold, this offers no advantage. We tackle the issue by introducing a formal general framework for sharding blockchain protocols. We prove that all sharded protocols obtained by applying our framework live up to the same safety and liveness guarantees as their non-sharded counterparts. A concrete demonstration of the framework is also provided, by sharding the recently proposed Algorand protocol.

### Pixel Club: Spectral Analysis of a Non-Equilibrium Stochastic System on a General Network

- Speaker:
- Inbar Seroussi (Tel-Aviv University)
- Date:
- Tuesday, 26.3.2019, 11:30
- Place:
- Room 337 Taub Bld.

Unravelling underlying complex structures from limited resolution measurements is a known problem arising in many scientific disciplines. We study a stochastic dynamical model with a multiplicative noise. It consists of a stochastic differential equation living on a graph, similar to approaches used in population dynamics or directed polymers in random media. This model has numerous applications, such as population growth, economic growth, and optimal control. We present a new application of this model in the context of Magnetic Resonance (MR) measurements of porous structure such as brain tissue from a single voxel. We develop a new tool for approximation of correlation functions based on spectral analysis that does not require translation invariance. This enables us to go beyond lattices and analyze general networks. We show, analytically, that this general model has different phases depending on the topology of the network. One of the main parameters which describe the network topology is the spectral dimension d ̃. We show that the correlation functions depend on the spectral dimension and that only for d ̃> 2 a dynamical phase transition occurs. We show by simulation how the system behaves for different network topologies, by defining and calculating the Lyapunov exponents on the graph.

PhD student under supervision of Prof. Nir Sochen.### From Cognitive Biases to the Communication Complexity of Local Search

- Speaker:
- Shahar Dobzinski - COLLOQUIUM LECTURE
- Date:
- Tuesday, 2.4.2019, 14:30
- Place:
- Room 337 Taub Bld.
- Affiliation:
- Weizmann Institute, Applied Math and Computer Science Dept.
- Host:
- Yuval Filmus

In this talk I will tell you how analyzing economic markets where agents have cognitive biases has led to better understanding of the communication complexity of local search procedures. We begin the talk with studying combinatorial auctions with bidders that exhibit endowment effect. In most of the previous work on cognitive biases in algorithmic game theory (e.g., [Kleinberg and Oren, EC'14] and its follow-ups) the focus was on analyzing the implications and mitigating their negative consequences. In contrast, we show how cognitive biases can sometimes be harnessed to improve the outcome. Specifically, we study Walrasian equilibria in combinatorial markets. It is well known that a Walrasian equilibrium exists only in limited settings, e.g., when all valuations are gross substitutes, but fails to exist in more general settings, e.g., when the valuations are submodular. We consider combinatorial settings in which bidders exhibit the endowment effect, that is, their value for items increases with ownership. Our main result here shows that when the valuations are submodular even a mild level of endowment effect suffices to guarantee the existence of Walrasian equilibrium. In fact, we show that in contrast to Walrasian equilibria with standard utility maximizers bidders -- in which the equilibrium allocation must be a global optimum -- when bidders exhibit endowment effect any local optimum can be an equilibrium allocation. This raises the natural question of understanding the complexity of computing a local maximum in combinatorial markets. We reduce it to the following communication variant of local search: there is some fixed, commonly known graph G. Alice holds f_A and Bob holds f_B, both are functions that specify a value for each vertex. The goal is to find a local maximum of f_A+f_B, i.e., a vertex v for which f_A(v)+f_B(v) >= f_A(u)+f_B(u) for every neighbor u of v. We prove that finding a local maximum requires polynomial (in the number of vertices) bits of communication. Based on joint works with Moshe Babaioff, Yakov Babichenko, Noam Nisan, and Sigal Oren.

### Knowledge-Based Learning through Feature Generation

- Speaker:
- Michal Badian, M.Sc. Thesis Seminar
- Date:
- Sunday, 7.4.2019, 14:30
- Place:
- Taub 601
- Advisor:
- Prof. Shaul Markovitch

Machine learning algorithms have difficulties to generalize over a small set of examples. Humans can perform such a task by exploiting vast amount of background knowledge they possess. One method for enhancing learning algorithms with external knowledge is through feature generation. We introduce a new algorithm for generating features based on a collection of auxiliary datasets. We assume that, in addition to the training set, we have access to a additional datasets. We do not assume that the auxiliary datasets represent learning tasks that are similar to our original one. The algorithm finds features that are common to the training set and the auxiliary datasets. Based on these features and on examples from the auxiliary datasets, it induces predictors for new features from the auxiliary datasets. The induced predictors are then added to the original training set as generated features. Our method was tested on a variety of learning tasks, including text classification and medical prediction, and showed a significant improvement over using just the given features.

### The Complexity of Relational Queries over Extractions from Text

- Speaker:
- Liat Peterfreund, Ph.D. Thesis Seminar
- Date:
- Monday, 8.4.2019, 14:30
- Place:
- Taub 601
- Advisor:
- Prof. Benny Kimelfeld

Information Extraction (IE) is the task of extracting structured information from textual data. We explore a programming paradigm that is supported by several IE systems where relations extracted by atomic extractors undergo a relational manipulation. In our efforts toward achieving a better understanding of IE systems, we study queries in the framework of document spanners that was introduced by Fagin et al. A spanner is a function that extracts from a document (string) a relation over text intervals, called spans, using either atomic extractors or a relational algebra query on top of these extractors. Evaluating IE queries is a computational problem that involves both the atomic extractors, the relational algebra expression and the document. We investigate the complexity of this problem from various angles, each keeping some components fixed and regarding the rest as input. In addition, we study the expressive power of IE queries that involve recursion and the implications of supporting partial answers in the flavor of SPARQL.

- Date:
- Place:

### Some systems engineering problems and a little bit of theory

- Speaker:
- Eitan Bachmat - COLLOQUIUM LECTURE
- Date:
- Tuesday, 16.4.2019, 14:30
- Place:
- Room 337 Taub Bld.
- Affiliation:
- Ben-Gurion University
- Host:
- Yuval Filmus

We will consider the SITA server farm scheduling policies which were introduced and studied by Harchol-Balter and her collaborators. In particular we will discuss a recent INFOCOM 17 paper of Doncel, Aalto and Ayesta and relate one of the tables there to the work of Riemann on the functional equation of the zeta function. We will also consider certain disk drive scheduling problems (travelling salesman on a disk drive) and then relate it space-time geometry and in particular gravitational lensing for positive mass particles. Finally we will relate, via airplane boarding, the disk scheduling problem with server farm scheduling. Short Bio: ========== Eitan Bachmat received his PhD in mathematics from M.I.T. and is currently a professor of computer science at Ben-Gurion University. Eitan works on problems in the areas of Storage Systems, Performance analysis, Systems engineering, Operations research, Autism, Personalized Medicine and Digital healthcare, using techniques from Physics, Mathematics and Computer Science. He is an expert on airplane boarding and express line queues and how they relate to relativity theory and number theory respectively. Eitan also works closely with industry and various organizations on diverse applications and holds 38 patents. ========================== Refreshments will be served from 14:15 Lecture starts at 14:30

### CS Open Day For Graduate Studies

- Date:
- Wednesday, 17.4.2019, 12:15
- Place:
- Room 337 Taub Bld.

The 2019 open day invites outstanding undergraduates from all universities to come to the Technion and learn about the Computer Science and Department, to meet faculty and graduate students and to hear a fascinating talk by Dr. Tal Cohen, Director of Program Development at Google: "Do Advanced Degrees Indeed Advance?"

The event will be held on Wednesday, April 17, 2018, between 12:15-15:00, in CS Taub Building, room 337 (3rd floor).

The program will include review on curriculum and admission requirements, as well as scientific lectures. In addition, personal meeting between candidates and vice deans of both faculties will be optional.

Attendance at the open day requires pre-registration.

More details and program.### Computer Agents that Interact Proficiently with People

- Speaker:
- Sarit Kraus - COLLOQUIUM LECTURE
- Date:
- Tuesday, 30.4.2019, 14:30
- Place:
- Room 337 Taub Bld.
- Affiliation:
- Bar-Ilan University
- Host:
- Yuval Filmus

Automated agents that interact proficiently with people can be useful in supporting, training or replacing people in complex tasks. The inclusion of people presents novel problems for the design of automated agents’ strategies. People do not necessarily adhere to the optimal, monolithic strategies that can be derived analytically. Their behavior is affected by a multitude of social and psychological factors. In this talk I will show how combining machine learning techniques for human modelling, human behavioral models, formal decision-making and game theory approaches enables agents to interact well with people. Applications include intelligent agents that help drivers reduce energy consumption, agents that support rehabilitation, employer-employee negotiation and agents that support a human operator in managing a team of low-cost mobile robots in search and rescue tasks. Short Bio: =========== Sarit Kraus (Ph.D. Computer Science, Hebrew University, 1989) is a Professor of Computer Science at Bar-Ilan University. Her research is focused on intelligent agents and multi-agent systems (including people and robots). Kraus was awarded the IJCAI Computers and Thought Award, ACM SIGART Agents Research award, the EMET prize and was twice the winner of the IFAAMAS influential paper award. She is AAAI, ECCAI and ACM fellow and a recipient of the advanced ERC grant.

### On Optimization and Generalization in Deep Learning

- Speaker:
- Amir Globerson - COLLOQUIUM LECTURE
- Date:
- Tuesday, 4.6.2019, 14:30
- Place:
- Room 337 Taub Bld.
- Affiliation:
- Tel-Aviv University
- Host:
- Yuval Filmus

TBA

### SYNTECH: Synthesis Technologies for Reactive Systems Software Engineers

- Speaker:
- Shahar Maoz - COLLOQUIUM LECTURE
- Date:
- Tuesday, 11.6.2019, 14:30
- Place:
- Room 337 Taub Bld.
- Affiliation:
- School of Computer Science, Tel-Aviv University
- Host:
- Yuval Filmus

T B A Shahar Maoz research interests are in Software Engineering, specifically software and systems modeling, modeling languages, and formal methods. He has recently worked on synthesis of structure and behavior, differencing, and log analysis. He joined the faculty of the School of Computer Science, Tel Aviv University, in summer 2012, as a (tenure-track) Senior Lecturer (assistant professor). Since January 2018 he is an Associate Professor with Tenure. He received his B.Sc and M.Sc. in Computer Science from Tel Aviv University and his PhD in Computer Science from the Weizmann Institute (2009). Before joining TAU as a faculty member he was post-doc research fellow at RWTH Aachen University, Germany (2010-2012). In 2015-2016 he was on sabbatical as visiting scientist at MIT CSAIL.