Fall 2017 weekly seminar

  • Tuesday, 19/12, room A56, 12:30. Alvaro Fuentes (INRIA) - Anisotropic convolution.

    Abstract: Convolution surfaces was a standard tool for modeling smooth objects. With modern techniques similar results can be achieved with spline-based surfaces, but still special care need to be taken in the "gluing" of patches. No such problems occur when modeling with convolution surfaces. Moreover since this technique is inherently skeleton-based, it is still an interesting tool for this type of modeling. I'll present the standard definitions along with some (simple) mathematical background. I'll discuss extensions and in particular our extension: anisotropic convolution; which allows for more modeling freedom.

  • Tuesday, 13/11, room A56, 13:00. Evelyne Hubert (INRIA Méditerranée (Sophia-Antipolis)) - Multivariate sparse interpolation in terms of generalized Chebyshev polynomial bases.

    Abstract: Given a polynomial that can be evaluated at chosen point, sparse interpolation offers to first recover the support of this polynomial. We examine the situation where the polynomial is assumed to consist of a small number of generalized multivariate Chebyshev polynomials. This is joint work with Michael Singer (North Carolina State University)

  • Monday, 13/11, room A56, 14:00. Panos Theodoropoulos (NKUA) - Probabilistic Model Counting with Short XORs.

    Abstract: The idea of counting the number of satisfying truth assignments (models) of a CNF formula by adding random parity constraints can be traced back to the seminal work of Valiant and Vazirani, showing that NP is as easy as detecting unique solutions. While theoretically sound, the random parity constraints in that construction have the following drawback: each constraint, on average, involves half of all variables. As a result, the branching factor associated with searching for models that also satisfy the parity constraints quickly gets out of hand. However as we recently proved, one can work with much shorter parity constraints and still get rigorous mathematical guarantees, especially when the number of models is large so that many constraints need to be added. The method is based on the realization that the essential feature for random systems of parity constraints to be useful in probabilistic model counting is that the geometry of their set of solutions resembles an error-correcting code.

  • Friday, 10/11, room A3, 13:30. Clement Laroche (NKUA) - Singular Points and Blow-ups.

    Abstract: We discuss of singular points of algebraic curves in C². Singular points are those at which a curve is not smooth, such as self-intersections or cusps. We present a device, the blow-up, that can be used to regularize the curve by embedding it into a bigger space. The different kinds of singular points are then exposed by the means of a topological invariant, the Puiseux pairs. We finally show how this invariant can be used to compute the "complexity" of a singular point.

  • Friday, 3/11, room A3, 14:00. Vangelis Anagnostopoulos (NKUA) - Polytope oracles in optimization and sampling.

    Abstract: Polytopes in optimization and sampling problems are usually given by implicit rep- resentations through oracles. The most basic oracle is the polytope membership ora- cle which can identify whether a query point q lies inside P or not and is often used as the basis for more complex oracles, such as the separation oracle or the bound- ary oracle. In this work we aim to design, implement and analyse algorithms for approximating the membership oracle in polytopes given as the intersection of half- spaces in high dimension, by trading exactness for efficiency. Previous approaches were based on classic polytope approximation techniques which, however, have complexity that scales exponentially in the dimension and are, thus, intractable in high dimension. We establish a straightforward reduction from approximate poly- tope membership to approximate nearest neighbor search among points and obtain complexity bounds polynomial in the dimension, by exploiting recent progress in the complexity of nearest neighbor search. We then employ this new membership oracle to obtain a solution for the boundary oracle in high dimension. Lastly, we evaluate our algorithms experimentally and report results.

  • Friday, 20/10, room A9, 16:00: Jan Legersky (JKU Linz) - An upper bound for real embeddings result of rigid graphs with 7 vertices.
  • Thursday, 19/10, room A9, 12:30: Ioannis Psarros (NKUA) - Chebyshev polynomials in high dimensional proximity problems e.g. the approximate closest pair problem.
  • Wednesday, 11/10, room A56, 12:00: Timur Sadukov (Plekhanov U. Moscow) - Amoeba-shaped polyhedral complex of an algebraic hypersurface.
  • Thursday, 28/09, room A9, 13:30: Alvaro Fuentes (INRIA) - Scaffolding skeletons using spherical Voronoi diagrams.

    Abstract: Given a skeleton made of line segments we describe how to obtain a coarse mesh (or scaffold) of a surface surrounding it. With our method we can treat skeleton with cycles (closed) and get an optimal solution in terms of the number of quads. We also present a formal proof of feasibility. Our work is based in SQM algorithm by Baerentzen et al. (Comput. & Graphics 2012) which cannot handle closed skeletons.

  • Thursday, 21/09, room A9, 14:30: Jan Legersky (JKU Linz) - Graphs with flexible labelings

    Abstract: A graph with a flexible labeling has infinitely many realizations in a plane, up to Euclidean isometries, such that the distance between two vertices connected by an edge is equal to the length given by the flexible labeling. We provide a combinatorial characterization of these graphs, which is based on colorings of edges by two colors such that a certain property is satisfied for every cycle. We discuss existence of such colorings for Laman graphs, which are know to be minimally generically rigid, but many of them are flexible for a nongeneric choice of lengths.

Previous ΕρΓΑ Seminars and meetings


For the courses' web pages (mostly in Greek), click on the flags.

Graduate Courses

  • Algorithms in Structural Bioinformatics: algebraic & geometric algorithms (Spring) (since 2009 with Dr. E. Chrysina, Hellenic Research Foundation)
  • Computational Algebra (Fall) (since 2014 with Dr. C. Konaxis)
  • Computational Geometry (Spring)
  • Advanced Geometric Algorithms (2015) (Fall)
  • Geometric Design (2004--2010) (by Prof. P. Kaklis, NTUA)
Most postgrad courses cross-listed with the Graduate Program ALMA / MPLA.

Undergraduate Courses

  • Computational Geometry (8th semester) (Spring)
  • Algorithms in Structural bioinformatics (8th semester, special Topics) (Spring)
  • Software development for algorithmic problems (7th semester, since 2014)
  • Math for Computer Science (5th semester) (2008, 2010)
  • Discrete Math (1st year) (2002-2008, 2016)