Enllaç a l'anunci, https://www.iec.cat/activitats/veure.asp?id_agenda=4566

Enllaç a resum i presentació: https://www.iec.cat/activitats/documents/2019%2001%2021%20difusi%C3%B3_Calderer(1).pdf

Ring signatures, introduced by Rivest, Shamir and Tauman (ASIACRYPT 2001), allow to sign a message on behalf of a set of users while guaranteeing authenticity and anonymity. Groth and Kohlweiss (EUROCRYPT 2015) and Libert et al. (EUROCRYPT 2016) constructed schemes with signatures of size logarithmic in the number of users. An even shorter ring signature, of size independent from the number of users, was recently proposed by Malavolta and Schröder (ASIACRYPT 2017). However, all these short signatures are only obtained relying on strong and controversial assumptions. Namely, the former schemes are both proven secure in the random oracle model while the later requires non-falsifiable assumptions.

The most efficient construction under mild assumptions remains the construction of Chandran et al. (ICALP 2007) with a signature of size Θ(√n), where n is the number of users, and security is based on the Diffie-Hellman assumption in bilinear groups (the SXDH assumption in asymmetric bilinear groups).

In this work we construct an asymptotically shorter ring signature from the hardness of the Diffie-Hellman assumption in bilinear groups. Each signature comprises Θ(∛n) group elements, signing a message requires computing Θ(∛n) exponentiations, and verifying a signature requires Θ(n^{2/3}) pairing operations. To the best of our knowledge, this is the first practical ring signature with o(√n) signatures and sublinear verification complexity.

S’anuncia una nova Viquimarató ‘**Matemàtica intermèdia**’ de la SCM, aquesta vegada amb participació de la Societat Catalana d'Estadística (SoCE) i per tant amb interès especial a treballar també en els termes estadístics.
Són convidats a participar-hi els professors d’ensenyament secundari i de primers cursos d’universitat (en actiu, jubilats o en formació) però també tota altra persona interessada en col·laborar en el manteniment de la qualitat de les pàgines de Viquipèdia amb continguts de matemàtiques i estadística d’aquests nivells d’ensenyament. La idea és seguir treballant al voltant del Viquiprojecte https://ca.wikipedia.org/wiki/Viquiprojecte:Matem%C3%A0tica_interm%C3%A8diacadascú en algun tema o algun aspecte. La convocatòria està oberta també a participants que no tinguin experiència en edició de pàgines de Viquipèdia.

Inscripció: escriviu a viquimaratoMI2017@gmail.com o dirigiu-vos a J. Solà-Morales.

Spectral clustering algorithms find clusters in a given network by exploiting properties of the eigenvectors of matrices associated with the network. As a first step, one computes a spectral embedding, that is a mapping of nodes to points in a low-dimensional real space; then one uses geometric clustering algorithms such as k-means to cluster the points corresponding to the nodes.

Such algorithms work so well that, in certain applications unrelated to network analysis, such as image segmentation, it is useful to associate a network to the data, and then apply spectral clustering to the network. In addition to its application to clustering, spectral embeddings are a valuable tool for dimension-reduction and data visualization. The performance of spectral clustering algorithms has been justified rigorously when applied to networks coming from certain probabilistic generative models.

A more recent development, which is the focus of this lecture, is a worst-case analysis of spectral clustering, showing that, for every graph that exhibits a certain cluster structure, such structure can be found by geometric algorithms applied to a spectral embedding. Such results generalize the graph Cheeger’s inequality (a classical result in spectral graph theory), and they have additional applications in computational complexity theory and in pure mathematics.

Biosketch

Luca Trevisan is a professor of electrical engineering and computer sciences at U.C. Berkeley and a senior scientist at the Simons Institute for the Theory of Computing. Luca studied at the Sapienza University of Rome, he was a post-doc at MIT and at DIMACS, and he was on the faculty of Columbia University, U.C. Berkeley, and Stanford, before returning to Berkeley in 2014. Luca’s research is in theoretical computer science, and it is focused on computational complexity and graph algorithms. Luca received the STOC’97 Danny Lewin (best student paper) award, the 2000 Oberwolfach Prize, and the 2000 Sloan Fellowship. He was an invited speaker at the 2006 International Congress of Mathematicians.

Programa, inscripció i més informació a: https://matrix2018861590936.wordpress.com/

BCNspiracy, un esdeveniment estatal de divulgació científica, amb seu a Barcelona.

BCNspiracy neix amb la missió de transmetre la necessitat i la utilitat de la ciència, explicar-la de manera senzilla, assequible i interessant.

Dintre de les activitats previstes hi ha una taula rodona de Dones Científiques moderada per Pere Estupinyà on parlarà Eva Miranda del departament.