Colloquia and Seminars

To join the email distribution list of the cs colloquia, please visit the list subscription page.

Upcoming Colloquia & Seminars

  • Topics in Sparse Representation Modeling and Applications

    Speaker:
    Javier Turek, Ph.D. Thesis Seminar
    Date:
    Wednesday, 26.11.2014, 10:30
    Place:
    Taub 601
    Advisor:
    Prof. Irad Yavneh and Prof. Michael Elad

    In cardiac ultrasound, clutter is an artifact that obscures parts of the heart and may cause inaccurate diagnosis. In particular, a cluttered ultrasound signal is seen as a superposition of tissue, clutter and noise components. In this work, we apply a method called Morphological Component Analysis (MCA) for sparse signal separation with the objective of reducing such clutter artifacts. The MCA approach assumes that the signals corresponding to the clutter and the tissue have each a sparse representation under some dictionary of atoms (a matrix), and the separation is achieved by finding these sparse representations. We present several novel alternatives to train the dictionaries adaptively both from on-line and off-line data. The presented methods outperform the state-of-the-art Singular Value Filter (SVF), show a lower impact on tissue sections, are robust to the input data characteristics, and yield state-of-the-art performance. In a joint work with J. Sulam, we further extend our approach by presenting a method based on a joint sparsity model that fuses the first and second harmonic images while performing clutter mitigation and noise reduction.

  • ceClub: On the Scalability of Hop-by-hop Packet Routing

    Speaker:
    Gabor Retvari (Budapest University (BME-TMIT))
    Date:
    Wednesday, 26.11.2014, 11:30
    Place:
    EE Meyer Building 1007

    Many of our computer networks, not the least of which the Internet, are built upon hop-by-hop destination-based routing. Here, network devices are equipped with a unique address and routers use giant lookup tables to forward packets towards the intended destination based on the address encoded in the header. At the moment, it is not clear whether we will be able to scale the hop-by-hop routing paradigm into the future economically, as the memory requirement for storing these giant lookup tables keeps on increasing at a fast pace. The main goal of this talk is to highlight some recent results in the related research field on routing scalability.

    First, we present the fundamental impossibility result of the field, asserting that no routing scheme can achieve better than linearly increasing routing tables in general. We extend this result from shortest-path routing to general routing policies using an algebraic approach and, for the special case of BGP, we state a Separation Theorem that divides scalable BGP routing policies from unscalable ones. We then do a reality check: we show that IP forwarding tables used in Internet routers can be compressed way beyond what the worst-case analysis would suggest. To do so, we systematically squeeze out every single bit of redundancy from the most common forwarding table data structure, the prefix tree. We find that compression in this case not only does not ruin lookup performance but it even improves it, so this one turns out to be one of those rare cases in computer science when there is no space-time trade-off. Finally, we speculate about the reasons behind this seemingly magical compressibility of IP forwarding tables. We present preliminary analysis suggesting that some form of "heterogeneity" might be a main factor behind compressibility, we attempt to characterize this notion using the concept of certain routing table symmetries, and then we sketch the scalability map of the Internet which we then use to make some bold predictions.

    Bio:
    Gábor Rétvári received the M.Sc. and Ph.D. degrees in electrical engineering from the Budapest University of Technology and Economics (BME). He is now a Senior Research Fellow at the High Speed Networks Laboratory, BME. He has been passionate about the questions of routing scalability for a long time and he has done plenty of research in this field, using a diverse set of mathematical tools ranging from abstract algebra to computational geometry and, more recently, information-theory. He maintains numerous open source scientific tools written in Perl, C and Haskell.

  • Theory Seminar: Representative Sets For Multisets

    Speaker:
    Ariel Gabizon (CS, Technion)
    Date:
    Wednesday, 26.11.2014, 12:30
    Place:
    Taub 201

    The notion of a q-representative set for a family of subsets, originally arising in the Two-Families Theorem of Bollobás, has recently proven to be very useful in the design of parameterized and exact algorithms.

    In this talk I will explain this notion. Then, to illustrate its usefulness, I will show how it was used by Fomin, Lokshtanov and Saurabh to design a fast algorithm for finding long simple paths in a directed graph.

    Finally, I will describe a recent work where we generalize the notion of a representative set to a family of multisets and derive algorithmic applications.

    Based on joint work with Daniel Lokshtanov and Michal Pilipczuk

  • Job Scheduling Mechanisms for Cloud Computing

    Speaker:
    Jonathan Yaniv, Ph.D. Thesis Seminar
    Date:
    Wednesday, 26.11.2014, 13:30
    Place:
    Taub 601
    Advisor:
    Prof. Joseph (Seffi) Naor

    We present new job scheduling algorithms and pricing schemes for computing systems. The scheduling mechanisms we design provide guaranteed Service Level Agreements (SLAs) to users (e.g., meeting job deadlines), while obtaining desired properties driven by both system-aware goals and economic considerations. In our framework, users submit jobs along with a value function that specifies the user value (i.e., willingness to pay) as a function of the job completion time. In addition, each user submits other properties of their job, such as resource requirements or inner job dependencies. The scheduler, in response, allocates resources to users under capacity limitations to maximize the total value gained by completed jobs. We consider several allocation models, both offline and online, and develop novel scheduling algorithms that provide high guaranteed value, as well as high resource utilization in practice. Based on our scheduling algorithms, we construct truthful allocation and pricing mechanisms for public clouds, in which users are incentivized to report their true job properties. We empirically evaluate the benefits of our approach through simulations on job traces taken from Microsoft clusters, and show that the revenues obtained by our approach are high compared to commonly used fixed-price mechanisms, which charge a fixed price per resource unit.

  • CGGC Seminar: Functional Fluids on Surfaces

    Speaker:
    Omri Azencot (CS, Technion)
    Date:
    Sunday, 30.11.2014, 14:30
    Place:
    Room 337-8 Taub Bld.

    Fluid simulation plays a key role in various domains of science including computer graphics. While most existing work addresses fluids on bounded Euclidean domains, we consider the problem of simulating the behavior of an incompressible fluid on a curved surface represented as an unstructured triangle mesh. Unlike the commonly used Eulerian description of the fluid using its time-varying velocity field, we propose to model fluids using their vorticity, i.e., by a (time varying) scalar function on the surface. During each time step, we advance scalar vorticity along two consecutive, stationary velocity fields. This approach leads to a variational integrator in the space continuous setting. In addition, using this approach, the update rule amounts to manipulating functions on the surface using linear operators, which can be discretized efficiently using the recently introduced functional approach to vector fields. Combining these time and space discretizations leads to a conceptually and algorithmically simple approach, which is efficient, time-reversible and conserves vorticity by construction. We further demonstrate that our method exhibits no numerical dissipation and is able to reproduce intricate phenomena such as vortex shedding from boundaries.

  • Principles of Shape Analysis

    Speaker:
    Mooly Sagiv - Colloquium Lecture
    Date:
    Tuesday, 2.12.2014, 14:30
    Place:
    Room 337-8 Taub Bld.
    Link:
    http://www.cs.technion.ac.il/~colloq/20141202_14_30_Sagiv.html
  • ceClub: Making Machine Learning Accessible with GraphLab

    Speaker:
    Danny Bickson (GraphLab)
    Date:
    Wednesday, 3.12.2014, 11:30
    Place:
    Room 337-8 Taub Bld.

    GraphLab started as research project at Carnegie Mellon University were our main goal was implementing machine learning methods in large scale, (and writing papers about it!). Despite thousands of users of our open source software (and many papers written), the experience of setting up the system and using a distributed system was quite frustrating, where our target audience was mainly double PhDs with machine learning and graph theory & distributed systems background.

    When forming a company around GraphLab, we have decided to switch our focus and make machine learning much more accessible for the masses. In this talk I will summarize our experience in this direction. I will describe data structures we found useful for many commonly repeating computation patterns in machine learning, including support for dense data, graph (sparse) data, text records and even images. I will describe how we tackle the problem of wrapping up machine learning algorithms in a way which is user friendly to non experts, while algorithmic details can be tweaked layer. During the talk I will show many demos of cool applications that run on GraphLab.

    About GraphLab: GraphLab is a popular open source big data analytics project initiated in 2009 at Carnegie Mellon University. GraphLab implements numerous machine learning algorithms using a highly efficient multicore machines and over clusters. A year and a half ago we have formed a company in Seattle to backup the open source project, and grown to a machine learning research group of around 12 PhDs. GraphLab is free for academic usages, and has a major open source component.

    Bio:
    Danny is holding a PhD in distributed systems at the Hebrew University (advised by Prof. Danny Dolev and Prof. Dahlia Malkhi), and was a postdoc at the machine learning department at Carngie Mellon University (advised by Prof. Carlos Guestrin and Prof. Joe Hellerstein from Berkeley). Danny was involved in the GraphLab project from its early stages and is a co-founder of the GraphLab company. His research interests are distributed algorithms and large scale machine learning.

  • The Cryptographic Lens

    Speaker:
    Shafi Goldwasser - Colloquium Lecture
    Date:
    Tuesday, 9.12.2014, 14:30
    Place:
    Room 337-8 Taub Bld.
    Link:
    http://www.cs.technion.ac.il/~colloq/20141209_14_30_Goldwasser.html
  • CGGC Seminar: Precise Contact Motion Planning for Freeform Geometry

    Speaker:
    Yong Joon Kim (CS, Technion)
    Date:
    Sunday, 14.12.2014, 14:30
    Place:
    Room 337-8 Taub Bld.

    Generation of precise contact motions for freeform geometry is essential for many applications such as mechanical and manufacturing engineering and motion planning in robotics. Yet contemporary approaches construct the contact motions of geometric objects only for simple geometric objects, typically those bounded by line segments and circular arcs. In this talk, we present an efficient algorithm for constructing precise contact motions (within machine precision) to the case of general freeform planar objects bounded by B-spline curves. We then extend the algorithm to the tool path computation for the CNC machining.

  • Scalable algorithms for translating natural language to logical form

    Speaker:
    Jonathan Berant - CS-Lecture
    Date:
    Sunday, 21.12.2014, 14:30
    Place:
    Room 337-8 Taub Bld.
    Link:
    http://www.cs.technion.ac.il/~colloq/20141221_14_30_Bernat.html
  • Lessons Learned from and for Requirements Engineering and Building Construction: A Case Study of Requirements Engineering for a Synagogue Kitchen with Use Cases and Scenarios

    Speaker:
    Daniel M. Berry - Colloquium Lecture -
    Date:
    Wednesday, 24.12.2014, 14:30
    Place:
    Room 337-8 Taub Bld.
    Link:
    http://www.cs.technion.ac.il/~colloq/20141224_14_30_Berry.html
  • Aspects of Submodular Maximization Subject to a Matroid Constraint

    Speaker:
    Moran Feldman - CS-Lecture
    Date:
    Thursday, 1.1.2015, 14:30
    Place:
    Room 337-8 Taub Bld.
    Link:
    http://www.cs.technion.ac.il/~colloq/20150101_14_30_Feldman.html
  • Parallel Repetition From Fortification

    Speaker:
    Dana Moshkovitz - Colloquium Lecture -
    Date:
    Thursday, 8.1.2015, 12:30
    Place:
    Room 337-8 Taub Bld.
    Link:
    http://www.cs.technion.ac.il/~colloq/20150108_12_30_Moshkovitz.html
  • When Exactly Do Quantum Computers Provide a Speedup?

    Speaker:
    Scott Aaronson - Colloquium Lecture
    Date:
    Thursday, 8.1.2015, 14:30
    Place:
    Room 337-8 Taub Bld.
    Link:
    http://www.cs.technion.ac.il/~colloq/20150108_14_30_Aaronson.html