Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Concept

Problème du mot pour les groupes

Publications associées (15)

Gospel of the Marseille Docker - Nicholas Derybolsky from 1952

Sila Karatas

This text, accompanied by a ‘gospel’ that I made by montaging the US-recorded captions, is an attempt for re-narrating Marshall Plan’s discourse on the working class, aka the so-called ‘free labor’ of the US against the ‘communist labor’ of the “Soviet thr ...

EPFL Press2023

Equivalence Checking for Orthocomplemented Bisemilattices in Log-Linear Time

Viktor Kuncak, Simon Guilloud

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 ...

Springer2022

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

Kim-Manuel Klein, Alexandra Anna Lassota

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 = ...

SPRINGER HEIDELBERG2022

Formula Normalizations in Verification

Viktor Kuncak, Simon Guilloud, Dragana Milovancevic, Mario Bucev

We propose a new approach for normalization and simplification of logical formulas. Our approach is based on algorithms for lattice-like structures. Specifically, we present two efficient algorithms for computing a normal form and deciding the word problem ...

2023

Adaptation in Stochastic Algorithms: From Nonsmooth Optimization to Min-Max Problems and Beyond

Ahmet Alacaoglu

Stochastic gradient descent (SGD) and randomized coordinate descent (RCD) are two of the workhorses for training modern automated decision systems. Intriguingly, convergence properties of these methods are not well-established as we move away from the spec ...

EPFL2021

Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage

Volkan Cevher, Alp Yurtsever

This paper considers a fundamental class of convex matrix optimization problems with low-rank solutions. We show it is possible to solve these problem using far less memory than the natural size of the decision variable when the problem data has a concise ...

2017

Undecidability through Fourier series

In computability theory a variety of combinatorial systems are encountered (word problems, production systems) that exhibit undecidability properties. Here we seek such structures in the realm of Analysis, more specifically in the area of Fourier Analysis. ...

Elsevier Science Bv2016

Trace maps for Mackey algebras

Baptiste Thierry Pierre Rognerud

Let G be a finite group and R be a commutative ring. The Mackey algebra μR(G) shares a lot of properties with the group algebra RG however, there are some differences. For example, the group algebra is a symmetric algebra and this is not always the case fo ...

Elsevier2015

Approximation algorithms for regret minimization in vehicle routing problems

Adrian Aloysius Bock

In this thesis, we present new approximation algorithms as well as hardness of approximation results for NP-hard vehicle routing problems related to public transportation. We consider two different problem classes that also occur frequently in areas such a ...

EPFL2014

Endotrivial modules for p-solvable groups

Jacques Thévenaz

We determine the torsion subgroup of the group of endotrivial modules for a finite solvable group in characteristic p. We also prove that our result would hold for p-solvable groups, provided a conjecture can be proved about the case of p-nilpotent groups. ...

2011

Elementary abelian subgroups in p-groups of class 2

All the results in this work concern (finite) p-groups. Chapter 1 is concerned with classifications of some classes of p-groups of class 2 and there are no particularly new results in this chapter, which serves more as an introductory chapter. The "geometr ...

EPFL2009

Non-unitarisable representations and random forests

Nicolas Monod

We establish a connection between Dixmier's unitarisability problem and the expected degree of random forests on a group. As a consequence, a residually finite group is non-unitarisable if its first L2-Betti number is non-zero or if it is finitely generate ...

Oxford University Press2009

The link between the infinite mapping class group of the disk and the braid group on infinitely many strands

φ For all finite n ∈ N, there is a well-known isomorphism between the standard braid group Bn and the mapping class group π0Hn. This isomorphism has been exhaustively studied in literature, and generalized in many ways. For some basic topological reason, t ...

EPFL2008

From Set Membership to Group Membership: A Separation of Concerns

André Schiper

We revisit the well-known group membership problem and show how it can be considered a special case of a simple problem, the set membership problem. In the set membership problem, processes maintain a set whose elements are drawn from an arbitrary universe ...

2006

Modules d'endo-p-permutation

Jean-Marie Urfer

This dissertation is concerned with the study of a new family of representations of finite groups, the endo-p-permutation modules. Given a prime number p, a finite group G of order divisible by p and an algebraically closed field k of characteristic p, we ...

EPFL2006

Publications associées (15)