^December January – 2005 ^February

Suppose we are given a list of numbers and we wish to determine whether it is sorted. That problem obviously requires reading the entire list. But Ergun, Kannan, Kumar, Rubinfeld and Viswanathan showed in 1998 that if we know in advance that our list is either sorted or far from sorted, we can perform the test by examining only a small portion of the list. Sorting is thus an example of a testable property, as defined by Rubinfeld and Sudan in 1996, where we can distinguish between objects having the property and objects that are far from having it by examining only a small part of the object.

We will start by defining property testing, then talk about monotonicity testing which is a generalization of the sortedness testing problem. We will present algorithms and lower bounds that give partial classification of properties in terms of their query complexity, that is, the number of samples needed to test for them.

Bio:

Sofya recieved her Ph.D. from MIT in 2003. Last year she was a post-doc at the Hebrew University of Jerusalem, supported by the Lady Davis Fellowship. Currently she is a post-doc at the Weizmann Institute of Science.

Computer science education is a sub-field of mathematics and science education, which in turn is a sub-field of the discipline of education. Thus, the research of computer science education is based on methodologies of social science, as well as on understanding the special nature of computer science – as a discipline that has something in common with mathematics, science and engineering, but also has unique characteristics of its own. The research of computer science education focuses on two educational processes:

The teaching process: What should we teach our students in order to better prepare them to be computer science graduates, and how should we teach it? The learning process: How do our students interpret and perceive what we teach them?

In this talk I will give a short survey of the current research in computer science education, and its possible effects on teaching computer science in universities. In particular, I intend to relate to two aspects of my recent work: Teaching reductive thinking (joint work with Judith Gal-Ezer) and teaching backward reasoning (joint work with David Ginat)

Michal Armoni completed her B.A. and M.Sc. in computer science in the Technion in 1989 and 1991, respectively. In 2003 Michal submitted her Ph.D. thesis, on teaching computational models to high school students. The doctoral research was done in the School of Education in Tel-Aviv University. For the last 10 years she is a member of the computer science department in the Open University of Israel, where she chaired a team developing teaching materials in computational models for high school students, and is now the coordinator of two academic courses in algorithms. For the last four years she teaches in the School of Education in Tel-Aviv University, in the computer science teaching certificate track. She has a rich experience of teaching computer science in college, university and high school. As of January 2005 she is a postdoctorant in the department of Education in Technology and Science in the Technion.

A naturally occurring question in cryptography is how well the composition of simple permutations drawn from a simple distribution resembles a random permutation. Although such constructions are a common source of security for block ciphers like DES and AES, their mathematical justification (or lack thereof) is troubling.

Motivated by this question, we study the random composition of a small family of $O(n^3)$ simple permutations on ${0,1}^n$. Specifically we ask how many randomly selected simple permutations need be composed to yield a permutation that is close to k-wise independent. We improve on the results of Gowers 1996 and Hoory, Magen, Myers and Rackoff 2004, and show that up to a polylogarithmic factor,$n^2*k^2$ compositions of random permutations from this family suffice. We also introduce the new notion of closeness to k-wise independence against adaptive adversaries and show the constructed permutation has the stronger property. In addition, our results give an explicit construction of a degree $O(n^3)$ Cayley graph of the alternating group of $2^n$ objects with a spectral gap $\Omega(1/(n^2 * 2^n))$, which is a substantial improvement over previous constructions.

This question is essentially about the rapid mixing of a certain Markov chain, and the proofs are base on the comparison technique.

Joint work with Alex Brodsky.

Short bio:
I graduated the Hebrew University at 2002 with a Ph.D thesis titled "On graphs of high girth", supervised by Prof. Nati Linial. After that I have been a Postdoctoral Fellow at the University of Toronto and recently at the University of British Columbia.

My primary research is on graph eigenvalues, expansion and their connection to other fields. These include error correcting codes, geometric proof systems, cryptography, and computation. Of particular interest to me are the extremal properties of irregular graphs, and graphs of high girth. In addition, I have a rich practical experience from working in the industry in programming, real time systems, OS internals, VLSI design, and digital signal processing.

Given a graph $G=(V,E)$ with $|V|=n$, we consider the following problem: place $n$ points on the vertices of $G$ independently and uniformly at random. Once the points are placed, relocate them using bijection from the points to the vertices that minimize the maximum distance between the random place of the points and their target vertices.

We look for an upper bound on this maximum relocation distance that holds with high probability (over the initial placements of the points).

For general graph we prove that the maximum relocation distance is $O(\sqrt{n})$ w.h.p., for grid we prove that the maximum relocation

This is joint work with Ralf Klasing, Alfredo Navarra, St'ephane P'erennes.

Protecting the confidentiality of information manipulated by computing systems is a long-standing yet increasingly important problem. The standard way to protect confidential data is access control: some privilege is required in order to access files or objects containing the confidential data, but once information is released from its container, the accessing program may improperly transmit the information in some form. To ensure that information is used only in accordance with the relevant confidentiality policies, it is necessary to analyze how information flows within the using program.

This talk briefly overview (programming) language-based techniques, such as program semantics and analysis, for the specification and enforcement of security policies for data confidentiality and discuss in more details an information-flow security analysis for the Java bytecode.

(Joint work with Fausto Spoto)

Short BIO

---

02/2003 - present: Marie-Curie Fellow in the computer science department of the University of Verona, Italy.

10/1998 - 10/2002: Ph.D. in Computer Science at Ben-Gurion University of the Negev, Beer-Sheva, Israel. Thesis: Semantic Based WorkBench For Termination Analysis of Logic Programs. Advisor: Prof. Michael Codish.

10/1996 - 10/1998: M.Sc. in Mathematics and Computer Science at Ben-Gurion University of the Negev, Beer-Sheva, Israel.

10/1993 - 10/1996 B.Sc. in Mathematics and Computer Science at Ben-Gurion University of the Negev, Beer-Sheva, Israel.

Research Interests

---

Keywords: Program Analysis, Abstract Interpretation, Termination Analysis, Language-Based Security

My research interests in the are of "Semantic Based Program Analysis" is a mixture of theoretical and practical computer science. I apply techniques like abstract interpretation and use them to optimize programs, prove that programs will terminate and reason about the program's properties without executing the program. These techniques aid in the program development process as well as compiler optimizations.