^January February – 2013 ^March

This talk focuses on the classic problem of Matrix Rigidity, introduced by Valiant '77, motivated by algebraic circuit lower bounds. We suggest a new route for resolving the problem by reducing it to the problem of efficiently constructing a hitting set for a class of polynomials, which we call U-polynomials. To showcase the reduction, we deduce that (large..) small-bias sets induce rigid matrices. We also show how to construct (large..) rigid sets from unbalanced expanders. Joint work with Noga Alon. No prior knowledge is assumed.

Real-time compression and deduplication for primary storage is quickly becoming widespread as data continues to grow exponentially, but adding compression and deduplication on the data path consumes scarce CPU and memory resources on the storage system. In this talk we present different approaches to efficient estimation of the potential data reduction ratio of data and how these methods can be applied in advanced storage systems. The main focus is on compression ratio evaluation where we employ two filters: The first level of filtering that we employ is at the data set level( e.g., volume or file system), where we estimate the overall compressibility of the data at rest. According to the outcome, we may choose to enable or disable compression for the entire data set, or to employ a second level of finer-grained filtering. The second filtering scheme examines data being written to the storage system in an online manner and determines its compressibility. We also discuss the challenges in achieving similar results when deduplication is involved and suggest alternatives for this scenario.

Histogram distance functions are the cornerstone of numerous computer vision and machine learning tasks (e.g. image retrieval, descriptor matching and k-nearest neighbor classification). It is common practice to use distances such as the Euclidean and Manhattan norms to compare histograms. This practice assumes that the histogram domains are aligned. However, this assumption is violated through quantization, shape deformation, light changes, etc. The Earth Mover’s Distance (EMD) is a cross-bin distance that addresses this alignment problem. We present several new Earth Mover's Distance variants that are robust to outlier noise and global deformations. Additionally, we present efficient algorithms for their computation. We show state-of-the-art results for descriptor matching and image retrieval. These tools have already been used by other groups and demonstrated state-of-the-art results for a range of tasks such as superpixel matching, descriptor matching, image retargeting, image segmentation, social graph comparisons and population density comparison. Finally, we describe several future directions including learning with general (not necessarily positive-semidefinite) similarity functions.

We describe a framework for specifying and analyzing complex system models composed of heterogeneous components using an SMT (Satisfiability Modulo Theories) based approach. We apply this method to the emerging fields of Synthetic biology and DNA Computing, and more broadly to study Biological Computation. This work highlights biological engineering as a domain that can benefit extensively from the application of software engineering and formal methods, while some of the methods and challenges addressed have the potential to influence development of novel tools for system and software engineering.