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.
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.
Document last modified on September 13, 1999.