Seminars archive

Following a suggestion of Erdos (1974), Alon and Yuster (2006) investigated the maximum number of orientations graphs of a given order admit if we forbid copies of a fixed tournament. We discuss the analogous problem in which certain restricted orientations of typical graphs of a given order and a given number of edges are considered.\\ \\This is joint work with M. Collares (Belo Horizonte), R. Morris (Rio de Janeiro) and G. O. Mota (Sao Paulo).

Tensors (aka multiway arrays) can be instrumental in revealing latent correlations residing in high dimensional spaces. Despite their applicability to a broad range of applications in machine learning, speech recognition, and imaging, inconsistencies between tensor and matrix algebra have been complicating their broader utility. Researchers seeking to overcome those discrepancies have introduced several different candidate extensions, each introducing unique advantages and challenges. In this talk, we review some of the common tensor definitions, discuss their limitations, and introduce our tensor product framework which permits the elegant extension of linear algebraic concepts and algorithms to tensors. Following introduction of fundamental tensor operations, we discuss in further depth tensor decompositions and in particular the tensor SVD (t-SVD) and its randomized variant, which can be computed efficiently in parallel. We present details of the t-SVD, theoretical results, and provide numerical results that show the promise of our approach for compression and analysis of operators and datasets, highlighting examples such as facial recognition and model reduction.

The Birkhoff--von Neumann decomposition expresses a doubly stochastic matrix as a convex combination of permutation matrices. This talk will be an introduction to this decomposition. We are going to see its use in solving sparse linear systems, and investigate some algorithmic and combinatorial problems associated with it. This talk contains results from joint work with Michele Benzi (Emory Univ., Atlanta), Fanny Dufosse (Inria, France), Kamer Kaya (Sabanci Univ, Turkey), and Ioannis Panagiotas (ENS Lyon, France).

The u-invariant of a field is the maximal dimension of a nonsingular anisotropic quadratic form over that field, whose order in the Witt group of the field is finite. By a classical theorem of Elman and Lam, the u-invariant of a linked field of characteristic different from 2 can be either 0,1,2,4 or 8. The analogous question in the case of characteristic 2 remained open for a long time.. We will discuss the proof of the equivalent statement in characteristic 2, recently obtained in a joint work by Andrew Dolphin and the speaker.

In order to control the spectrum of singularities of the generalized Riemann function, we need to find sharp bounds for certain kind of Gauss sums with frequencies on polynomials. This can be achieved by Weil bounds on completely irreducible algebraic curves, which lead us to prove some theorems on irreducibility of polynomials in two variables. We will prove a general theorem in this field. An example of the theorem is the absolute irreducibility of p(x)-p(y)+1, for any p(x) with integer coefficients.

In this thesis, the author proves theorems on the existence and mapping properties of tropical stacks that arise from result concerning toric Artin stacks. The author also provides a generalization, using the same ideas from the toric Artin stacks, of recent work involving analytic stacks and their tropicalizations. The author also proves results on the notion of a tropical jet space.

Skyline, also known as Maxima in computational geometry or Pareto in business management field, is important for many applications involving multi-criteria decision making. The skyline of a set of multi-dimensional data points consists of the points for which no other point exists that is better in at least one dimension and at least as good in every other dimension. Although skyline computation and queries have been extensively studied in both computational geometry and database communities, there are still many challenges need to be fixed, especially in this big data ear. In this dissertation, I present several efficient and adaptive skyline computation algorithms. First, I show a faster output-sensitive skyline computation algorithm which is the state-of-the-art algorithm from the theoretical aspect. Second, traditional skyline computation is inadequate to answer queries that need to analyze not only individual points but also groups of points. To address this gap, I adapt the original skyline definition to the novel group-based skyline (G-Skyline), which represents Pareto optimal groups that are not dominated by other groups. Third, to facilitate skyline queries, I propose a novel concept Skyline Diagram, which given a set of points, partitions the plane into a set of regions, referred to as skyline polyominos. Similar to kth-order Voronoi diagram commonly used to facilitate k nearest neighbor (kNN) queries, any query points in the same skyline polyomino have the same skyline query results.