^June July – 2008

Computing the Fourier transform is a basic building block used in numerous applications. For data intensive applications, even the $O(Nlog N)$ running time of the Fast Fourier Transform (FFT) algorithm may be too slow, and sub-linear running time is necessary. Clearly, outputting the entire Fourier transform in sub-linear time is infeasible; nevertheless, in many applications it suffices to find only the significant Fourier coefficients, that is, the Fourier coefficients whose magnitude is at least a $tau$-fraction (say, 1%) of the $ell_2$-norm of the entire Fourier transform (ie, the sum of squared Fourier coefficients). In this paper we present an algorithm that finds the significant Fourier coefficients of functions $f$ over any finite abelian group $G$, which is: {bf Local.} The running time and number of function entries read by the algorithm is polynomial in $log N$, $1/tau$ and $L_1(f)$ (for $N=card G$ and $L_1(f)$ denoting the sum of absolute values of the Fourier coefficients of $f$). {bf Input-oblivious.} The set of entries read by the algorithm depends only on the domain $G$ and on an upper bound on the sum of Fourier coefficients $L_1(f)$, and not on the input function $f$ itself. That is, the {em same fixed} set of entries is read for all functions over the same domain and with the same upper bound on their sum of Fourier coefficients. {bf Robust to noise.} The algorithm finds the significant Fourier coefficients of $f$, even if the function entries it receives are corrupted by random noise. Furthermore, we present extensions of this algorithm to handle {em adversarial noise} in running time {em sub-linear} in the domain size. Our algorithm improves on the prior input-oblivious algorithms in: (1) handling functions over any finite abelian group, (2) being robust to noise, and (3) achieving {better running time in terms of $L_1(f)$.

We present applications of our algorithm to compressed sensing, to solving noisy variants of the Hidden Number Problem with advice, and to decoding polynomial rate Homomorphism codes and polynomial rate Multiplication codes.

The rapid accumulation of genetic material (e.g. sequencing of genes and genomes) and the prediction of new proteins should help us to better understand evolution at the molecular level. This task, however, is not trivial. First, the evolution of many organisms includes operations such as horizontal transfers (i.e. events of transferring genetic material from one lineage in the evolutionary tree to a different lineage) and rearrangements of genetic material. Thus, it requires accurate modeling of complex biological phenomena. Second, as most of the problems in the field are NP-hard, it requires designing sophisticated algorithms and heuristics for accurate and fast inference of evolutionary models. In this talk I will describe our recent attempts to address these challenges. I will discuss hardness issues related to inferring phylogenetic trees and networks, and will describe a few approaches for modeling and inferring evolution in the presence of horizontal gene transfer, partial horizontal gene transfer, and rearrangements of genetic material. No background in biology will be assumed.

This work presents research in the field of machine learning and transportation studies. Urban Traffic Control System (UTCS), which rely on a network of sensors, aim to describe real-time traffic in urban areas using a set of parameters and estimating them. Though the state of the art systems focus on data analysis, little has been done to date in terms of prediction. In this work, we describe a machine learning system for traffic flow management and control to address the problem of traffic regulation. This new algorithm is obtained by combining a Random Forests algorithm with an Adaboost algorithm as a weak learner. We show that o! ur algorithm performs relatively well on real data, and enables, according to the traffic flow evaluation model, to estimate and predict whether there is congestion or not at a given time at a given road intersection. The problem of avoiding traffic congestion can be solved by updating the signal timing of the traffic lights at an intersection in advance, based on the prediction of heavy traffic.

Abstract: The speaker works in requirements engineering (RE) and has not done any work on aspect orientation, cross-cutting cocerns, or early aspects. Nevertheless, RE is certainly early. The speaker believes that in RE, one never sees any cross-cutting concerns, but there are plenty of concerns and these are all requirements. The speaker is of the view that, in the early stages, requirements are not well enough structured that any concern can be identified as cross cutting as opposed to not cross cutting. Everything is just a concern. Nevertheless, there will certainly be cross-cutting concerns later when the required system is built.

---

Bio: Daniel M. Berry got his Ph.D. in Computer Science from Brown University in 1974. He was on the faculty of the Computer Science Department at the University of California, Los Angeles, USA from 1972 until 1987. He was in the Computer Science Faculty at the Technion, Israel from 1987 until 1999. From 1990 until 1994, he worked for half of each year at the Software Engineering Institute at Carnegie Mellon University, USA, where he was part of a group that built CMU's Master of Software Engineering program. During the 1998-1999 academic year, he visited the Computer Systems Group at the University of Waterloo in Waterloo, Ontario, Canada. In 1999, Berry moved to what is now the Cheriton School of Computer Science at the University of Waterloo. Berry's current research interests are software engineering in general, and requirements engineering and electronic publishing in the specific.

Abstract: This talk describes grounded analysis (GA) as a method to discover grounded theories (GTs) to be subjected to later empirical validation. It shows that a good instance of Requirements Engineering (RE) is an instance of GA for the purpose of discovering the artifacts that RE produces. Therefore, these artifacts are also GTs.

Work with Michael W. Godfrey, Ric Holt, Cory J. Kapser, and Isabel Ramos

Bio: Daniel M. Berry got his Ph.D. in Computer Science from Brown University in 1974. He was on the faculty of the Computer Science Department at the University of California, Los Angeles, USA from 1972 until 1987. He was in the Computer Science Faculty at the Technion, Israel from 1987 until 1999. From 1990 until 1994, he worked for half of each year at the Software Engineering Institute at Carnegie Mellon University, USA, where he was part of a group that built CMU's Master of Software Engineering program. During the 1998-1999 academic year, he visited the Computer Systems Group at the University of Waterloo in Waterloo, Ontario, Canada. In 1999, Berry moved to what is now the Cheriton School of Computer Science at the University of Waterloo. Berry's current research interests are software engineering in general, and requirements engineering and electronic publishing in the specific.

This talk should (hopefully) be of interest to people working in distributed systems, distributed CSPs, and multi-agent systems. Loosely coupled multi-agent systems are perceived as easier to plan for because they require less coordination between agent sub-plans. In this paper we set out to formalize this intuition. We establish an upper bound on the complexity of multi-agent planning problems that depends exponentially on two parameters quantifying the level of agents' coupling, and on these parameters only. The first parameter is problem-independent, and it measures the inherent level of coupling within the system. The second is problem-specific and it has to do with the minmax number of action-commitments PER AGENT required to solve the problem. Most importantly, the direct dependence on the number of agents, on the overall size of the problem, and on the length of the agents' plans, is only polynomial.

This result is obtained using a new algorithmic methodology which we call ``planning as CSP+planning''. We believe this to be one of the first formal results to both quantify the notion of agents' coupling and to demonstrate a tractable planning algorithm for fixed coupling levels. Joint work with Carmel Domshlak from the Technion.