MPI-INF and MPI-MiS joint workshop on Theoretical Computer Science and Algebraic Geometry

MPI-INF and MPI-MiS joint workshop on Theoretical Computer Science and Algebraic Geometry

All talks are in the MPI-SWS building E1 5 on the ground floor in the main large lecture hall. Tuesday afternoon was an exception.

Monday, January 14

• 08:45-09:15 Registration
• 09:15-10:45 Kurt Mehlhorn: Some Reflections on the Interplay of Theory and Practice. [Video]
  • I like to refer to myself as a mathematician in the morning and an engineer in the afternoon. The two sides of my personality interact fruitfully. I will discuss some outcomes of this interaction:
    (1) The insight that writing papers and books is not enough.
    (2) Engineering failures that asked and are still asking for new theory. New Theory that led to better engineering practice.
    (3) Unexpected experimental findings that asked for a theoretical explanation.
• 11:15-12:15 Michael Sagraloff: On Recent Development in Computing Roots of Polynomials and Polynomial Systems [Video]
  • The computation of the roots of a univariate polynomial is one of the best studied problems in the areas of computer algebra and numerical analysis. Nevertheless, until recently, there has still been a large discrepancy between methods that are considered to be efficient in practice and those that achieve good theoretical bounds. In the first part of this talk, I will review some recently developed algorithms for real and complex root finding, which are simple and practical on the one hand and whose worst-case bit complexity matches that of the best methods in theory on the other hand.
    In the second part of my talk, I will focus on the more general problem of computing the solutions of a given zero-dimensional polynomial system in d variables. A common approach for computing the set S of solutions is to first project S into one dimension (e.g. using resultant computation and univariate root finding) and then to recover the solutions from the projections. The latter step turns out to be difficult if the projection direction is not known to be separating for the solutions. I will review a simple and efficient algorithm for the certified computation of S, which only needs to compute projections of the solutions but no further algebraic manipulations. It computes a separating direction of small bit-size as well as isolating boxes for all solutions for the cost of O(d) projections of the solutions. I will further review a symbolic-numeric algorithm to count the number of solutions within a local region, which is based on a "local variant" of the rather global method from above. In contrast to global approaches, the complexity of this method mainly depends on local parameters such as the number of roots within the given region and the size of this region.
• 12:15-13:45 Lunch
• 13:45-14:45 Takeshi Tokuyama: Deformation of Determinants and Related Combinatorics and Computation [Video]
  • Determinant of a matrix is a central object in linear algebra, which is computed in polynomial time in the size of the matrix. Among several formulas on the determinant, the Vandermonde determinant formula (also called Weyl 's denominator formula of type A) and Weyl 's character formula are beautiful and powerful formulas with important applications. In this talk, I would like to talk about deformation of those formulas given in my work in 1988, and introduce its recent related topics in combinatorics such as alternating sign matrix, lattice model, partition function and enumeration algorithms.
• 15:15-16:15 Yue Ren: Tropical Geometry and Massive Parallelization [Video]
  • Tropical geometry studies combinatorial structures arising from polynomial systems. These so-called tropical varieties are highly complex objects, which is why parallelization is key. In this talk, we will briefly describe the motivation, the mathematics and the software behind computing (positive) tropical varieties using massive parallelization. Moreover, we will touch upon the core computational challenges such as working modulo large symmetry groups, basic polynomial arithmetic in high degrees, root isolation in several variables.
    This is joint work with Dominik Bendle (TU Kaiserslautern), Janko Boehm (TU Kaiserslautern), Mirko Rahn (Fraunhofer ITWM), Benjamin Schroeter (Binghamton).

Tuesday, January 15

• 09:15-10:45 Frank-Olaf Schreyer: Syzygies - usage, structure and their computation [Video]
  • Sygygy computation are at the core of computational algebraic geometry. The basic applications are the computation of Hilbert functions and of coherent sheaf cohomology. They can be used to construct interesting algebraic varieties and for unirationality proofs of certain moduli spaces.
    Boij-Soederberg theory gives a rough over all picture about the possible range of their numerical invariants.
    Detailed questions about the syzygies for example of a canonical curve are connected to existence questions of low degree rational functions on the curve.
    Their computation posses a serious challenge. In the final part of the talk I will report on the best known algorithm.
• 11:15-12:15 Fulvio Gesmundo: Tensors with Symmetries and the Complexity of Matrix Multiplication [Video]
  • The exponent of matrix multiplication omega is a fundamental constant that governs the complexity of several problems in computational linear algebra and it can be defined geometrically as the exponent of the asymptotic rate of growth of the tensor rank of the matrix multiplication tensor. Research on upper bounds on the exponent started in 1969 with the discovery of Strassen's algorithm; starting from 1989, all improvements were based on the so-called Strassen's laser method applied to Kronecker powers of the Coppersmith-Winograd tensors. Recent results by Ambainis-Filimus-LeGall proved strong barriers for this method and motivated our search for other tensors to which the laser method can be successfully applied. This search led us to classifying tensors with maximal symmetries under some natural genericity assumptions. In this seminar, I plan to present some of these recent contributions from a geometric point of view. This is joint work with A. Conner, J.M. Landsberg and E. Ventura.
• 12:15-13:45 Lunch
• 13:45-14:45 Kyo Nishiyama: Robinson-Schensted Correspondence and Flag Varieties [Video]
  • The RS correspondence in the title is a bijection between the set of permutations of order n and the set of pairs of standard tableaux of the same shape of size n.
    Though the correspondence itself is of purely combinatorial in nature, it can be understood in the language of the geometry of flag varieties. We first introduce the RS correspondence as elementary as possible, and explain how we can interpret it by using the geometry of flags.
    In the latter half of the talk, we extend the correspondence to the degenerate permutations, and explain it by using the geometry of double flag varieties.
    This talk is based on a on-going joint work with Lucas Fresse in IECL, France.
• 15:00-16:00 Khazhgali Kozhasov: Chebyshev polynomials and best rank-one approximation ratio [Video]
  • We discover new extremal properties of classical Chebyshev polynomials in the context of the theory of low-rank approximation of symmetric tensors.
• 16:30-17:30 Henning Seidler: Lower Bounds via Circuit Polynomials [Video]
  • Finding the minimum of a multivariate real polynomial is a well-known hard problem with various applications. We present a polynomial time algorithm to approximate such lower bounds via sums of nonnegative circuit polynomials (SONC). SONC yields bounds competitive to SOS in several cases, but using significantly less time and memory. Additionally, it provides a candidate for the global minimiser. By branching over the signs of the variables, we improve the bounds even further, with only a moderate increase in the running time.

Wednesday, January 16

• 09:15-10:45 Joël Ouaknine: Program Invariants [Video]
  • Automated invariant generation is a fundamental challenge in program analysis and verification, going back many decades, and remains a topic of active research. In this talk I'll present a select overview of work on this problem, mainly focussing on algebraic and semialgebraic invariants, and discuss a number of foundational open questions.
    This is joint work with Shaull Almagor, Dmitry Chistikov, Ehud Hrushovski, Engel Lefaucheux, Amaury Pouly, and James Worrell.
• 11:15-12:15 Susumu Ariki: The RSK correspondence and its variants in the light of crystal graph theory [Video]
  • The Robinson-Schensted-Knuth correspondence, the RSK correspondence for short, is the famous bijection which appears in the volume 3 of D. E. Knuth's book "The Art of Computer Programming". This correspondence lifts an identity of symmetric polynomials to the bijection. The crystal graph theory invented by Kashiwara further upgrades the bijection to an isomorphism of colored digraphs, where vertexes and directed edges are colored by Lie theoretic data. Hence, the classical theory of the RSK correspondence was incomplete in the sense that it only looked at the correspondence of the vertex sets. In this talk, I introduce the Kashiwara crystal to the audience in a purely graph theoretical manner using the RSK correspondence, the geometric grid class, the amida (the ghost leg) and the Edelman-Greene-Morse-Schilling correspondence as examples.
• 12:15-13:45 Lunch
• 13:45-14:45 Wolfram Decker: What can be Computed in Algebraic Geometry? A Survey from Historical Roots to Future Plans. [Video]
  • We give an overview on computational algebraic geometry which culminates in a discussion of today's (and also tomorrow’s) computational techniques and computer algebra systems. In particular, we will point out some of the challenges which we see in this context. The talk may help algebraic geometers to decide whether the techniques and systems provide useful tools for their own research.
• 15:15-16:15 Kunal Dutta: M-nets for Semi-algebraic Set Systems using Polynomial Partitioning [Video]
  • M-nets for range spaces were proposed by Mustafa and Ray (2014) as combinatorial analogs of Macbeath regions from convex geometry. In this talk we shall discuss how the polynomial partitioning of Elekes-Sharir and Guth-Katz, together with the shallow packing lemma of D.-Ezra-Ghosh and Mustafa, can be used to obtain M-nets for semi-algebraic range spaces.
    Time permitting, we shall also see a construction showing the optimality of our bounds.
    Joint work with B. Jartoux, A. Ghosh, N. Mustafa.
• 18:00 Dinner: China Restaurant, Hohenzollernstraße 21, 66117 Saarbrücken

Thursday, January 17

• 09:15-10:45 Markus Bläser: Testing membership in a variety, minimum circuit size problems, and algebraic natural proofs [Video]
  • A tensor has rank at most r if it can be written as the sum of r rank one tensors. The closure of the set of all rank r tensors are the tensors of border rank at most r. They form an algebraic variety. Consider some tensor of border rank > r. Any equation f of this variety such that f(t) ≠ 0 is an algebraic "proof" of the fact that t has border rank > r. In this talk, I will present some results on the complexity of testing membership in certain varieties and the relation to the circuit complexity of algebraic proofs.
    In particular, we will look at the following variant of the problem above: Given a tensor of order three, is there a nontrivial linear combination of the 1-slices of rank at most r. We call this quantity the minrank of a tensor. Testing whether a tensor has minrank at most r is NP-hard. We prove that even testing whether the border minrank is at most r is NP-hard, too. This allows us to relate the circuit size of equations for the corresponding variety to uniform Boolean complexity assumption and to formulate certain barrier results for algebraic natural proofs, a concept recently introduced by Forbes, Shpilka and Volk and independently by Grochow, Kumar, Saks and Saraf as an attempt to transfer Razborov and Rudich's famous barrier for Boolean circuit complexity to algebraic complexity theory.
    (Based on joint works with Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov, Anurag Pandey, and Frank-Olaf Schreyer)
• 11:15-12:15 Zeyu Guo: Algebraic independence testing, approximate polynomials satisfiability, and the GCT chasm [Video]
  • Algebraic independence testing of polynomials over a field F is a basic problem with several applications in theoretical computer science. When char(F) = 0, this problem has an efficient randomized algorithm thanks to the classical Jacobian criterion. Over finite fields, however, no general subexponential-time algorithm is known due to the failure of the Jacobian criterion in positive characteristic. In this talk, I will show that algebraic independence testing over finite fields are in the intersection of AM and coAM. In particular, it is unlikely to be NP-hard and joins the league of problems of "intermediate" complexity, e.g. graph isomorphism & integer factoring. Our proof is based on a novel "point counting" approach that avoids the use of the Jacobian criterion.
    Next, I will talk about another problem called approximate polynomials satisfiability, which asks if a given system of polynomial equations has an approximate solution over an algebraically closed field. I will show that this problem can be solved in PSPACE using properties of projective spaces. As an unexpected application to approximative complexity theory, we prove that hitting-sets for the class "border VP" can be designed in PSPACE. This solves an open problem posed in (Mulmuley, FOCS'12, J.AMS 2017), greatly mitigating the GCT Chasm (exponentially in terms of space complexity).
    This is joint work with Nitin Saxena and Amit Sinhababu.
• 12:15-13:45 Lunch
• 13:45-14:45 Joachim von zur Gathen: Shifted varieties and discrete neighborhoods [Video]
  • For an affine variety X defined over a finite prime field F_p and some integer h, we consider the discrete h-neighborhood of the set of F_p-rational points, consisting of those points over F_p whose distance from X is not more than h, for a natural notion of ``distance''. There is a natural upper bound on its size. We address the question whether the neighborhood's size is close to its upper bound.
    The central notion for understanding this question turns out to be the shift of a variety, which is the translation by a nonzero constant vector of the coordinates. If no absolutely irreducible component with maximal dimension of X is a shift of another component, then the answer to the question is "yes". For the opposite case, we exhibit examples where the answer is "no". When X is absolutely irreducible, the condition on shifts turns out to be necessary and sufficient. Computationally, testing the condition is coNP-complete under randomized reductions, already for simple cases.
    Joint work with Guillermo Matera.
• 15:15-16:15 Marton Hablicsek: Mathematical foundations of three-dimensional graphic statics [Video]
  • In this talk, I will provide a fundamental algebraic formulation for 3D Graphic Statics by developing equilibrium equations around the edges of the primal diagram and satisfying the equations by the closeness of the polygons constructed by the edges of the corresponding faces in the dual/reciprocal diagram. I will also describe constrained problems: when some of the positions of nodes and some of the forces are specified. Finally, I will provide numerical methods for solving the equilibrium equations and explain the advantage of using each technique. This project is joint with Masoud Akbarzadeh and Yi Guo.
• 16:30-17:30 Marieke van der Wegen: Recognizing hyperelliptic graphs [Video]
  • Based on analogies between algebraic curves and graphs, a new multigraph parameter was defined, called stable gonality. The gonality of an algebraic curve is the minimal degree of a morphism to the projective line, the stable gonality of a graph is the minimal degree of a morphism to a tree. We consider so-called hyperelliptic graphs, which are graphs of stable gonality 2, and we will see that recognizing hyperelliptic graphs can be done in quasilinear time.

Friday, January 18

• 09:15-10:15 Nitin Saurabh: On Fourier-Entropy Influence Conjecture [Video]
  • Given a Boolean function f : {-1,1}^n -> {-1,1}, define the Fourier distribution to be the distribution on subsets of [n], where each subset S of [n] is sampled with probability equaling square of the Fourier coefficient associated with S, \hat{f}(S)^2. The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai (1996) seeks to relate two fundamental measures associated with the Fourier distribution: does there exist a universal constant C>0 such that H(f) <= C Inf(f), where H(f) is the Shannon entropy of the Fourier distribution of f and Inf(f) is the total influence of f.
    We will discuss the significance of the conjecture and present new upper bounds on Fourier entropy of Boolean functions. We will also discuss its relationship with Mansour's conjecture. This talk is based on a joint work with S. Arunachalam, S. Chakraborty, M. Koucky, and R. de Wolf.
• 10:45-11:45 Suguru Tamaki: Beating Brute Force for Systems of Polynomial Equations over Finite Fields [Video]
  • Solving systems of multivariate polynomial equations over finite fields is a fundamental problem in mathematics, science and engineering. Let q be the order of the underlying field and n be the number of variables. Then, the problem can be solved by the brute force search over q^n possible solutions. We present the first algorithm that solves the problem in time faster than q^n in the worst-case. Our algorithm can count the number of solutions as well. The running time of the algorithm is roughly of the form q^{n(1-1/O(d))}, where d is the maximum degree of polynomials. We also consider a generalization of the problem, where each equation is defined by a certain type of arithmetic circuit, and give an algorithm for the generalized problem.
• 11:45-14:15 Long lunch break. The room stays the same
• 14:15-15:45 Bernd Sturmfels: Learning Algebraic Varieties from Samples [Video]
  This talk is part of the Saarland University mathematics colloquium. The room is the same as for the workshop.
  • This lecture addresses the role of algebraic geometry in data science. We discuss work with Paul Breiding, Sara Kalisnik and Madeline Weinstein, aimed at determining a real algebraic variety from a fixed finite subset of points. Existing methods are studied and new methods are developed. Our focus lies on topological and algebraic features, such as dimension and defining polynomials. All algorithms are tested on a range of datasets and made available in a software package in Julia.

• Welcome
• Accomodation
• Program