Previous talks (Winter 2021)
Date/Time: April 28, 2021
Speaker: Cathy Swaenepoel (Universite de Paris)
Title: Trace of products in finite fields and additive double character sums
Abstract: Let $C$ and $D$ be two subsets of a finite field $\F_q$ of characteristic $p$ and let $\Tr$ be the absolute trace of $\F_q$.
In the first part of this talk, we will consider some ``interesting'' subsets $A$ of $\F_p$ (such as singletons or subgroups of $\F_p^*$) and give lower bounds on $\card(C)$ and $\card(D)$ to ensure that $\Tr(CD)\cap A\neq \emptyset$.
Our method allows us to obtain explicit and optimal results (up to an absolute constant factor).
Some estimates lead to interesting combinatorial
questions.
In the second part which is a joint work with Arne Winterhof, we will see that if $D$ has some desirable structure then there is a large subset $U$ of $D$ for which the standard upper bound on the additive double character sum $\sum_{(c,u)\in C \times U} \psi(cu)$ can be improved.
The proof uses a decomposition theorem of Roche-Newton, Shparlinski and Winterhof.
This new bound allows us to improve one of the results presented in the first part of the talk as well as a result of Gyarmati and S\'ark\"ozy (provided that one of the involved sets has some desirable structure).
slides video.
Date/Time: April 14, 2021
Speaker: Anne Canteaut (INRIA)
Title: Recovering or Testing Extended-Affine Equivalence
Abstract:
Extended Affine (EA) equivalence is the equivalence relation between
two vectorial Boolean functions $F$ and $G$ such that there exist two
affine permutations $A$, $B$, and an affine function $C$ satisfying
$G = A \circ F \circ B + C$. While a priori simple, it is very difficult
in practice to test whether two functions are EA-equivalent. This
problem has two variants: EA-testing deals with figuring out whether
the two functions can be EA-equivalent, and EA-recovery is about
recovering the tuple $(A,B,C)$ if it exists.
In this talk, we present a new efficient algorithm that efficiently
solves the EA-recovery problem for quadratic functions. Though its
worst-case complexity is obtained when dealing with APN functions,
it supersedes all previously known algorithms in terms of performance,
even in this case. This approach is based on the Jacobian matrix of
the functions, a tool whose study in this context can be of independent
interest.
In order to tackle EA-testing efficiently, the best approach in practice
relies on class invariants. We discuss a new invariant based on the
so-called ortho-derivative which is applicable to quadratic APN functions,
a specific type of functions that is of great interest, and of which
tens of thousands need to be sorted into distinct EA-classes. Our
ortho-derivative-based invariant is both very fast to compute, and
highly discriminating.
Joint work with Alain Couvreur and Léo Perrin.
slides video
Date/Time: March 31, 2021
Speaker: Ivelisse Rubio (University of Puerto Rico, Rio Piedras)
Title: On Multidimensional Periodic Arrays
Abstract:
Multidimensional periodic arrays have applications for encoding data
during digital communication or storage. In many applications the
arrays are stored in memory, a burden for environments with limited
resources. Hence, it is important to provide algebraic constructions
for the arrays that assure the desired properties, are easily
implemented and have small use of memory. In the case of sequences,
their linear complexity is an important parameter, especially for
applications related to information security. In this talk we describe
different algebraic constructions of multidimensional arrays, present
a generalization of the concept of linear complexity, and analyze the
multidimensional linear complexity of several types of periodic arrays.
slides,
video
Date/Time: March 17, 2021
Speaker: Markus Grassl (University Gdansk)
Title: Algebraic Quantum Codes: New challenges for classical
coding theory?
Abstract:
The talk will discuss connections between quantum error-correcting
codes (QECCS) and algebraic coding theory. A quantum error-correcting
code is a subspace of a complex Hilbert space that allows to protect
quantum information against certain errors. Using the so-called
stabilizer formalism, we illustrate how QECCs can be constructed using
techniques from algebraic coding theory.
We will also present some open problems in classical coding theory
that are motivated by the link to quantum error-correcting codes.
The talk includes a short introduction to the relevant concepts of
quantum mechanics. slides, video
Date/Time: March 3, 2021
Speaker: Nurdagul Anbar Meidl (Sabancı University)
Title: On nilpotent automorphism groups of function fields
Abstract:
In this talk, we give a new result on the automorphisms of a function
field of genus g at least 2 over an algebraically closed field of positive
characteristic p. More precisely, we show that the order of a nilpotent
subgroup G of its automorphism group is bounded by 16(g−1) when G is
not a p-group. We observe that if |G|= 16(g−1), then (g−1) is a power
of 2. Furthermore, we provide an infinite family of function fields
attaining the bound. This is a joint work with Burcin Gunes. slides, video
Date/Time: February 17, 2021
Speaker: Claude Carlet (University of Bergen, and University of Paris 8)
Title: Image sets, nonlinearity and distance to affine functions of delta-uniform functions, and gamma-functions of APN functions
Abstract:
We revisit and take a closer look at a result of 2017, showing that the differential uniformity of any vectorial function is bounded from below by an expression depending on the size of its image set. We make explicit the resulting tight lower bound on the image set size of differentially $\delta$-uniform functions.
We improve an upper bound on the nonlinearity of vectorial functions obtained in the same reference and involving their image set size. We study when the resulting bound is sharper than the covering radius bound. We obtain as a by-product a lower bound on the Hamming distance between differentially $\delta$-uniform functions and affine functions, which we improve significantly with a second bound. This leads us to study what can be the maximum Hamming distance between vectorial functions and affine functions. We provide an upper bound which is slightly sharper than a bound by Liu, Mesnager and Chen when $m < n$, and a second upper bound, which is much stronger in the case where $m$ is near $n$.
In a second part, we initiate a study, when $F$ is a general APN function, of the Boolean function $\gamma_F$ related to the differential spectrum of $F$ (which is known to be bent if and only if $F$ is almost bent). We characterize its linear structures and specify nonexistence cases; we show, for $n$ even, their relation with the bent components of $F$. We characterize further in terms of $\gamma_F$ the fact that a component function of $F$ is bent and study if the number of bent components can be optimal. We study more deeply the relation between the Walsh transform of $\gamma_F$ and the Walsh transform of $F$. By applying the Titsworth relation to the Walsh transform $W_{\gamma_F}$, we deduce a very simple new relation satisfied by $W_F^2$. From this latter relation, we deduce, for a sub-class of APN functions, a lower bound on the nonlinearity, which is significantly stronger than $nl(F)>0$ (the only general known bound). This sub-class of APN functions includes all known APN functions. We finally show how the nonlinearities of $\gamma_F$ and $F$ are related by a simple formula
slides
video.
Date/Time: February 3, 2021
Speaker: Daqing Wan (UC Irvine)
Title: Counting solutions of large polynomial systems over finite fields
Abstract: A fundamental algorithmic problem in mathematics and computer science is to efficiently count the solutions of a multivariate polynomial system over a finite field, and over all of its finite extensions. All general algorithms so far are fully exponential in terms of the number of equations. In a recent joint work with Q. Cheng and M. Rojas, we have reduced this exponential dependence to a polynomial dependence on the number of equations. A key new ingredient is an effective version of the classical Kronecker theorem which says that set-theoretically any polynomial system in n variables can be defined by n+1 equations if the field is not too small. video