1. Optimal Proof Systems and Sparse Sets Lance Fortnow NEC Research Computer scientists study lower bounds in proof complexity with the ultimate hope of actual complexity class separation. Cook and Reckhow formalize this approach. They create a general notion of a proof system and show that polynomial-size proof systems exist if and only if NP = coNP. Cook and Reckhow also ask about the possibility of whether optimal proof systems exist. Informally an optimal proof system would have proofs which are no more than polynomially longer than any other proof system. An optimal proof system would play a role similar to NP-complete sets. There exists a polynomial-time algorithm for Satisfiability if and only if P = NP. Likewise, if we have an optimal proof system, then this system would have polynomial-size proofs if and only if NP = coNP. The existence of optimal proof systems remains an interesting open question. Krajicek and Pudlak and Messner and Toran show that optimal proof systems do occur under some (unlikely) assumptions. Messner and Toran show that the existence of optimal proof systems implies that there is a complete set for the class of sparse NP sets. This means there would be a single "small" NP set that is hard for every other "small" set. However they could not argue that these complete sets could not exist. We show that proving the existence of optimal proof systems will require new techniques by creating a relativized world where there do not exist complete sets for the class of sparse NP sets. We also prove other results along these lines as well as tying together the question of complete sparse NP sets and reductions from sparse sets to tally (unary) sets. This talk will survey the area as well as describing recent joint research with Harry Buhrman, Steve Fenner, Dieter van Melkebeek and the speaker. The research was done while the speaker was at the University of Chicago. 2. Foveation Techniques and Scheduling Issues in Visualization of Large Images Ee-Chien Chang DIMACS, Rutgers University We are interested in the visualization of large images over a network. Under the thinwire scheme, the viewer can interactively indicate the area of interests, and this area will has a higher priority in the transmission process. As a result, the displayed image is a "space-variant" image. A fundamental difference between this scheme and the usual progressive transmission scheme is that we place more emphasis on the visualization process. This shift in emphasis open up new perspectives on the problem. In this talk, I will briefly describe two theoretical issues. The first issue arises from the representation of "space-variant" (or foveated) images. The notion of foveated images has been applied in many computer vision and visualization systems. We treat the process of obtaining foveated images as an integral operator and study this operator using wavelet. These studies lead to an efficient algorithm for foveated images. The second issue arises from the underlying on-line nature in the thinwire scheme. I will describe an abstract on-line scheduling problem and give a few algorithms and their competitive ratio. 3. Structural Results for Planar sets with many similar subset Bernardo Abrego Dept. of Mathematics, Rutgers University Consider a finite subset $P$ of the plane. Earlier results from Elekes and Erd\H{o}s, and by Laczkovich and Ruzsa indicate that the maximum number of sets similar to $P$ that can be found among $n$ points in the plane is $\Theta (n^{2})$ if and only if the cross ratio of any quadruplet of points in $P$ is algebraic. As the main result in this talk we prove that if an $n$-element set $A$ contains $cn^{2}$ subsets similar to $P$ then $A$ must contain large lattice-like structures. In particular we prove that for $n$ sufficiently large, $A$ must contain $k$ points in a line forming an arithmetic progression. Moreover, when $P$ is not a cocyclic set, we can guarantee arbitrarily large $k\times k$ lattices in $A$. On the other hand we show that for cocyclic sets $P$, there are $n$-element sets $A$ with $\Theta (n^{2})$ copies of $P$ and without $3\times 3$ lattice subsets. This is joint work together with Silvia Fern\'{a}ndez-Merchant and Gy\"{o}rgy Elekes. 4. Christophe Long Dept of Mathematics, Rutgers University In 1979 Peter Frankl made the following conjecture: if ${\mathcal F}$ is a finite family of finite sets, not all empty, that is closed under unions, then some element is contained in at least half of the sets in ${\mathcal F}$. We prove that the conjecture is true if the largest set in ${\mathcal F}$ has size 8, as well as comments on how to extend this result to largest set having size 9. 5. Good Characterization for Coloring Problems Jaroslav Nesetril DIMATIA We approach coloring problems as the existence of homomorphism (H-coloring problems). Finitary and good charaterization were recently characterized C.Tardif and author. We present this and survey related research. 6. Global Internet Simulation Myongsu Choe DIMACS, Rutgers University Internet is one of the most dynamic and fast growing networks. A simulation framework to investigate the inherent behaviors of the Internet is also required to be scalable to keep track of the increasing network size. For the simulation scalability, we discuss the application of parallel simulation techniques on this particular simulation application and give some interesting issues such as load balancing and partitioning. 7. Self-configuring Systems Sivaram Rajagopalan Telcordia Technologies As computer systems get bigger and more interconnected, managing change is becoming much harder. The space of available configurations and their interdependencies has exploded beyond the reach of human operators and change is occurring today in faster and more pervasive ways than current management tools can track. We need to build self-configuring software at all levels from within a single workstation to global-span distributed systems that will allow software to manage change automatically, removing the need for human intervention as much as possible.Document last modified on September 13, 1999.As an initial step towards building self-configuring systems, we have focused on the problem of managing security policy in networks of firewalls. Current methods rely on low-level scripts that are highly customized and hard to verify. What is needed is a tool that will automatically reconfigure the system in response to any change so that the desired security policy is maintained. Building on the NESTOR platform for network management developed at Columbia University, we are developing a security policy management system for enterprise-level networks that automatically reconfigures network elements such as firewalls, switches, servers etc. so that the desired service availability can be maintained transparently through network change without violating security policy.
This is joint work with Sandeep Bhatt, Ernie Cohen and Sanjai Narain at Telcordia Technologies and Alexander Konstantinou and Yechiam Yemini at Columbia University.