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

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

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

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

דובר:
אדם מוריסון (מדעי המחשב, טכניון)
תאריך:
יום רביעי, 12.3.2014, 11:30
מקום:
טאוב 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

דובר:
אלעזר גולדברג (מכון ויצמן למדע)
תאריך:
יום רביעי, 12.3.2014, 12:30
מקום:
טאוב 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

דובר:
שירי אזנקוט (אונ' וושינגטון)
תאריך:
יום חמישי, 13.3.2014, 13:00
מקום:
חדר 337, בניין טאוב למדעי המחשב

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

דובר:
רמי רוזן
תאריך:
יום שני, 17.3.2014, 18:30
מקום:
טאוב 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

דובר:
Noam Nisan - Colloquium Lecture
תאריך:
יום שלישי, 18.3.2014, 14:30
מקום:
חדר 337-8 טאוב.
קישור:
http://www.cs.technion.ac.il/~colloq/20140318_14_30_Nisan.html
• ### Design and Management of Complex Distributed Systems: Optimization and Game-Theoretic Perspectives

דובר:
אמיר נהיר, הרצאה סמינריונית לדוקטורט
תאריך:
יום שני, 31.3.2014, 11:00
מקום:
טאוב 601
מנחה:
Prof. Ariel Orda, Prof. Danny Raz

The design and management of current distributed systems is a very complex task. This is mainly due to the fact that typical systems are very large and are often not controlled by a single entity. For example, the Internet is composed of independent administrative entities, called Autonomous Systems (ASs), and the overall behavior is determined by a non-trivial combination of the different policies of each AS and the actions of the end-users. When designing such a system, one must consider the fact that, while the system's designer may have some idea of optimal system-wide behavior, it has to consider very different possible policies and end-user actions, which determine the actual system performance. Cloud computing is an emerging computing paradigm in which tasks are assigned to a combination of connections, software and services accessed over a network. This network of servers and devices is collectively known as "the cloud". Computing at the scale of the cloud allows users to access supercomputer-level power using a thin client or another access point, like an iPhone or a laptop. Since end-users are given access to supercomputer-level resources, their effect over the system's overall performance is greater than ever. This raises multiple research questions related to the management and performance of cloud computing systems in light of the end-user's selfishness. In this work, we analyze the topologies of networks constructed by selfish users as well as the overall system performance when selfish end-users may split work between a shared resource (cloud) and private resources. We further study task assignment policies that are specifically adequate for large-scale distributed systems, and show that they provide new capabilities in improving system performance. In particular, we develop new resource allocation algorithms that converge to a working point that balances the end-user experience with the operational costs of leasing resources from the cloud provider. The talk will focus on a novel scheme supporting elasticity in large scale cloud-based services and will assume no prior knowledge.