Title: Multi-restricted and multi-restrained Sterling Numbers

Title: Streaming Graph Computations with a Helpful Adviso

Given a positive integer m and nonnegative integers n and k, the (n,k)-th m-restricted Sterling number of the second kind is the number of partitions of an n-set with k nonempty subsets of size less than or equal to m, and the (n,k)-th m-restrained Sterling number of the first kind is the number of permutations of an n-set with k disjoint cycles of length less than or equal to m. In this talk, their explicit formulae, recurrence relations, generating functions will be presented.

Bio: Ji Young was born in Busan, Korea, and came to the states for graduate school where she earned my Ph.D. in Mathematics at Iowa State University in 2002 with the thesis: Multi-restricted numbers and powers of permutation representations, supervised by Dr. Jonathan D. H. Smith. Ji Young is an associate professor in the Department of Mathematics at Shippensburg University of Pennsylvania and currently I am on sabbatical as a DIMACS visiting researcher. Her research interests include topics in Algebra and Combinatorics.

Title: Streaming Graph Computations with a Helpful Advisor

There has been much work on algorithms for graphs presented as a stream of edges, but many problems are "hard" in this model, in that they require space linear in the number of nodes or edges. Motivated by the trend to outsource work to commercial cloud computing services, we consider a variation of the streaming paradigm where a small space streaming algorithm can be assisted by a powerful helper that can provide annotations to the data stream. We extend previous work on such annotation models by considering a number of graph stream problems. Without annotations, streaming algorithms for graph problems generally require significant memory; we show that for many standard problems, including all graph problems that can be expressed with totally unimodular integer programming formulations, only a constant number of hash values are needed for single-pass algorithms given linear-sized annotations.

Title: A Completeness Theorem for Pseudo-Linear Functions with Applications to UC Security

We consider multivariate pseudo-linear functions over finite fields of characteristic two. A pseudo-linear polynomial is a sum of guarded linear-terms, where a guarded linear-term is a product of one or more linear-guards and a single linear term, and each linear-guard is again a linear term but raised to the power q-1, where q is the field size. Pseudo-linear functions over GF(2^m) are given by pseudo-linear polynomials defined over GF2.

Let f1, f2,...,fk be k pseudo-linear functions in n variables, and let f be another pseudo-linear function in the n variables. We show that if f is a function of the given k functions, then it must be a pseudo-linear function of the given k functions. This generalizes the straightforward claim for just linear functions. We also prove a more general theorem where the k functions can in addition take further arguments, and prove that if f can be represented as a iterated composition of these k functions, then it can be represented as a pseudo-linear iterated composition of these functions. Further generalizations to stateful and randomized functionalities are considered.

These theorems have implications for automatic proving of universally-composable security theorems for ideal and real functionalities composed of if-then-else programs and m-bit exclusive-or. It follows that deciding if a simulator exists is in computational time independent of m. (This is joint work with Arnab Roy, IBM T. J. Watson)

Bio: Charanjit Jutla received his PhD in Computer Science from the University of Texas at Austin in 1990. Since then he has been a Research Staff Member at the IBM T. J. Watson Research Center. His research focuses in the fields of Cryptography, Coding Theory and Complexity Theory. Among his various contributions to Cryptography, he invented the first single-pass Authenticated Encryption Scheme. He is also one of the main designers of the block cipher MARS, and the hash function Fugue. He has been on the program committee of various international cryptography conferences.

Title: Personal Social Graph as an Anonymous Vehicle for P2P Applications: The Cost of Renting Trusted Connections

We introduce a trusted self-organized network infrastructure for running anonymous peer-to-peer applications, which leverages real-life social links and the basic need for privacy that each individual converts into a carefully built structure dubbed Personal Social Graph (PSG). The PSG is a list owned by each person (a node in the infrastructure graph), with entries that represent strict trust relationships with other individuals. The real-life small-world connections result in large network of interconnected PSGs, which we call the Personal Social Graph Network. We introduce a cost per social network edge, incurred whenever the application rents the trusted edge for data exchange. For dissemination strategies designed to evenly cache the data across peer nodes, we study the cost of usage to an application as a function of the application's popularity and activity. By using a subgraph that encompasses the application nodes, and the nodes directly attached to them, we lower the price of renting.

Bio: Silvija Kokalj-Filipovic received the Diploma of Engineering degree in 1989 and M.S. degree in 1995, both from the School of Electrical Engineering, University of Belgrade, Yugoslavia. She received her Ph.D. degree in electrical and computer engineering from Rutgers University in November 2008. From 1989 to 2002 she worked as a developer of cutting-edge communication and networking products. Before joining INRIA, Saclay, France as a Postdoctoral Fellow in Fall 2009, Silvija was a Visiting Researcher at Princeton University. This presentation is a result of her research in INRIA, which focused on modeling those structural properties of social networks that can be leveraged by P2P networks, and vice versa. She is currently ASEE/NSF Corporate Postdoc fellow in Alcael-Lucent, Murray Hill. Her research interests include wired and wireless networks, coding techniques and stochastic modeling in communication networks.

Title: Analysis of Computer Experiments with Functional Response

Computer experiments refer to those experiments that are performed in computers using physical models and ?nite element analysis. Most existing methods for analyzing computer experiments with single outputs such as kriging cannot be easily extended to functional outputs due to the computational problems caused by high-dimensionality of the response. In this talk, we develop an efficient implementation of kriging for analyzing functional responses. The methodology is illustrated using computer experiments conducted for machining process optimization and data center thermal management.

Title: Indoor Mapping Robot for Urban Structure Mapping

This talk will discuss the development of an Indoor Mapping robot that will be used for generating 3-D datasets of indoor urban terrain using sensors and with selectable levels of detail. There are several industries exploring solutions to quickly and accurately digitize unexplored urban environments, into useable three-dimensional databases. Unfortunately, there are inherent challenges to the indoor mapping process such as, scanning limitations and environment complexity, which require a specific application of tools to map an environment precisely with low cost and high speed. Our work successfully demonstrated the capability to develop real-time 3D maps of indoor locations with multiple application areas including search and rescue, indoor navigation and site security.

Bio: Dr. Palaniappan is a Post-doc fellow from NSF/ASEE and currently a member of Statistics and Learning Department at Bell labs, Murray Hill, NJ. His areas of research include location & tracking systems, robotics, wireless sensor networks and High Performance Computing.

Title: A Survey of Approaches to Improving Network Switching & Routing Configuration

Several studies of Internet router configurations and messages sent by routers to coordinate how traffic is directed have shown that a nontrivial portion of the routes computed are unstable or probably incorrect. Three of the major contributing factors are human error, the lack of visibility that routers have when making their independent, distributed decisions, and that the many routing devices that compose a network are often configured individually using vendor-specific, simple imperative languages. Ideas under development in the networking community will hopefully change this, allowing network operators to configure networks at a higher level of abstraction, but these ideas raise interesting questions that must be addressed using expertise in programming languages, algorithms analysis, and network measurement and performance. In this talk, I will introduce a framework that permits this type of higher-level network configuration and discuss several projects that I'm working on that address some of these interesting questions, including the appropriate algorithms to use for network autoconfiguration and the behavior of networks and their control algorithms under a high degree of churn.

Bio: Vijay Ramachandran is an assistant professor of computer science at Colgate University, and is a DIMACS visitor for summer and fall 2010, and co-mentored several students in the DIMACS REU program. He holds an A.B. in mathematics from Princeton and a Ph.D. in computer science from Yale. Before working at Colgate, he was a postdoc at ICSI in Berkeley, CA, and at DIMACS/the Stevens Institute of Technology in Hoboken, NJ. He has previously been a DIMACS visitor during summer 2008. His research interests include algorithmic foundations of the Internet, specifically, design, analysis, and configuration of Internet routing protocols.