Indiscreet logarithms in finite fields of small characteristic

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called 2-stage stochastic. A 2-stage stochastic ILP is an integer program of the form min{c(T)x vertical bar Ax = ...

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n. Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed ...

Two prominent categories for achieving coordinated multirobot displacement are flocking and navigation in formation. Both categories have their own body of literature and characteristics, including their respective advantages and disadvantages. While typic ...

The goal of this thesis is the development and the analysis of numerical methods for problems where the unknown is a curve on a smooth manifold. In particular, the thesis is structured around the three following problems: homotopy continuation, curve inter ...

As historical stone masonry structures are vulnerable and prone to damage in earthquakes, investigating their structural integrity is important to reduce injuries and casualties while preserving their historical value. Stone masonry is a composite material ...

In this article, we consider decentralized optimization problems where agents have individual cost functions to minimize subject to subspace constraints that require the minimizers across the network to lie in low-dimensional subspaces. This constrained fo ...

We present a quasilinear time algorithm to decide the word problem on a natural algebraic structures we call orthocomplemented bisemilattices, a subtheory of boolean algebra. We use as a base a variation of Hopcroft, Ullman and Aho algorithm for tree isomo ...

We study the computational complexity of the optimal transport problem that evaluates the Wasser- stein distance between the distributions of two K-dimensional discrete random vectors. The best known algorithms for this problem run in polynomial time in th ...

Non-convex constrained optimization problems have become a powerful framework for modeling a wide range of machine learning problems, with applications in k-means clustering, large- scale semidefinite programs (SDPs), and various other tasks. As the perfor ...

Finding cycles in directed graphs enables important applications in various domains such as finance, biology, chemistry, and network science. However, as the size of graph datasets continues to grow, it becomes increasingly difficult to discover cycles wit ...

We derive a dynamical field theory for self-propelled particles subjected to generic torques and forces by explicitly coarse-graining their microscopic dynamics, described by a many-body Fokker-Planck equation. The model includes both intrinsic torques ind ...

This work aims to study the effects of wind uncertainties in civil engineering structural design. Optimising the design of a structure for safety or operability without factoring in these uncertainties can result in a design that is not robust to these per ...

In this thesis we present and analyze approximation algorithms for three different clustering problems. The formulations of these problems are motivated by fairness and explainability considerations, two issues that have recently received attention in the ...

This paper presents a distributed shadow dynamic consensus (DSDC) framework to address the generation company (GENCO) strategic bidding problem in the independent system operator (ISO) operation. First, each sub-group is defined according to the communicat ...

Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also ...

This paper reports on the computation of a discrete logarithm in the finite field F-230750, breaking by a large margin the previous record, which was set in January 2014 by a computation in F-29234. The present computation made essential use of the elimina ...

The advent of comprehensive synaptic wiring diagrams of large neural circuits has created the field of connectomics and given rise to a number of open research questions. One such question is whether it is possible to reconstruct the information stored in ...

We present a novel framework for the reconstruction of 1D composite signals assumed to be a mixture of two additive components, one sparse and the other smooth, given a finite number of linear measurements. We formulate the reconstruction problem as a cont ...

With the looming threat of large-scale quantum computers, a fair portion of recent cryptographic research has focused on examining cryptographic primitives from the perspective of a quantum adversary. Shor's 1994 result revealed that quantum computers can ...

Indiscreet logarithms in finite fields of small characteristic

Chat with Graph Search

The double exponential runtime is tight for 2-stage stochastic ILPs

Approximation Algorithms for Allocation and Network Design

Results on Sparse Integer Programming and Geometric Independent Sets

Hybrid Flock - Formation Control Algorithms

Retraction-based numerical methods for continuation, interpolation and time integration on manifolds

Geometrical Treatise on the Modelling of 3D Particulate Inclusion-Matrix Microstructures with an Application to Historical Stone Masonry Walls

Quantization for Decentralized Learning Under Subspace Constraints

Equivalence Checking for Orthocomplemented Bisemilattices in Log-Linear Time

Discrete Optimal Transport with Independent Marginals is #P-Hard

Augmented Lagrangian Methods for Provable and Scalable Machine Learning

Fast Parallel Algorithms for Enumeration of Simple, Temporal, and Hop-Constrained Cycles

Microscopic field theory for structure formation in systems of self-propelled particles with generic torques

Multi-Level Monte Carlo Methods for Uncertainty Quantification and Risk-Averse Optimisation

Fairness and Explainability in Clustering Problems

Distributed Shadow Dynamic Consensus Optimization Framework for Power Market with Parameterization Bidding Strategy of GENCOs

Streaming and Matching Problems with Submodular Functions

Computation Of A 30750-Bit Binary Field Discrete Logarithm

Bayesian reconstruction of memories stored in neural networks from their connectivity

Continuous-Domain Formulation of Inverse Problems for Composite Sparse-Plus-Smooth Signals

Security in the Presence of Quantum Adversaries