-
18/09/2023 09:30
-
19/09/2023 09:30
-
19/09/2023 14:00
-
20/09/2023 10:00
-
20/09/2023 16:00
-
21/09/2023 09:30
-
22/09/2023 09:30
-
25/09/2023 08:45
-
25/09/2023 09:15
-
25/09/2023 09:30
Abstract. Does the recent craze about chatbots affect Computer Algebra? If so, in which way? As a non-expert, I will share some observations.
Aller à la page de la contribution -
25/09/2023 10:30
-
25/09/2023 11:00
Abstract. There are several deterministic factoring algorithms of complexity N1/4+o(1) going back to the 1970s. A few years ago Hittmeir lowered the exponent to 2/9, and I subsequently improved it further to 1/5. In this talk I will explain the key ideas behind these new algorithms.
Aller à la page de la contribution -
25/09/2023 14:00
Abstract. In modern numerical computations, real numbers are approximated with floating-point numbers, of the form s2e, where s and e are integers with a fixed precision. This representation is compact and can represent numbers with small and large magnitudes. In this talk, we will generalize this idea to approximate univariate polynomial functions with piecewise polynomials of the form s(X)Xe...
Aller à la page de la contribution -
25/09/2023 15:00
Abstract. We develop and compare two algorithms for computing first-order right-hand factors in the ring of linear Mahler operators ℓrMr+⋯+ℓ1M+ℓ0 where ℓ0,…,ℓr are polynomials in x and Mx=xbM for some integer b≥2. In other words, we give algorithms for finding all formal infinite product solutions of linear functional equations ℓr(x)f(xbr)+⋯+ℓ1(x)f(xb)+ℓ0(x)f(x)=0.
Aller à la page de la contribution
The first of our algorithms... -
25/09/2023 16:00
-
25/09/2023 16:30
Abstract. Coppersmith's generalization of Wiedemann's algorithm is a key ingredient in algorithms for integer factorization or discrete logarithms. I will describe how, in recent years, it has also successfully been applied in contexts arising from algorithms for polynomial equations, such as sparse FGLM algorithms, or modular composition.
Aller à la page de la contribution -
26/09/2023 09:30
Abstract. Cohn and Umans proposed a group-theoretic approach to bounding the exponent of matrix multiplication. Previous work within this approach ruled out certain families of groups as a route to obtaining ω=2, while other families of groups remain potentially viable. In this work we turn our attention to matrix groups, whose usefulness within this framework was relatively unexplored.
Aller à la page de la contribution
To... -
26/09/2023 10:30
-
26/09/2023 11:00
Abstract. An algebraic circuit computes a polynomial using addition and multiplication operators. Understanding the power of algebraic circuits has close connections to understanding general computation. Despite this, not many lower bounds are known for even simple Sigma Pi Sigma (product-depth 1) circuits. Before our work, the best known lower bound for product-depth 1 circuit was (slightly...
Aller à la page de la contribution -
26/09/2023 14:00
Abstract. Border (or approximative) complexity of polynomials plays an integral role in GCT (Geometric Complexity Theory) approach to P!=NP. This raises an important basic question: can arbitrary approximations of simple polynomials involve exponential-precision which may not be efficiently simulable? Circuits of depth 3 or 4, are a good testing ground for this question. Recently, Kumar proved...
Aller à la page de la contribution -
26/09/2023 15:00
Abstract. Riemann—Roch spaces are a cornerstone of modern applications of algebra to various areas of computer science: error correcting codes, secret sharing, multi-party computations, zero-knowledge proofs, resilience in distributed storage systems, interactive oracle proofs... Best performances are achieved for specific families of spaces known to be difficult to compute.
Aller à la page de la contribution
We will present a... -
26/09/2023 16:00
-
27/09/2023 09:30
Abstract. The topic of the talk connects skew-fields, polynomial identity testing, invariant theory and optimization. By a linear matrix we mean a matrix having homogeneous linear entries and the non-commutative rank is the rank when we consider the variables as elements of the appropriate free skew-field. Computing it is a relaxation of determining the maximal rank of a matrix in a given...
Aller à la page de la contribution -
27/09/2023 10:30
-
27/09/2023 11:00
Abstract. Polynomial factoring is one of the most fundamental problems in the area of computational algebra. Its variants have attracted a huge amount of attention in the last half-a-century. On the other hand, algebraic complexity theory classifies polynomials, into complexity classes, according to computational resources. Could we show that these classes afford polynomial factoring...
Aller à la page de la contribution -
27/09/2023 18:30
-
28/09/2023 09:30
Abstract. I will survey some concrete lattice computations that have appeared in the context of some recent papers in applied cryptography that I have been involved with, and pose some open problems and speculative improvements that arose in these contexts.
Aller à la page de la contribution -
28/09/2023 10:30
-
28/09/2023 11:00
Abstract. In 2011, Jao and De Feo proposed a key exchange based on the presumed hardness of the following problem: given two elliptic curves, and the images of a few points through a secret isogeny, compute this isogeny.
Aller à la page de la contribution
In 2022, a polynomial-time algorithm was discovered. This powerful new tool has broken many cryptosystems, but has also lead to new constructions, and other applications in... -
28/09/2023 14:00
Abstract. : Among the classical problems in computational linear algebra, the computation of the characteristic polynomial is of great relevance for applications as it reflects most invariants of the input matrix. It is a key component in the solution of many other related problems, such as computing eigenvalues, invariant factors and invariant subspace decomposition, testing matrices for...
Aller à la page de la contribution -
28/09/2023 15:00
Abstract. Most familiar operations on N-digit real numbers (sum, product, square root, exponential, logarithm, etc.) can be computed in time quasilinear in N. However, this kind of asymptotic statement hides details which can add up to huge differences in practical running times. We will discuss how to think about optimizing arbitrary-precision algorithms, with a detailed look at...
Aller à la page de la contribution -
28/09/2023 16:00
-
28/09/2023 16:30
Abstract. The non-negativity of a function on a finite abelian group can be certified by its Fourier sum of squares (FSOS). We propose a method of certifying the nonnegativity of an integer valued function by an FSOS certificate, which is defined to be an FSOS with a small error. We prove the existence of exponentially sparse polynomial and rational FSOS certificates and provide two methods to...
Aller à la page de la contribution -
29/09/2023 09:30
We discuss how sparse interpolation in computer algebra and exponential analysis in digital signal processing can cross-fertilize and lead to new results. The Nyquist constraint [11] is the digital signal processing equivalent of stating that the argument of a complex exponential exp(φ∆) with φ ∈ C and ∆ ∈ R+ can only be retrieved uniquely under the condition that |=(φ)|∆ < π. It governs...
Aller à la page de la contribution -
29/09/2023 10:30
-
29/09/2023 11:00
Abstract. Sparse polynomials with integer coefficients are a basic building block in computer algebra systems, as well as an important fundamental object for algorithmic study. Since at least the 1980s, efficient algorithms have been constructed based on the flexibility afforded by changing the integer modulus repeatedly during the computation. This talk will attempt to briefly survey some of...
Aller à la page de la contribution -
-
-
-
-
Choisissez le fuseau horaire
Le fuseau horaire de votre profil: