Abstract

There are many excellent software packages for the everyday calculation of graph properties, and other packages, also very good, for the creation of diagrams, but finding both functions in the same tool is not that easy. Autograph modestly tries to fill that void, combining the power of the NetworkX software with an edition area where graphs can be drawn as they would be drawn on a blackboard, but fostering greater interactivity, since the values of many properties are automatically updated with each modification. It is also possible to undo and redo changes, graphs can be stored and retrieved, and even different topologies can be used. We will be able to see this graph editor at work, not forgetting its possible competitors, and also to comment on which new features would be interesting for their addition in future versions.

Encara que hi ha molts paquets de programari excel·lents per fer càlculs habituals de la teoria de grafs, i altres, també molt bons, per crear diagrames, no és tan freqüent que totes dues funcions coincideixin en la mateixa eina. Autograph intenta modestament omplir aquest buit, combinant la potència del programari NetworkX amb una àrea d'edició que permet dibuixar els grafs de manera semblant a com els dibuixaríem en una pissarra, però facilitant la interactivitat, ja que els valors de diverses propietats s'actualitzen automàticament amb cada modificació. També és possible desfer i refer canvis, els grafs es poden desar i recuperar, i fins i tot es pot treballar en diferents topologies. Podrem veure aquest editor de grafs en funcionament, sense oblidar els seus possibles competidors, i també comentar quines noves característiques serien interessants per incorporar-les a futures versions.

Abstract

The theory of dependency graphs is a powerful toolbox to prove asymptotic normality of sums of random variables. I will explain how this works, and then present a more general notion of weighted dependency graphs. Applications to random graphs, random permutations and subwords in a Markov chain will be given.

Abstract

Finite permutations can be thought of as models of the theory of two linear orders. This viewpoint sits well with the study of permutation patterns since, in that context, permutation classes are simply theories with universal axioms. However, it sits much less well with the algebraic view of permutations since we cannot recover the effect of the permutation as a function. We consider some cases where it is possible to reconcile the two views and answer questions such as: in which permutation classes is it possible to recognise the existence of fixed points (or more generally k-cycles) with a formula from the logic of two linear orders?

Per registrar-vos, podeu fer-ho mitjançant l'enllaç següent:

http://wiley.qualtrics.com/jfe/form/SV_832Ht3M4vXDYaP3.

Abstract

In social choice theory, many combinatorial problems have been addressed from the viewpoint of parameterized complexity. For many of these problems, though, either their fixed-parameter tractability is not known, or the fastest known algorithms have doubly-exponential dependence on the parameters. These shortcomings (among others) led Bredereck et al. to pose their “Nine Research Challenges in Social Choice Theory”.

In this work we provide a general approach to many fundamental voting and bribing problems in social choice theory, when parameterized by the number of candidates. Our approach shows, for the first time, fixed-parameter tractability of those problems, or provides the first algorithms with singly-exponential dependence on the parameter. Thereby, we solve “Challenge #2” by Bredereck et al., and substantially contribute towards resolving their “Challenge #1”.

In particular, we show that R-Swap Bribery is fixed-parameter tractable parameterized by the number of candidates and solvable in single-exponential time, for many voting rules R; this extends an earlier double-exponential time algorithm by Dorn and Schlotter that is restricted to the unit-cost case.

Abstract: After its introduction in the summer of 2016, Pokémon GO quickly became the most popular game around. The game requires players---called trainers---to walk outside to search for and catch Pokémon. Now that the first craze is over, it is time for scientists to analyze various aspects of the game. Since the game requires a mobile device with GPS and is (in part) essentially a search problem played on the streets, we can analyze it using competitive analysis. We define an abstraction of searching for Pokémon using a geometric graph and call it the Pokémon GO search problem. We show that for general geometric graphs, there is no constant competitive ratio to find a Pokémon. However, if the graph has convex faces only, or if the graph has constant-bounded geometric dilation, then there is an O(1)-competitive search strategy.

Abstract

En esta charla abordaremos el problema de Moore en Gráficas Mixtas, el cual fue introducido por Bosàk en 1979, a partir de ese momento este problema ha sido abordado por varios autores y se han logrado distintos resultados de los cuales hablaremos en esta charla, además expondremos nuestras recientes aportaciones en este tema. Por otro lado, buscando generalizar este problema, debido a que dicho problema está relacionado de manera natural con el problema de las Jaulas, plantearemos el problema de Jaulas Mixtas y mostraremos los avances que tenemos en dicho problema. 

In this talk, we present an identification protocol and a signature scheme due to Galbraith, Petit and Silva. We rely on the hardness of an isogeny problem on supersingular elliptic curves, which is believed to be a hard problem, and even the best known quantum algorithms to solve it run in exponential time.

Our identification protocol relies on two key ingredients. First, the good mixing properties of supersingular isogeny graphs, which allow us to move through the graph efficiently and at the same time achieve random-looking outputs.

Second, we make use of Deuring’s correspondence, which identifies endomorphism rings of supersingular elliptic curves with maximal orders in a certain quaternion algebra.  We use the algorithm of Kohel-Lauter-Petit-Tignol (ANTS 2014) to compute ideals of a certain norm between maximal orders in the quaternion algebra. This will allow to simulate the protocol with indistinguishable distribution.

Finally, we use the standard technique of Fiat-Shamir to derive a signature scheme from the identification protocol, and we discuss its security.

Background on elliptic curves, quaternion algebras and expander graphs will be provided at the beginning of the talk, only cryptography definitions are required.

L’any 2016 es commemora el tercer centenari de la mort d’un dels matemàtics més rellevants de la història, Gottfried Wilhelm Leibniz (Leipzig, 1646 – Hannover, 1716). Amb aquest cicle volem commemorar aquest centenari, adherint-nos així a tots els homenatges que la comunitat científica està celebrant arreu del món.

Si cal destacar quelcom de l’obra matemàtica de Leibniz, podríem citar els seus nombrosos treballs sobre el càlcul infinitesimal, els determinants, la combinatòria, la lògica i els jocs d’atzar.

Entendre el pensament matemàtic de Leibniz és molt complex i requereix submergir-se no només en els seus textos matemàtics sinó també en els filosòfics relacionats amb el seu sistema metafísic, amb la seva interpretació dels processos de raonament com una àlgebra del pensament, i en les nombroses cartes i manuscrits recentment editats.

Un dels objectius del cicle és presentar la figura de Leibniz des de la seva vessant com a matemàtic, donant a conèixer la seva obra i el seu impacte. A més, l’estudi de Leibniz i de la seva obra contribuirà a transmetre als participants del cicle una percepció de la matemàtica com a ciència útil, humana, interdisciplinària, dinàmica i heurística.

Amb aquest homenatge a Leibniz, pretenem conèixer millor el seu pensament, així com les seves fonts i l’impacte que va tenir la seva obra tant al segle XVIII, com posteriorment.

El cicle s'estructura en dues sessions, amb dues xerrades cadascuna:

• 4 novembre 2016

M. Rosa Massa (UPC): “Una aproximació a la figura de Leibniz: filòsof, físic, enginyer i matemàtic”
Guillermo Lusa (UPC): “Tras las huellas de Leibniz”

• 18 novembre 2016

Mònica Blanco (UPC): “Algunes qüestions al voltant del càlcul de Leibniz”
Siegmund Probst (Leibniz Archive): “Gottfried Wilhelm Leibniz (1646-1716) and John Wallis (1616-1703)”

Trobareu més informació sobre el cicle a http://arban.espais.iec.cat/2016/10/11/leibniz-300-anys-despres/.