Vesselin Dimitrov (Caltech)
Abstract:
Title: Arithmetic holonomy bounds in transcendence proofs and effective Diophantine approximation. Abstract: The method of arithmetic holonomy bounds, developed presently in a collaboration with Calegari and Tang, encodes some Diophantine problems of a traditional interest into suitable generating functions with good analytic and Diophantine properties. I will present a completely explicit Ansatz and explain its fairly straightforward proof. The challenge is then to cook up holonomy template setups where the Ansatz has interesting consequences. Nevertheless, already the simplest "infinite dihedral orbifold" setup has applications including the transcendence of Pi (in a particularly simple way) and a new effective solution of the two-variable S-unit equation, but also some explicit irrationality measures for logarithms that seem to enter into a blind spot of the literature. New room: Seminarraum 00.002, Rheinsprung 21
10:15 • Universität Basel
Prashanth Amireddy
Title T.B.A. abstract
Abstract:
The PCP Theorem is a central result in theoretical computer science giving query-efficient verifiers for NP. All known proofs of the PCP Theorem rely on (multiple applications of) proof composition, where two sub-optimal PCPs are combined into an optimal one. In this work, we build improved component PCPs strong enough that only a single composition step is needed to recover the PCP Theorem. In particular, we give a new and direct construction (i.e., without composition) of a constant-query PCP with proof size 2^{n^ε} for arbitrarily small constant ε > 0, which is a regime of parameters evaded by prior constructions.Our constructions are based on a new Zero-on-Variety Test for checking whether an oracle f : F^m → F is identically zero on a variety V ⊆ F^m (where F is a finite field). While previous works largely tackle this problem for the setting of V = H^m (a product set), our test applies to much more general varieties, with proof size governed by a measure known as the Macaulay basis complexity of the variety. Instantiating this framework with two specific varieties and composing the resulting PCPs thus yields a proof of the PCP Theorem with a single composition. Joint work with Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, and Sophus Valentin Willumsgaard.
11:00 • EPF Lausanne, INJ114
Prof. Dr. Dimitry Dolgopyat (University of Maryland)
Up the Down Staircase abstract
Abstract:
<p><span style="caret-color: #ffffff; color: #000000; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; display: inline !important; float: none;">We describe generic points for linear flows with bounded </span><span style="caret-color: #ffffff; color: #000000; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; display: inline !important; float: none;">type slope on the infinite staircase. </span><span style="caret-color: #ffffff; color: #000000; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; display: inline !important; float: none;">As an application we characterize bounded type rotation numbers for </span><span style="caret-color: #ffffff; color: #000000; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; display: inline !important; float: none;">which the error terms for Kronicker discrepancy </span><span style="caret-color: #ffffff; color: #000000; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; display: inline !important; float: none;">are uniformly distributed. A key step in our proof is the local limit </span><span style="caret-color: #ffffff; color: #000000; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; display: inline !important; float: none;">theorem for inhomogeneous Markov chains </span><span style="caret-color: #ffffff; color: #000000; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; display: inline !important; float: none;">in the regime of large deviations. Based on a joint work with Omri Sarig.</span></p>
13:30 • ETH Zentrum, Rämistrasse 101, Zürich, Building HG, Room G 19.1
Chiara Spadafora (Swiss Post)
From Theory to Deployment: Insights from the Swiss Post E-Voting Protocol abstract
Abstract:
<p>How do cryptography and real-world constraints meet in an e-voting system? This talk examines how cryptographic protocols are translated into a real-world e-voting system, involving legal requirements, operational procedures, and human factors. The main focus of the talk is the e-voting protocol currently deployed by some Swiss cantons to enable citizens to securely cast their votes online in legally binding elections. We then move from the present to the near future, detailing the new protocol under development and highlighting how it is expected to improve both the security and the verifiability of the system.
Throughout the talk, we keep an eye on practical constraints: how the Federal Ordinance on electronic voting shapes trust assumptions and transparency requirements, and how operational procedures influence the generation of election parameters and the verification of protocol steps. We also address usability and accessibility, discussing how the voting process can be made understandable and verifiable for all voters. We close by outlining how external experts and independent implementations contribute to the continuous evaluation and analysis of the protocol.</p>
15:00 • Uni Neuchatel, B217
Francesco Lin (Columbia University)
Coexact 1-form spectral gaps and three-dimensional topology abstract
Abstract:
The spectral gap of the Hodge Laplacian on coexact 1-forms is a fundamental quantity associated to a Riemannian manifold which has attracted quite a lot of attention in recent years. I will begin by discussing the role it plays in topological problems about three-manifolds (such as the existence on taut foliations on rational homology spheres) via its relation with Floer theoretic invariants. Motivated by this, I will then focus on the case of hyperbolic manifolds, and describe techniques to determine explicitly such spectral gaps in concrete examples (including certain infinite families). This is joint work with M. Lipnowski.
15:30 • ETH Zentrum, Rämistrasse 101, Zürich, Building HG, Room G 43
Prof. Dr. Aymeric Dieuleveut (Ecole Polytechnique)
Abstract:
First-order methods are widely used in optimization and machine learning, and their behavior is often analyzed through the spectrum of worst case convergence rates. Obtaining such guarantees is often difficult and both time consuming and error-prone. Starting with the work of Drori and Teboulle (2014), novel techniques have been used to gain numerical insights, leading to the release of various performance estimation (PE) software. In this talk, I will show how various computer-aided techniques can be used to study first-order optimization methods in a systematic way. From performance estimation problems with automated Lyapunov discovery, to symbolic regression and computer algebra systems, novel tools completely reshape the way we approach theory of optimization. As a main example, I will focus on error feedback methods used with compressed communication in distributed optimization. While error feedback has been widely studied, existing theory often provides untight (thus unreliable) bounds. I will present tight analyses with matching lower bounds that allow a fair comparison between error feedback schemes and standard compressed gradient descent, and help explain when error feedback is useful and when it is not.Overall, the talk aims to show how various computer-aided proofs can lead to clearer and more reliable insights into first-order optimization methods.
16:15 • Universität Bern, Hörsaal B78, ExWi, Sidlerstrasse 5, 3012 Bern
Michele Battagliola (Universität St.Gallen)
The Code Equivalence Problem in Cryptography abstract
Abstract:
<p>Given two linear codes, the Code Equivalence Problem asks to find (if it exists) an isometry between them. In this talk we introduce linear code equivalence and its main variants (permutation, monomial). We then discuss its crucial role as a hardness assumption in post-quantum digital signatures, with particular focus on LESS and related schemes, such as LEAST. Finally, we present new cryptanalysis techniques based on power codes that efficiently solve permutation and linear code equivalence for low dimension codes.</p>
16:30 • Uni Neuchatel, B217