# Colloquia and Seminars

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

## Upcoming Colloquia & Seminars

• ### Pixel Club: Image Dehazing

Speaker:
Raanan Fattal (CS & EE, The Hebrew University of Jerusalem)
Date:
Tuesday, 11.3.2014, 11:30
Place:
Room 337-8 Taub Bld.

Photographs of hazy scenes typically have low-contrast and offer a limited scene visibility. I will describe a new method for single-image dehazing that relies on a generic regularity in natural images in which pixels of small image patches exhibit one-dimensional distributions in pixel space. I will derive a local formation model that explains this formation in the context of hazy scenes and use it for recovering the scene transmission based on the models' offset. Moreover, this model allows identifying and dismissing pixels that do not follow it and hence, unlike existing approaches that follow their assumptions across the entire image, the new algorithm validates its hypotheses and obtains more reliable estimates where possible. I will also describe a Markov random field model that is dedicated for producing complete and regularized transmission maps. Unlike traditional field models that consist of local coupling, the new model is augmented with long-range connections between pixels of similar color. This allows the algorithm to properly resolve the transmission in isolated regions where nearby pixels do not offer relevant information. An extensive evaluation of the new method over different types of images and its comparison to state-of-the-art methods on established benchmark images show a consistent improvement in the accuracy of the estimated scene transmission and recovered haze-free radiances.

• ### Bioinformatics Forum: Algorithmic Techniques for RNA Secondary Structure Prediction

Speaker:
Shay Zakov (Computer Science and Engineering, UCSD)
Date:
Tuesday, 11.3.2014, 13:30
Place:
Taub 701

The main role of RNA as a mediator in the process of protein construction out of DNA information, as expressed in Crick's "central dogma of molecular biology", is challenged by recent discoveries regarding the amount of non-protein-coding RNA (ncRNA) being transcribed, and the diverse functionalities of some of these molecules. Some functional RNA molecules are known for several decades now (e.g. tRNA and ribosomal RNA), and other were more recently discovered (e.g. riboswitches), yet it is speculated that many additional ncRNA molecules carry functionalities which are still unknown.

As for proteins, information regarding the structure of RNA molecules is valuable when studying their functional roles. Unfortunately, traditional wet-lab structural inference techniques, such as X-ray crystallography and NMR, are more difficult to apply to RNA than to proteins, and to date only a relatively small number of RNA structures were determined using these techniques. On the other hand, current sequencing technologies can determine RNA sequences in a relatively accurate, fast, and cheap manners. This motivates the development of computational tools that predict RNA structures, given RNA sequences.

In this talk, we will present some of the main computational concepts in the domain of RNA secondary structure prediction, and recent advanced algorithmic techniques that may be applied in order to improve algorithms for several related problem variants. As much as time permits, we will discuss feature-modeling and machine-learning techniques to improve the accuracy of RNA structure prediction, and sparsification and other techniques to improve both time and space complexities of the standard RNA folding algorithms.

• ### ceClub: Fence-Free Work Stealing on Bounded TSO Processors

Speaker:
Date:
Wednesday, 12.3.2014, 11:30
Place:
Taub 601

Work stealing is the method of choice for load balancing in task parallel programming languages and frameworks. Yet despite considerable effort invested in optimizing work stealing task queues, existing algorithms issue a costly memory fence when removing a task, and these fences are believed to be necessary for correctness. We will refute this belief, demonstrating fence-free work stealing algorithms for microarchitectures with a bounded total store ordering (TSO) memory model. Bounded TSO is a novel restriction of TSO---which nevertheless captures mainstream x86 and SPARC TSO processors---in which a load can only be reordered with a bounded number of prior stores.

Bio:
Adam Morrison is an Aly Kaufman Post Doctoral Fellow at the Technion, hosted by Hagit Attiya. His research focuses on bridging between the theory and practice of distributed programming---particularly concurrency and synchronization. He did his PhD work at Tel Aviv University, during which he was awarded an IBM PhD Fellowship as well as Intel and Deutch prizes.

• ### Theory Seminar: Direct Sum Testing

Speaker:
Elazar Goldenberg (Weizmann Institute of Science)
Date:
Wednesday, 12.3.2014, 12:30
Place:
Taub 201

Abstract: For a string $a \in \{0,1\}^n$ its $k$-fold direct sum encoding is a function $f_a$ that takes as input sets $S \subseteq [n]$ of size $k$ and outputs $f_a(S) = \sum_{i \in S} a_i$.

In this paper we are interested in the Direct Sum Testing Problem, where we are given a function $f$, and our goal is to test whether $f$ is close to a direct sum encoding, i.e., whether there exists some $a \in \{0,1\}^n$ such that $f(S) = \sum_{i \in S} a_i$ for most inputs $S$. By identifying the subsets of $[n]$ with vectors in $\{0,1\}^n$ in the natural way, this problem can be thought of as linearity testing of functions whose domain is restricted to the $k$-th layer of the hypercube.

We first consider the case $k=n/2$, and analyze for it a variant of the natural 3-query linearity test introduced by Blum, Luby, and Rubinfeld (STOC '90). Our analysis proceeds via a new proof for linearity testing on the hypercube, which extends also to our setting.

We then reduce the Direct Sum Testing Problem for general $k < n/2$ to the case $k = n/2$, and use a recent result on Direct Product Testing of Dinur and Steurer in order to analyze the test.

This is a joint work with Roee David, Irit Dinur, Guy Kindler and Igor Shinkar.

• ### CGGC Seminar: Eyes-Free Input on Mobile Devices

Speaker:
Shiri Azenkot (CS, University of Washington)
Date:
Thursday, 13.3.2014, 13:00
Place:
Room 337-8 Taub Bld.

I will discuss new methods and studies that aim to improve eyes-free data entry for blind mobile device users. Currently, mobile devices are generally accessible to blind people, but text entry is almost prohibitively slow. Studies show that blind people enter text on an iPhone at a rate of just 4 words per minute.

I will present Perkinput, a chording text entry method where users touch the screen with one to three fingers at a time in patterns based on Braille. Instead of soft keys, Perkinput uses concepts from signal detection theory to determine the user’s input. Based on Perkinput, I developed PassChords, a touchscreen authentication method that has no audio feedback. Unlike current eyes-free input methods, PassChords doesn’t echo a user’s input, so it won’t broadcast the user’s password for others to hear. Finally, I will discuss another modality for eyes-free input: speech. I conducted a survey and a study to determine the patterns and challenges of the use of speech input for composing paragraphs on mobile devices. I will conclude by presenting current work on eyes-free methods for correcting speech recognition errors.

Bio:
Shiri Azenkot is a PhD candidate in Computer Science at the University of Washington. Her research is in human-computer interaction and accessibility, focusing on eyes-free input on mobile devices using gestures and speech. Shiri received two Best Paper awards from ACM's ASSETS conference and has presented her work at other top HCI conferences (CHI and UIST). She received a National Science Foundation Graduate Research Fellowship and an AT&T Labs Graduate Fellowship. Shiri holds a BA in computer science from Pomona College and an MS in computer science from the University of Washington. You can find out more about her at http://shiriazenkot.com.

• ### Haifux Club: Linux Containers and the Future Cloud

Speaker:
Rami Rosen
Date:
Monday, 17.3.2014, 18:30
Place:
Taub 6

Linux Containers is a technology based on namespaces and cgroups. We will start with an half an hour rehearsal about namespaces and cgroups, which are the building blocks of Linux Containers. Then we will discuss Linux Containers implementation and Checkpoint/Restart.

• ### Complexities in Auctions and Markets

Speaker:
Noam Nisan - Colloquium Lecture
Date:
Tuesday, 18.3.2014, 14:30
Place:
Room 337-8 Taub Bld.