Title: Locally & Universally Finding Significant Fourier Coefficients

Computing the Fourier transform is a basic building block used in numerous applications. For data intensive applications, even the O(N\log 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 fraction (say, 1%) of 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: 1. Local. The running time and number of function entries read by the algorithm is polynomial in \log|G|, 1/\tau and L_1(f) (for L_1(f) denoting the sum of absolute values of the Fourier coefficients of f). 2. Universal. The 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. 3. 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 adversarial noise in running time sub-linear in the domain size.

Our algorithm improves on the prior universal 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 proving cryptographic bit security results, and to efficiently decoding polynomial rate variants of Homomorphism codes, MPC codes and other exponential rate codes.

Title: Graph homomorphism and gradually varied functions

Graph homomorphism maps adjacent vertices to adjacent vertices between two graphs. The gradually varied function in a discrete space preserves that the value change of neighborhood is limited respect to the center point. This talk will discuss how theses two topics are highly related. We will first introduce absolute retracts in graph homomorphism and P. Hell and Rival^s theorem for reflexive graphs (1987). Then we discuss why gradually varied functions are important to digital spaces, and the necessary and sufficient condition of the existence of gradually varied extension. At the last, we discuss the generalization of related concepts to discrete surface immersion and graph homomorphic extension (Agnarsson and Chen, 2006).

Main Theorem: For a reflexive graph G the following are equivalent:

1. G has the Extension Property
2. G is an absolute retract.
3. G has the Helly property.

The alternate representation of the theorem:

For a discrete manifold M the following are equivalent:

1. Any discrete manifold can normally immerse to M 
2. Reflexivized M is an absolute retract.
3. M has the Helly property.

1. L. Chen, The necessary and sufficient condition and the efficient
algorithms for gradually varied fill, Chinese Sci. Bull. 35 (10) (1990) 870^873.
2. L. Chen, Random gradually varied surface fitting, Chinese Sci.
Bull. 37 (16) (1992) 1325^1329.
3. L. Chen, Discrete surfaces and manifolds, Scientific and Practical
Computing, Rockville, Maryland, 2004
4. P. Hell, I. Rival, Absolute retracts and varieties of reflexive
graphs, Canad. J. Math. 39 (3) (1987) 544^567.
5. P. Hell, J. Ne^etril, Graphs and homomorphisms, Oxford Lecture
Series in Mathematics and its Applications, vol. 28, Oxford University Press, Oxford, 2004.
6. G. Agnarsson and L. Chen, On the extension of vertex maps to graph
homomorphisms, Discrete Mathematics, Vol 306, No 17,  pp 2021-2030,  Sept.
2006.

Title: Improved Piecewise-Linear Approximations for Minimizing Separable Concave Cost Functions Over Polyhedra

Minimizing a separable concave cost function over a polyhedral feasible set arises often in fields such as transportation, logistics, and supply chain management. In this context, we are interested in approximating the concave cost functions with piecewise-linear functions, in order to then employ discrete optimization methods to obtain theoretical results and computational approaches. Recently, we have shown how to perform a 1+epsilon approximation with a number of pieces that is polynomial in the input size of the concave cost problem and linear in 1/epsilon. We have also shown a lower bound on the number of needed pieces as a function of the input size and 1/epsilon. In this talk, we will discuss an improved upper bound on the number of pieces. We will relate this theoretical bound to our experience with approximating concave functions in computations.

Title: Tracking Malicious Regions of the IP Address Space Dynamically.

Current measurements across the Internet indicate that many kinds of malicious traffic (e.g., spam, scans, botnets) are correlated with relatively small regions of the IP address space. We design online algorithms that, with low space requirements, can dynamically track IP prefixes that originate malicious traffic. Our algorithms provide a near-optimal prediction of IP addresses that send malicious and normal traffic, over adversarially generated data. Our experiments on real mail traces demonstrate that our algorithms' predictions are orders of magnitude more accurate than pre-existing fixed clusterings.

Title: Privacy in a Networked World

Networked electronic devices have permeated business, government, recreation, and almost all aspects of daily life. Coupled with the decreased cost of data storage and processing, this has led to a proliferation of data about people, organizations, and their activities. This cheap and easy access to information has enabled a wide variety of services, efficient business, and convenience enjoyed by many. However, it has also resulted in privacy concerns.

Privacy-preserving data mining seeks to balance the ability to perform useful computations on data held by many parties with the desire to protect the privacy of sensitive information. Distributed cryptographic data mining protocols allow two or more data holders to interact with each other in order to apply particular data mining algorithms to their joint data wthout revealing anything else about their data to each other or anyone else. In this talk, I will give an overview of the general privacy landscape and describe some of our work on privacy-preserving data mining.

(This includes joint work with Geetha Jagannathan and Jun Sakuma.)