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.