DIMACS third event in its Mixer Series
Bellcore, Monday, February 10, 1:30 pm - 4:20 pm
INVITATION
DIMACS invites you to the third event in its Mixer Series. All DIMACS
members, visitors, postdocs, and students are invited to join us on
Monday afternoon, February 10 at Bellcore. The purpose of this mixer
is to introduce the postdocs and DIMACS visitors to each other and to
DIMACS members from the different DIMACS institutions.
The mixer will feature talks by DIMACS member Jozsef Beck and four of
our postdocs: Dominic Mayers, David Wilson, Shiyu Zhou and Owen Kelly.
A schedule of the talks is attached. More details will soon be
available on the DIMACS web pages (http://www.dimacs.rutgers.edu).
Those wishing to attend the mixer should send mail (preferably by
February 7) to Dan Boneh (dabo@bellcore.com), so that badges can be
prepared. Directions to Bellcore are available from the DIMACS
homepage (http://dimacs.rutgers.edu/archive/Directions/Directions4). For
further information about the mixer, contact Mona Singh
(mona@cs.princeton.edu).
Fred Roberts,
Director
Bellcore Mixer: Monday Feb 10 at 1:30 pm
1:30 - 1:35 Fred Roberts
DIMACS Director, Rutgers University
Opening Remarks
1:35 - 2:25 Jozsef Beck
Rutgers University
"Randomness in lattice point problems and arithmetic"
2:25 - 2:50 Dominic Mayers
Princeton University
"Unconditional security in quantum cryptography"
2:50 - 3:15 David Wilson
Berkeley and Rutgers University
"Determinant algorithms for random planar structures"
3:15 - 3:30 Coffee Break
3:30 - 3:55 Shiyu Zhou
Bell Laboratories
"Computing undirected st-connectivity in small space"
3:55 - 4:20 Owen Kelly
Rutgers University
"A context tree channel equalizer"
ABSTRACTS
Title:
Randomness in lattice point problems and arithmetic
Speaker:
Jozsef Beck, Rutgers University
Abstract:
We study the fluctuations of the numbers of lattice points in
translated copies of tilted hyperbola-segments and tilted rectangles,
and prove Central limit theorems for quadratic irrational angles.
This is a very exciting new subject on the border line of probability
theory, number theory and geometry.
We point out some unexpected connections with class number formulas
of quadratic number fields and continued fractions.
We explain why $\sum_{n=1}^N (\{ n\sqrt{2}\} -1/2)$ is a random series
(here $\{ ...\}$ stands, as usual, for the fractional part).
Title:
Unconditional security in quantum cryptography
Speaker:
Dominic Mayers, Princeton University
Abstract:
Assume that you are 30 km away from your friend and want to exchange
secret messages with him. You are connected to your friend by an
underground optical fiber and a public channel. An eavesdropper can
intercept any signal transmitted on the optical fiber. S/he listens
to the messages sent to the public channel. S/he has unlimited time,
space and technology. Your only advantage is that the public channel
cannot be secretely tampered by a third party. You want the
transmission of your secret messages to tolerate a reasonable amount
of noise. Also, you would like to know whether or not a transmission
has been sucessful, so that you can try again in case of failure. The
most important point is that in all cases you want the message to
remain secret. In this situation, can you simulate this kind of
private channel between you and your friend?
In accordance with the classical information theory, this task cannot
be realized unless we accept unproven assumptions. However, even with
the current technology, quantum cryptography allows you to accomplish
such a task. Charles Bennett (IBM) and Gilles Brassard (Universite de
Montreal) had the original idea which shows that quantum physics is
superior to classical physics in manipulating information.
I will explain why the original idea of Bennett and Brassard is
unbreakable. I will also consider other cryptographic tasks. Assume
that two milionnaires want to know who is richer, but neither wants
to reveal how much money he has. Can they accomplish this task with
no use of unproven assumptions? This is still an open question, but
we will see that other important tasks in cryptography have been shown
to be impossible in accordance with the laws of nature.
To summarize, we will discuss what quantum cryptograhy can do and what
it cannot do to fulfill our cryptographic needs.
Title:
Determinant algorithms for random planar structures
Speaker:
David Wilson, Rutgers University
Abstract:
Colbourn, Myrvold, and Neufeld developed a fast algorithm for
generating random arborescences of a graph, using the fact that the
determinant of a certain matrix enumerates these arborescenes. There
are a variety of other combinatorial structures that can be enumerated
by evaluating a determinant, structures of interest in both the
physics and mathematical communities. Randomly generating such
objects has been a useful tool in studying their properties, and has
guided mathematicians by suggesting theorems that might be true. We
show here how to adapt and extend the techniques used by Colbourn et
al. to efficiently randomly generate such objects. These new
algorithms offer significant improvements over previous algorithms in
both their generality and their speed.
Title:
Computing undirected st-connectivity in small space
Speaker:
Shiyu Zhou, Bell Laboratories
Abstract:
The undirected st-connectivity problem is: given as input an undirected
graph and two vertices s and t, determine whether there is a path
>from s to t. A major open question in complexity is whether this
problem can be solved in space logarithmic in n, the number of vertices.
We give a review of the history of the problem and the approaches people
have developed to computing undirected st-connectivity in small space.
Title:
A context tree channel equalizer
Speaker:
Owen Kelly, Rutgers University
Abstract:
New results from Information Theory on the limits of data
compression (redundancy) are also relevant for probabilistic modeling
of finite alphabet sequences. Through Kraft's inequality, estimated
probability is the dual of compressed sequence length. Context-tree
algorithms provide near optimal probability estimates in the sense of
minimal redundancy. We have used context-tree based probability
estimates to build a receiver that is highly immune to unknown channel
distortions. Through a training sequence, the receiver learns the
unknown probability law of the channel in the same manner that a file
compressor learns the patterns of a source file. Historically,
receivers that compensate for dependence in observations are called
channel equalizers.
Document last modified on February 3, 1997