# 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

### The Complexity of Database Inconsistency Measures

- Speaker:
- Ester Livshits, Ph.D. Thesis Seminar
- Date:
- Wednesday, 23.10.2019, 13:30
- Place:
- Room 601 Taub Bld.
- Advisor:
- Prof. Benny Kimelfeld

Managing data inconsistency has been one of the major challenges in the research and practice of database management. Database inconsistency arises for different reasons and in different applications. Nowadays, many applications obtain information from imprecise sources (e.g., social encyclopedias, social networks, and sensors attached to appliances) via imprecise procedures (e.g., natural-language processing, signal processing, and image analysis). Inconsistency may also arise when integrating conflicting data from different (possibly consistent) sources. During the past two decades, researchers have established, developed and investigated a principled approach to managing database inconsistency via the notion of database repairs. A repair of an inconsistent database is traditionally defined as a consistent database that differs from the inconsistent one in a "minimal" way. We explore various problems arising in the challenge of measuring how inconsistent a database is. Inconsistency measures are important for estimating the extent to which a database is trustworthy, and the effort required to clean it. Such measures are useful for implementing progress bars in data cleaning systems, as well as for recommending next steps in interactive systems, and estimating the potential usefulness and cost of incorporating databases for downstream analytics. Specifically, we explore the computational complexity of two inconsistency measures. The first measure is based on the cost of a minimal repair (i.e., the minimal number of operations required to obtain consistency), and the second is based on the number of repairs. Then, we revisit the second measure in the presence of preferences among tuples in the database. Often, repairs are not equally legitimate, as it is desired to prefer one over another; for example, one tuple is regarded more reliable than another, or a more recent tuple should be preferred to an earlier one. Motivated by these considerations, researchers have introduced and investigated the framework of preferred repairs that incorporates preferences among database tuples. We show that the presence of preferences significantly affects the computational complexity.

### Query Evaluation in Election Databases

- Speaker:
- Muhammad Tibi, M.Sc. Thesis Seminar
- Date:
- Wednesday, 23.10.2019, 15:00
- Place:
- Room 601 Taub Bld.
- Advisor:
- Prof. Benny Kimelfeld

Election databases are the main elements of a recently introduced framework that aims to create bridges between the computational social choice and the data management communities. An election database consists of incomplete information about the preferences of voters, in the form of partial orders, alongside with standard database relations that provide contextual information. Earlier work in computational social choice focused on the computation of possible winners and necessary winners that are determined by the available incomplete information and the voting rule at hand. The presence of the relational context, however, permits the formulation of sophisticated queries about voting rules, candidates, potential winners, issues, and positions on issues. Such queries can be given possible answer semantics and necessary answer semantics on an election database, where the former means that the query is true on some completion of the given partial orders and the latter means that the query is true on every such completion. We carry out a systematic investigation of query evaluation on election databases by analyzing how the interaction between the partial preferences, the voting rules and the relational context impacts on the complexity of query evaluation. To this effect, we focus on positional scoring rules and unions of conjunctive queries. We establish a number of results that delineate the complexity of the possible answers and of the necessary answers for different positional scoring rules and for various classes of unions of conjunctive queries. Furthermore, we show that query evaluation is fixed parameter tractable, where the parameter is the number of candidates in the election.

### CS Jubilee Event

- Date:
- Tuesday, 29.10.2019, 16:30
- Place:
- CS Taub Building, Technion

Technion CS celebrates jubilee and invites you to CS City - a festival of science and technology for the whole family which will be held on Tuesday, October 29, 2019 starting at 4:30 pm at the CS Taub Building, Technion.

Participation is free, but pre-registration is required.

You are all invited!### A Calculus for Brain Computation

- Speaker:
- Prof. Christos Papadimitriou, Special Guest Talk, Harvey Prize Winner
- Date:
- Monday, 4.11.2019, 11:00
- Place:
- Room Auditorium 2 Taub Bld.
- Affiliation:
- Computer Science Dept., Columbia University, New York, NY.
- Host:
- Seffi Naor

How does the brain beget the mind? How do molecules, cells and synapses effect reasoning, intelligence, language, science? Despite dazzling progress in experimental neuroscience we do not seem to be making progress in the overarching question -- the gap is huge and a completely new approach seems to be required. As Richard Axel recently put it: "We don't have a logic for the transformation of neural activity into thought." What kind of formal system would qualify as this "logic"? In this talk I will propose an answer. (Joint work with Santosh Vempala, Dan Mitropolsky, Mike Collins, and Larry Abbott.) Short Bio: Christos Papadimitriou is currently the Donovan Family Professor of Computer Science at Columbia University. Before that he taught at UC Berkeley for 20 years, and earlier he taught at Harvard, MIT, the National Technical University of Athens, Stanford, and UC San Diego. Papadimitriou has been awarded the Knuth Prize, IEEE’s John von Neumann Medal, the EATCS Award, the IEEE Computer Society Charles Babbage Award, and the Gödel Prize. He is a fellow of the Association for Computer Machinery and the National Academy of Engineering, and a member of the National Academy of Sciences. This year Papadimitriou is the recipient of the prestigious Harvey Prize. Papadimitriou received his BS in Electrical Engineering from Athens Polytechnic in 1972. He has a MS in Electrical Engineering and a PhD in Electrical Engineering/Computer Science from Princeton, received in 1974 and 1976, respectively. =============================== Refreshments will be served from 10:45 Lecture starts at 11:00

### Training Neural Networks: The Bigger the Better?

- Speaker:
- Ohad Shamir - COLLOQUIUM LECTURE
- Date:
- Tuesday, 5.11.2019, 14:30
- Place:
- Room 337 Taub Bld.
- Affiliation:
- Weizmann Institute
- Host:
- Yuval Filmus

Artificial neural networks are nowadays routinely trained to solve challenging learning tasks, but our theoretical understanding of this phenomenon remains quite limited. One increasingly popular approach, which is aligned with practice, is to study how making the network sufficiently large (a.k.a. ''over-parameterized'') makes the associated training problem easier. In this talk, I'll describe some of the possibilities and challenges in understanding neural networks using this approach. Based on joint works with Itay Safran and Gilad Yehudai. Short Bio: ============ Ohad Shamir is a faculty member at the Department of Computer Science and Applied Mathematics at the Weizmann Institute. He received his PhD in 2010 at the Hebrew University, and between 2010-2013 and 2017-2018 was a researcher at Microsoft Research in Boston. His research focuses on theoretical machine learning, in areas such as theory of deep learning, learning with information and communication constraints, and topics at the intersection of machine learning and optimization. He received several awards, and served as program co-chair of COLT as well as a member of its steering committee. =============================== Refreshments will be served from 14:15 Lecture starts at 14:30

### Is there Logic in Software Engineering?

- Speaker:
- Yuri Gurevich - COLLOQUIUM LECTURE
- Date:
- Tuesday, 12.11.2019, 14:30
- Place:
- Room 337 Taub Bld.
- Affiliation:
- University of Michigan
- Host:
- Assaf Schuster

When this logician moved to theoretical computer science, this did not seem such a big deal to him. The transition was seamless. The transition to software engineering was radical. Microsoft research invited me to come, start a group and use my ideas to build tools. That was enticing and frightening. The chances of success seemed remote. But it worked, thanks to the engineering talent that my group was lucky to attract. Our Spec Explorer became indispensable when EU demanded that Microsoft provides high-level executable specifications of numerous communication protocols. I did not prove many logic theorems during my 20 years in software industry. Yet, looking back, I see the importance of logic - mostly logic framework rather than theorems - to software industry. Software engineers do formal logic day in and day out, even though they may not realize that. As a rule, they have not studied logic. Instead, they spent a lot of time studying calculus which they use rarely, if ever. I will try to illustrate why logic is relevant for software industry and why it is hard for software engineers to pick it up. Time permitting; I'll say a few words on the state of quantum computing. (The last five years of my Microsoft career I was with the Quantum Architecture and Computing group). Short Bio: Yuri Gurevich is Professor Emeritus at the University of Michigan, recently retired from Microsoft Research where he worked 20 years as a Principal Researcher. He is ACM Fellow, Guggenheim Fellow, EATCS Fellow, a foreign member of Academia Europaea, and Dr. Honoris Causa of a Belgian and Russian universities. =============================== Refreshments will be served from 14:15 Lecture starts at 14:30

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