Lattice Algorithms: State of the Art and Open Problems

Speaker: 

Daniele Micciancio

Institution: 

UCSD

Time: 

Wednesday, March 14, 2012 - 2:00am

Host: 

Location: 

RH 306

TITLE: Lattice Algorithms: State of the Art and Open Problems
SPEAKER: Daniele Micciancio (UCSD)

ABSTRACT
Computational problems on point lattices play an important role in
many areas of computer science and mathematics. Since the discovery of
the LLL basis reduction algorithm in the early '80s, much effort has
gone into the development of better (faster, or more accurate)
algorithms, largely motivated by applications in cryptanalysis. Today,
with the flourishing of lattice based cryptography (i.e.,
cryptographic function whose security rests on the computational
intractability of lattice problems, including the recent development
of fully homomorphic encryption schemes), improving our understanding
of the effort required to solve lattice problems has never been more
important, as it plays a critical role determining appropriate key
sizes. In this talk I will describe the current state of the art in
lattice algorithms, including the asymptotically fastest known
algorithm of Micciancio and Voulgaris, as well as less understood but
practically effective heuristics, and a panoramic of the many research
problems that are still open in the area.

Bio sketch: Daniele Micciancio got his PhD from MIT in 1998, and
joined the UCSD CSE faculty in 1999. He is the recipient of several
awards, including an NSF CAREER award, Sloan Fellowship and Hellman
Fellowship. He is most known for his research on the complexity of
lattice problems, which spans the whole spectrum from computational
complexity and algorithms, to cryptography. His most notable
achievements include the first significant inapproximability result
for the Shortest Vector Problem, pioneering the use of cyclic and
ideal lattices from algebraic number theory for the construction of
very efficient cryptographic primitives based on worst-case complexity
assumptions, and the discovery of the first single exponential time
algorithm to solve all the most important computational problems on
point lattices.

Mathematical Models for Phototaxis

Speaker: 

Doron Levy

Institution: 

University of Maryland

Time: 

Tuesday, May 29, 2012 - 3:00pm to 4:00pm

Host: 

Location: 

RH 440R

Certain organisms undergo phototaxis, that is they migrate toward light. In this talk we will discuss our recent results on modeling phototaxis in order to understand the functionality of the cell and how the motion of individual cells is translated into emerging patterns on macroscopic scales. This is a joint work with Amanda Galante, Susanne Wisen, Tiago Requeijo, and Devaki Bhaya.

MATLAB seminar on "Computer Vision with MATLAB"

Speaker: 

Allyson Butler and Grant Martin

Institution: 

MathWorks

Time: 

Wednesday, March 28, 2012 - 10:00am to 12:00pm

Host: 

Location: 

RH 306

The topics covered will include:

  • Working with files & live sources
  • Pre-processing
  • Blob/point detection, feature extraction, and matching techniques
  • Video Motion analysis with Optical flow, and block matching
  • Video stabilization and stereo image rectification
  • Classification algorithms to recognize image content
  • Video display and graphic overlay
  • Multi-core PC and NVidia GPU simulation and acceleration
  • Integration with OpenCV

Image Deblurring Via Self-Similarity and Via Sparsity

Speaker: 

Yifei Lou

Institution: 

UCSD and UCLA

Time: 

Thursday, March 8, 2012 - 11:00am to 12:00pm

Location: 

RH 306

In this talk, I will present two deblurring methods, one exploits the spatial interactions in images, i.e. the self-similarity; and the other explicitly takes into account the sparse characteristics of natural images and does not entail solving a numerically ill-conditioned backward-diffusion.

In particular, the self-similarity is defined by a weight function, which induces two types of regularization in a nonlocal fashion. Furthermore, we get superior results using preprocessed data as input for the weighted functionals.

The second part of the talk is based on the observation that the sparse coefficients that encode a given image with respect to an over-complete basis are the same that encode a blurred version of the image with respect to a modified basis. An explicit generative model is used to compute a sparse representation of the blurred image, and the coefficients of which are used to combine elements of the original basis to yield a restored image.

Professor Matthew Foreman invited to speak at the Fields Institute's Distinguished Lecture Series

Professor Matthew Foreman has been invited to speak at the Fields Institute in the fall term of 2012 as part of their Distinguished Lecture Series. "The Fields Insittute's Distinguished Lecture Series is intended to bring a leading international mathematician in a field related to the them of the thematic program to give a series of three lectures." Professor Foreman's lectures will be part of the Thematic Program on Forcing and its Applications taking place at the Institute from July - December 2012.

Backscattering of polarized beams by layered tissues

Speaker: 

Arnold Kim

Institution: 

UC Merced

Time: 

Monday, April 16, 2012 - 4:00pm to 5:00pm

Host: 

Location: 

RH 306

A layered tissue model has a thin, epithelial layer supported underneath by a thick, stromal layer. Each layer has its own optical properties which, in turn, provide useful medical diagnostic information. We present an asymptotic analysis of the boundary value problem for the vector radiative transport equation that governs a polarized beam incident on layered tissues. In doing so, we are able to propose novel methods to study the optical properties of epithelial tissue layers which have applications in the early diagnosis of cancer.

This work involves collaborations with Miguel Moscoso, Shelley Rohde, and Julia Clark.

Some Applications of Optimal Control of Systems Governed by Partial Differential Equations

Speaker: 

Todd DuPont

Institution: 

University of Chicago

Time: 

Monday, June 4, 2012 - 4:00pm to 5:00pm

Host: 

Location: 

RH 306

This talk addresses some issues of optimal control of systems whose behavior is described by partial differential equations. One of the motivations is comparing experiments and simulations, a central aspect of program validation.
Another motivation involves state and parameter estimation for physical systems, even in the presence of bad data; here the drivers have been atmospheric modeling and safe, efficient pipeline operation.

Various parts of the work described here is joint with Andrei Draganescu (University of Maryland Baltimore County), Henry H Rachford, Jr., and Richard Carter (GL Noble Denton).

Jacobian SDP Relaxation for Polynomial Optimization

Speaker: 

Jiawang Nie

Institution: 

UCSD

Time: 

Monday, April 30, 2012 - 4:00pm to 5:00pm

Host: 

Location: 

RH 306

Consider the global optimization problem of minimizing a polynomial function subject to polynomial equalities and/or inequalities. Jacobian SDP Relaxation is the first method that can solve this problem globally and exactly by using semidefinite programming. This solves an open problem in the field of polynomial optimization. Its basic idea is to use the minors of Jacobian matrix of the given polynomials, add new redundant polynomial equations about the minors to the constraints, and then apply the hierarchy of Lasserre's semidefinite programming relaxations. The main result is that this new semidefinite programming relaxation will be exact for a sufficiently high (but finite) order, that is, the global minimum of the polynomial optimization can be computed by solving a semidefinite programming problem.

Fast solvers for the symmetric discontinuous Galerkin approximation of second order elliptic problems

Speaker: 

Liuqiang Zhong

Institution: 

Chinese University of Hong Kong

Time: 

Friday, April 6, 2012 - 4:00pm to 5:00pm

Host: 

Location: 

RH 306

We develop a preconditioner and an iterative method for the linear system resulting from the discretization of second order elliptic problems by the symmetric discontinuous Galerkin methods. The key is a new stable decomposition of the piecewise polynomial discontinuous finite element space into a conforming space and a space containing the high frequency components. By using this new decomposition, we then prove that both the condition numbers of the preconditioner and the convergent rate of the iterative method are independent of the mesh size. Numerical experiments are also shown to confirm these theoretical results.

Computational methods in pattern formation solutions

Speaker: 

Yongtao Zhang

Institution: 

Notre Dame

Time: 

Monday, May 21, 2012 - 4:00pm to 5:00pm

Host: 

Location: 

RH 306

In this talk, I will present two kinds of numerical methods for mathematical models in biological pattern formation problems. The first method is the weighted essentially non-oscillatory (WENO) method for solving the nonlinear chemotaxis models. Chemotaxis is the phenomenon in which cells or organisms direct their movements according to certain gradients of chemicals in their environment. Chemotaxis plays an important role in many biological processes, such as bacterial aggregation, early vascular network formation, among others. While WENO schemes on structured meshes are quite mature, the development of finite volume WENO schemes on unstructured meshes is more difficult. A major difficulty is how to design a robust WENO reconstruction procedure to deal with distorted local mesh geometries or degenerate cases when the mesh quality varies for complex domain geometry. In this work, we combined two different WENO reconstruction approaches to achieve a robust unstructured finite volume WENO reconstruction on complex mesh geometries. The second method is the Krylov implicit integration factor (IIF) method for nonlinear reaction–diffusion and advection-reaction-diffusion equations in pattern formations. Integration factor methods are a class of ‘‘exactly linear part’’ time discretization methods. Efficient implicit integration factor (IIF) methods were developed for solving systems with both stiff linear and nonlinear terms, arising from spatial discretization of time-dependent partial differential equations (PDEs) with linear high order terms and stiff lower order nonlinear terms. The tremendous challenge in applying IIF temporal discretization for PDEs on high spatial dimensions is how to evaluate the matrix exponential operator efficiently. For spatial discretization on unstructured meshes to solve PDEs on complex geometrical domains, how to efficiently apply the IIF temporal discretization was open. Here, I will present our results in solving this problem by applying the Krylov subspace approximations to the matrix exponential operator. We applied this novel time discretization technique to discontinuous Galerkin (DG) methods on unstructured meshes for solving reaction–diffusion equations. Then we extended the Krylov IIF method to solve advection-reaction-diffusion PDEs and achieved high order accuracy. Numerical examples are shown to demonstrate the accuracy, efficiency and robustness of the methods.

Pages

Subscribe to UCI Mathematics RSS