Talk 9
| Title: | Gröbner Fans and Tropical Algebraic Geometry |
| Speaker: | Anders Nedergaard Jensen |
| When: | Friday, November 25, 09:15-11:00 |
| Where: | Aud. E, Department of Mathematical Sciences |
| Abstract |
|
In tropical mathematics the tropical semi-ring (ℝ, max, +) is
considered. By letting maximum take the role of addition and addition
the role of multiplication a tropical polynomial becomes a piecewise
linear function. Many classical definitions and theorems have a
translation in tropical mathematics. For example Bezout's theorem and
a certain version of Pappus' theorem exist. It makes sense to define
the tropical variety of a polynomial ideal. The tropical variety turns
out to be a union of a finite set of polyhedral cones and it may be
considered as a polyhedral subcomplex of the Gröbner fan of the
ideal.
Besides giving an introduction to tropical algebraic geometry we will
discuss new algorithms for computing Gröbner fans and tropical
varieties of prime ideals. Our methods rely on polyhedral and
Gröbner basis techniques and on a connectivity result.
Joint work with T. Bogart, K. Fukuda, D. Speyer, B. Sturmfels, and
R. Thomas.
|
Talk 8
| Title: | Combinatorial Analysis of Quantum Random Walks |
| Speaker: | Eric Bach, Computer Sciences and Mathematics Departments, University of Wisconsin |
| When: | Friday, October 28, 09:15-11:00 |
| Where: | Lille Aud Benjamin-117, Department of Computer Science |
| Abstract |
|
Random walks have many applications in the analysis of algorithms and
elsewhere. These processes have quantum analogs, which are extremely
interesting in their own right and may play a role in future
applications of quantum computing. The behavior of these processes is
strikingly different from their classical cousins. For example, a
gambler who bets on the flip of a fair coin against an infinitely rich
adversary is sure to be ruined, but in the quantum casino, play can be
eternal. In this talk I will survey the results we have obtained on
quantum walks and discuss some intriguing new connections between
finite barrier walks and arithmetic sequences.
Joint work with Andris Ambianis, Lev Borisov, Susan Coppersmith,
Marcel Goldschen, Robert Joynt, Ashvin Nayak, Ashwin Vishwanath, and
John Watrous.
|
Talk 7
| Title: | Binary GCD like Algorithms for quadratic number rings. |
| Speaker: | Saurabh Agarwal |
| When: | Thursday, June 9, 10.15-12.00 |
| Where: | Turing-016, Department of Computer Science |
| Abstract |
|
Greatest common divisor is one of the most important concepts of
number theory. The Euclidean algorithm is a well known algorithm to
compute the GCD of two integers. However it is not the best! The
binary GCD algorithm was invented by Josef Stein in mid 60's to
compute the GCD of ordinary integers. Not only is the algorithm simple
to understand, it is efficiently implementable on computers. In this
talk I will present a brief history of the problem and walk you
through different techniques used to extend this algorithm to
different quadratic rings. Finally I will talk about different issues
involved in extending it to other number rings.
|
Talk 6
| Title: | Uniform Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two |
| Speaker: | Alex Healy, Division of Engineering and Applied Sciences, Harvard University
|
| When: | Wednesday, May 25, 15.15-17.00 |
| Where: | Ada-018, Department of Computer Science |
| Abstract |
|
The complexity of arithmetic (over the integers or in finite fields)
is a fundamental topic in computer science. This has been studied in
a variety of computational models, and in this talk we focus on the
constant-depth circuits model. While seemingly restricted,
constant-depth circuits can actually be surprisingly poweful -- for
instance, a breakthrough result of Hesse et al (JCSS 2002) shows that
integer division can be computed by constant depth circuits with
majority gates (i.e., TC0). On the other hand,
constant-depth circuits are the strongest model of computation for
which explicit lower-bounds are known.
In this work, we study arithmetic operations in finite fields of
characteristic two, and ask to what extent they can be computed by
constant-depth circuits. For example, we consider the problem of
exponentiation in the finite field F2n: it is
well-known that one can use the repeated-squaring algorithm to compute
ai in polynomial time, given a in F2n and an
n-bit integer i. We show how constant-depth circuits can compute
exponentiation over a certain family of finite fields. To the best of
our knowledge, this is the first result placing exponentiation in a
complexity class below polynomial-time. We also study the complexity
of iterated multiplication, irreducibility-testing and related
problems.
As one application of our results, we prove that constant-depth circuits
with majority gates (TC0) are equivalent to the class AE of functions
computable by certain natural arithmetic expressions. This answers a
question raised by Frandsen, Valence and Barrington (Mathematical Systems
Theory '94).
Joint work with Emanuele Viola.
|
Talk 5
| Title: | Pearls of Algebra in Computational Complexity II: The Razborov-Smolensky Lower Bound |
| Speaker: | Kristoffer Arnsfelt Hansen |
| When: | Thursday, May 12, 10.15-12.00 |
| Where: | Ada-018, Department of Computer Science |
| Abstract |
|
Boolean circuits provide a purely combinatorial formalization of
Boolean computation, as opposed to the more operational formalization
by Turing Machines. As a consequence we can directly recast questions about
computation into combinatorial questions. Most advances on
these questions have been obtained using algebra, in particular
polynomials over various algebraic structures. After an introduction
to Boolean circuits I will present one of the most successful
applications of polynomials to circuits, the Razborov-Smolensky lower
bound. Finally I will discuss obstacles in generalizing this lower bound.
|
Talk 4
| Title: | A variant of the probable prime test by Miller and Rabin |
| Speaker: | Gebhard Böckle (Essen) |
| When: | Thursday, April 28, 16.15 |
| Where: | Aud. G1, Department of Mathematical Sciences |
| Abstract |
|
An important issue in modern cryptology is the generation of large
prime numbers. Such are needed in most asymetric cryptosystems that
are currently used, for instance for the RSA system. Perhaps the
most-used method to generate such primes on smart cards is based on
the probable prime test by Miller and Rabin (MR). The actual
generation works as follows: First one generates a random integer n
that is relatively prime to the first k prime numbers. A typical bit
length of n is 1024, a typical value for k is 54. The number n is
generated using a physical system. Once it is generated, its primality
is probed by having it run through a certain number of rounds of the
Miller-Rabin test. The number n is declared a prime if it passes a
certain number of rounds successfully. For safety reasons one
generates the needed prime numbers on the smart card, since they
should not be known outside the card. Therefore one is worried about
possible side channel attacks that might reveal the primes when
generated. One of the most critical parts of the MR test is that in
each round one uses binary exponentiation (basically each time) with
the number n-1. If no protection is provided, by measuring currents
one can easily read of the digits of n-1, and hence n. In the talk I
will first recall the Miller-Rabin test, explain the usual qualitative
analysis of its confidentiality and some results of Damgard Landrock
and Pomerance that gouvern its reliability in prime generation. Then I
will discuss a method of randomizing and hence of hiding the exponent
of the MR test. This serves as one possible countermeasure against
side channel attacks. The drawback is that the `randomized MR-test'
has a lower confidentiality than the original test. In the second half
of the talk, I will therefore discuss this issue, and provide bounds
that allow for practical implementation.
|
Talk 3
| Title: | Dependent rational points on curves over finite fields - Lefschetz theorems and exponential sums |
| Speaker: | Johan P. Hansen |
| When: | Thursday, April 14, 10.15-12.00 |
| Where: | Aud. G2, Department of Mathematical Sciences |
| Abstract |
|
For an algebraic curve defined over the finite field Fq
with q elements, we study the probability that d randomly chosen
Fq -rational points on the curve impose dependent
conditions on the functions in a given d-dimensional vector space of
rational functions on the curve. This probability tends to be close to
1/q . The results have applications in the assessment of the
performance of decoding algorithms for algebraic geometry codes. The
proofs involve a geometric construction, Lefschetz theorem for
quasi-projective varieties and majorizations of exponential sums.
|
Talk 2
| Title: | Pearls of Algebra in Computational Complexity I: The PCP theorem |
| Speaker: | Peter Bro Miltersen |
| When: | Thursday, March 31, 10.15-12.00 |
| Where: | Ada-018, Department of Computer Science |
| Abstract |
|
The goal of computational complexity theory is to obtain an
understanding of resource bounded Boolean computation,
i.e., computation with bits and bytes, as formalized, for instance
by the Turing machine model, leading to questions such as P
vs. NP. Thus,
the topic seems to be of a purely combinatorial nature and it
is not at all clear a priori that algebraic methods
would be particularly useful for obtaining such an understanding.
Nevertheless, it seems that nearly all important advances in
computational complexity theory in the last two decades have been
by proofs with some concrete algebraic core. In particular,
polynomials over the integers and over finite rings and fields have been
ubiquitous. I plan to present a series of such "pearls of applications
of polynomials in computational complexity", beginning in this lecture
with the PCP theorem.
|
Talk 1
| Title: | The generic Gröbner walk |
| Speaker: | Niels Lauritzen |
| When: | Friday, March 18, 10.15-12.00 |
| Where: | Aud. G2, Department of Mathematical Sciences |
| Abstract |
|
In this talk we will begin by giving a brief introduction to the interface
between Gröbner bases and convex geometry. Then we will outline
a new algorithm for computing Gröbner bases
inspired by formal perturbation techniques in
optimization and computational geometry. The algorithm is an
extension of the Gröbner walk, which may be viewed as a
simplex algorithm on a well defined polytope in algebra.
|
|
|
