קולוקוויום וסמינרים

כדי להצטרף לרשימת תפוצה של קולוקוויום מדעי המחשב, אנא בקר בדף מנויים של הרשימה.


Computer Science events calendar in HTTP ICS format for of Google calendars, and for Outlook.

Academic Calendar at Technion site.

קולוקוויום וסמינרים בקרוב

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

    דובר:
    ענבר סרוסי (אונ' תל-אביב)
    תאריך:
    יום שלישי, 26.3.2019, 11:30
    מקום:
    חדר 337, בניין טאוב למדעי המחשב

    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.

  • Theory Seminar: Improved Bounds for Excluded Grid Theorem

    דובר:
    זיהאן טאן (אונ' שיקגו)
    תאריך:
    יום רביעי, 27.3.2019, 12:30
    מקום:
    טאוב 201

    We study the Excluded Grid Theorem, a fundamental structural result in graph theory, that was proved by Robertson and Seymour in their seminal work on graph minors. The theorem states that there is a function f, such that for every integer g > 0, every graph of treewidth at least f(g) contains the (g×g)-grid as a minor. For every integer g>0, let f(g) be the smallest value for which the theorem holds. Establishing tight bounds on f(g) is an important graph-theoretic question. Robertson and Seymour showed that f(g) is at least of order g^2 log g). For a long time, the best known upper bounds on f(g) were super-exponential in g. The first polynomial upper bound of f(g) = O(g^98 poly log g) was proved by Chekuri and Chuzhoy. It was later improved to f(g) = O(g^36 poly log g), and then to f(g) = O(g^19 poly log g). In this talk we present our recent work that further improves this bound to f(g) = O(g^9 poly log g) via a simpler proof. Moreover, while there are natural barriers that seem to prevent the previous methods from yielding tight bounds for the theorem, it seems conceivable that the techniques proposed in this thesis can lead to even tighter bounds on f(g).

  • CGGC Seminar: Volumetric Frame Fields for Hexahedral Meshing

    דובר:
    דוד פלמר (MIT)
    תאריך:
    יום חמישי, 28.3.2019, 11:00
    מקום:
    חדר 337, בניין טאוב למדעי המחשב

    The hexahedral meshing problem is the volumetric analog of the quad meshing problem, with analogous applications in finite element modeling. One might expect that frame field–based methods, which have proven effective in quad meshing, would extend naturally to the volumetric case. Unfortunately, several problems arise in attempting this extension. The geometry of frames becomes significantly more complicated, making optimization over frames more challenging. Moreover, field and mesh topology is far more complicated in 3D due to non-commutative symmetries.

    I will discuss our recent work (joint with David Bommes and Justin Solomon), in which we examine the geometry of two different spaces of frames and develop tailored optimization techniques to achieve state-of-the-art results. Next, time permitting, I will detail some observations (joint with Paul Zhang) about integrability and meshability of frame fields.

    Finally, I will talk about tantalizing insights we have gleaned from the physics of topological defects in ordered media.

  • Graph Balancing with Orientation Costs

    דובר:
    רן יחזקאל, הרצאה סמינריונית למגיסטר
    תאריך:
    יום שני, 1.4.2019, 11:30
    מקום:
    טאוב 601
    מנחה:
    Roy Schwartz

    We consider the Graph Balancing problem, where we are given an undirected multigraph with edge weights and orientation costs. The goal is to find an orientation of the edges that minimizes the worst weighted incoming degree of a vertex (also known as makespan) while minimizing the total orientation cost. Graph Balancing is an interesting special case of the well-known Generalized Assignment Problem (GAP), which is perhaps one of the most famous and extensively studied problems in scheduling theory. In this work we focus on bi-criteria algorithms for Graph Balancing that consider the tradeoff between makespan and the total orientation cost. While a 2-approximation with respect to the makespan with no loss in the total orientation cost is known [Shmoys-Tardos ??], the problem of achieving an approximation better than 2 with respect to the makespan with orientation costs was not studied. We achieve the following results: (1) we show that using known approaches to Graph Balancing any approximation better than 2 with respect to the makespan must lose in the orientation cost; (2) we present an algorithm that achieves a bounded tradeoff between makespan and orientation cost; and (3) we consider extensions of Graph Balancing that include hyperedges and unrelated weights and present improved algorithms for these problems. To the best of our knowledge, for the latter, we present the first approximation algorithm that achieves an approximation better than with respect to the makespan.

  • From Cognitive Biases to the Communication Complexity of Local Search

    דובר:
    Shahar Dobzinski - COLLOQUIUM LECTURE
    תאריך:
    יום שלישי, 2.4.2019, 14:30
    מקום:
    חדר 337 טאוב.
    השתייכות:
    Weizmann Institute, Applied Math and Computer Science Dept.
    מארח:
    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.

  • On-the-fly Model Checking with Guided Abstraction

    דובר:
    גל שדה, הרצאה סמינריונית למגיסטר
    תאריך:
    יום שלישי, 2.4.2019, 15:30
    מקום:
    טאוב 601
    מנחה:
    Prof. O. Grumberg

    Model checking is an automatic verification method that accepts a system model and a specification, and checks whether the model satisfies the specification. CTL is a branching temporal logic suitable for specifying behaviors of both software and hardware systems. In this work, we present a novel approach that combines on-the-fly verification with abstraction in order to obtain an efficient model checking. On-the-fly verification ensures that only parts that are needed for determining the satisfaction of the specification are developed. The abstraction is used to generalize information that was computed on fragments of the model, thus allowing the algorithm to halt without developing the entire model. We implemented our algorithm, compared it with a state-of-the-art CTL model checker and received very encouraging results.

  • Knowledge-Based Learning through Feature Generation

    דובר:
    מיכל בדיאן, הרצאה סמינריונית למגיסטר
    תאריך:
    יום ראשון, 7.4.2019, 14:30
    מקום:
    טאוב 601
    מנחה:
    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

    דובר:
    ליאת פטרפרוינד, הרצאה סמינריונית לדוקטורט
    תאריך:
    יום שני, 8.4.2019, 14:30
    מקום:
    טאוב 601
    מנחה:
    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.

  • Some systems engineering problems and a little bit of theory

    דובר:
    Eitan Bachmat - COLLOQUIUM LECTURE
    תאריך:
    יום שלישי, 16.4.2019, 14:30
    מקום:
    חדר 337 טאוב.
    השתייכות:
    Ben-Gurion University
    מארח:
    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

    תאריך:
    יום רביעי, 17.4.2019, 12:15
    מקום:
    חדר 337 טאוב.

    היום הפתוח לקראת ההרשמה לשנה"ל תש"פ מזמין בוגרי תואר ראשון מצטיינים מכל האוניברסיטאות להגיע לטכניון ולהתרשם מהפקולטות למדעי המחשב, לפגוש חברי סגל וסטודנטים לתארים מתקדמים ולשמוע הרצאה מרתקת מפי דר' טל כהן, דירקטור פיתוח תוכנה, גוגל: "האם תואר מתקדם אכן מקדם?"
    .
    האירוע יתקיים ביום ד', 17 באפריל 2019, בין השעות 12:15-15:00, בבניין טאוב למדעי המחשב, חדר 337 (קומה 3).

    תוכנית היום תכלול סקירה על הלימודים ותנאי הקבלה וכן הרצאות מדעיות. לכל מועמד תתאפשר פגישה אישית עם סגן הדיקן לתארים מתקדמים בפקולטה.

    המעוניינים להגיע לאירוע מתבקשים להירשם מראש.

    פרטים נוספים ותוכנית מלאה.

  • Computer Agents that Interact Proficiently with People

    דובר:
    Sarit Kraus - COLLOQUIUM LECTURE
    תאריך:
    יום שלישי, 30.4.2019, 14:30
    מקום:
    חדר 337 טאוב.
    השתייכות:
    Bar-Ilan University
    מארח:
    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

    דובר:
    Amir Globerson - COLLOQUIUM LECTURE
    תאריך:
    יום שלישי, 4.6.2019, 14:30
    מקום:
    חדר 337 טאוב.
    השתייכות:
    Tel-Aviv University
    מארח:
    Yuval Filmus

    TBA

  • SYNTECH: Synthesis Technologies for Reactive Systems Software Engineers

    דובר:
    Shahar Maoz - COLLOQUIUM LECTURE
    תאריך:
    יום שלישי, 11.6.2019, 14:30
    מקום:
    חדר 337 טאוב.
    השתייכות:
    School of Computer Science, Tel-Aviv University
    מארח:
    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.