ARC

Algorithms Randomization Computation

ARC (Algorithms, Randomisation, Computation) is a research group of the Department of Computer Science at Sapienza, University of Rome. Our research mainly lies in the study of algorithms, both theoretical and applied, with special emphasis on the interplay between chance and computation.

WE ARE HIRING!

We have several open research positions at the Junior Professor, Postdoc and PhD Student level. We are looking for talented and highly motivated people in all areas of algorithmic research, both theoretical and applied.

For inquiries email us at arc@di.uniroma1.it.

News

  • July 21, 2022: Matteo is giving a virtual presentation of "RUMs from Head-to-Head Contests" at ICML 2022

  • June 20, 2022: "The Gibbs-Rand Model" is being (virtually) presented at PODS 2022

  • May 20, 2022: Giuseppe and Matteo successfully defended their PhD thesis in front of the National Committee. Congratulations!

  • March 28, 2022: Giuseppe gave a virtual presentation of "Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models" at AISTATS 2022. This was a joint work with Flavio Chierichetti, Alessandro Panconesi, and Luca Trevisan

  • March 24, 2022: Alessandro Epasto is visiting. He gave an insightful talk about fairness in clustering.

  • February 22, 2022: Giuseppe and Matteo gave a virtual presentation of "k-Clustering with Fair Outliers" at WSDM 2022. This was a joint work with Alessandro Epasto and Alessandro Panconesi.

  • December 10, 2021: Giuseppe and Matteo gave a virtual presentation of "Online Facility Location with Multiple Advice" at NeurIPS 2021. This was a joint work with Flavio Chierichetti, Silvio Lattanzi, and Alessandro Panconesi.

  • October 7, 2021: Giuseppe and Matteo gave a virtual poster presentation of "k-Clustering with Fair Outliers" at Google's Scalable Algorithms for Semi-supervised and Unsupervised Learning Workshop.

  • April 19, 2021: Giuseppe gave a virtual presentation of "Twin Peaks, a Model for Recurring Cascades" at The Web Conference 2021. This was a joint work with Matteo Almanza, Silvio Lattanzi, and Alessandro Panconesi.

  • January 13, 2021: "Faster motif counting via succinct color coding and adaptive sampling" by Marco Bressan, Stefano Leucci and Alessandro Panconesi is accepted for publication in the ACM Transactions on Knowledge Discovery from Data (TKDD)

  • January 1, 2021: Happy New Year!

  • December 2, 2020: "OLIVAW: Mastering Othello with neither Humans nor a Penny" by Antonio Norelli and Alessandro Panconesi is accepted at the AAAI RLG 2021 workshop

  • September 26, 2020: Marco has a paper accepted at NeurIPS 2020 with oral presentation.

  • September 2, 2020: Marco is giving a short talk at HALG20, while Flavio is chairing one of the sessions.

  • February 18, 2020: Gabor Lugosi is visiting and gave a very nice talk today about network archeology, or how to find Adam in a tree.

  • February 5, 2020: Andreas Krause is visiting us. He gave an interesting seminar on safe and efficient reinforcement learning.

  • January 26, 2020: Alessandro is speaking at the celebrations for David Shmoys' 60th Birthday at Cornell tech, NYC

  • January 23, 2020: Alessandro is giving a talk at Università degli Studi di Milano

  • January 17, 2020: Charles Elkan is visiting. He gave a great seminar on learning to rank in search engines.

  • January 10, 2020: Flavio has a paper accepted at WWW2020!

  • December 8-14, 2019: Marco and Fabio present "Correlation Clustering with Adaptive Similarity Queries" at NeurIPS in Vancouver.

  • December 2, 2019: Luca Trevisan is visiting. He gave a nice talk on subexponential-time algorithms for approximating MAXCUT.

  • November 28, 2019: Mohsen Ghaffari is visiting, and presented his recent groundbreaking result on derandomizing distributed algorithms.

  • October 29-30, 2019: Raffaele Giancarlo is visiting. His October 30 seminar will open season 2 of the ARC-types seminar series

  • October 13-18, 2019: Marco is in Poznan (PL) attending the AlgPIE workshop on theoretical computer science.

  • October 25, 2019: Alessandro and Giuseppe are in enchanting Venice, giving talks at ECLT

  • September 30, 2019: Marco enjoys the thrilling nightlife of Milan while visiting the CS dept of Università Statale, where he talked about motif counting

  • September 10-15, 2019: Marco presents "Counting subgraphs via DAG tree decompositions" at ESA/IPEC.

  • September 4, 2019: Two papers accepted at NeurIPS 2019:

    1. "Flattening a Hierarchical Clustering through Active Learning" by Fabio Vitale, Anand Rajagopalan, and Claudio Gentile

    2. "Correlation Clustering with Adaptive Similarity Queries" by Marco Bressan, Nicolò Cesa-Bianchi, Andrea Paudice, and Fabio Vitale

  • August 22, 2019: "Mixing time bounds for graphlet random walks" by Matteo Agostini, Marco Bressan, and Shahrzad Haddadan is accepted in Inf. Proc. Lett.

  • July 15, 2019: "Counting subgraphs via DAG tree decompositions" by Marco Bressan is accepted at IPEC 2019

  • July 7-12, 2019: the glorious Castle of the Metamorphoses in Rocca Sinibalda hosts the Billion User Cloud Applications summer school, co-organized by us.

  • June 30, 2019: "Motivo: fast motif counting via succinct color coding and adaptive sampling" by Marco Bressan, Stefano Leucci, and Alessandro Panconesi is accepted at VLDB 2019

  • June 27, 2019: Ola Svensson is visiting. He gave today a very nice talk on the current world record for approximating the k-means clustering

  • June 15, 2019: Alessandro is awarded, together with Aravind Srinivasan, the 2019 Edsger W. Dijkstra Prize. Congratulations!

  • May 9, 2019: Christian Scheideler is visiting. He gave today a very nice talk on algorithmic problems for hybrid networks in our series ARC-types

  • April 18, 2019: Devdatt Dubhashi is visiting. He gave yesterday a very nice overview talk titled "The Age of AI and Automation: What is Possible and What are the Risks?" and will give today a more technical talk on the use of optimal transport theory in ML in the ARC-types seminar series.

  • April 17, 2019: Flavio is presenting the paper "Matroids, Matchings, and Fairness", by Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii at AISTATS 2019 in Okinawa, Japan

  • April 10, 2019: Christian Sohler is visiting. He gave today a very nice talk on core sets in our seminar series ARC-types

  • March 8, 2019: Danupon Nanongkai is visiting. He gave today a great talk in our seminar series ARC-types

  • February 21-23, 2019: Artur Czumaj is visiting. On Wednesday he will be giving a talk on computing maximum matching in the map-reduce model in our seminar series ARC-types

  • January 27, 2019: Flavio delivers "LSH, Similarities and Distortion", an invited talk at SOFSEM 2019, Nový Smokovec, Slovakia

  • January 23, 2019: "On the Distortion of Locality Sensitive Hashing" by Flavio Chierichetti, Ravi Kumar, Alessandro Panconesi, and Erisa Terolli is accepted for publication in SIAM Journal on Computing

  • January 21-22, 2019: Nikhil Bansal is visiting. On Tuesday, Nikhil gave a great talk on discrepancy in our seminar series ARC-types.

  • December 23, 2018: Two papers accepted at AISTATS 2019:

    1. "MaxHedge: Maximising a Maximum Online with Theoretical Performance Guarantees" by Stephen Pasteris, Fabio Vitale, Kevin Chan, and Shiqiang Wang.

    2. "Matroids, Matchings and Fairness" by Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii

  • December 20, 2018: Silvio Lattanzi delivers a very interesting talk thereby inaugurating our seminar series ARC-types

  • December 10-14, 2018: Alessandro, Giuseppe and Matteo are visiting Google Zürich

  • November 14, 2018: Alessandro is visiting Chalmers University, in sunny Göteborg. Today he presents "New Algorithms for Efficient LDA Topic Reconstruction" at the local Big Data seminar

  • November 5-6, 2018: Paolo Frasca, CNRS Gernoble, is visiting

  • November 1, 2018: Matteo Almanza and Giuseppe Re join the group as PhD students. Welcome!

  • October 9, 2018: Marco proudly presents "Sublinear algorithms for local graph centrality estimation" by Marco Bressan, Enoch Peserico, and Luca Pretto at FOCS 2018, October 7-9, in Paris

  • October 4, 2018: Alessandro gives an invited talk at Digital Tools & Uses, Paris, October 3-5, 2018

  • September 14, 2018: Alessandro presents "(Im)possibility of LDA Topic Reconstruction" at Foulard 2018, very nice workshop in Bertinoro

  • September 5, 2018: We have three papers accepted at NIPS 2018! They are:

    1. "A Reduction for Efficient LDA Topic Reconstruction" by Matteo Almanza, Flavio Chierichetti, Alessandro Panconesi, Andrea Vattani

    2. "Top-k Lists: Models and Algorithms" by Flavio Chierichetti, Anirban Dasgupta, Shahrzad Haddadan, Ravi Kumar, Silvio Lattanzi

    3. "Online Reciprocal Recommendation with Theoretical Performance Guarantees" by Fabio Vitale, Nikos Parotsidis, Claudio Gentile

  • July 16, 2018: Marco (briefly) presents "On Approximating PageRank Locally with Sublinear Query Complexity", by Marco Bressan, Enoch Peserico, and Luca Pretto, at SPAA 2018, in Vienna

  • July 12, 2018: Shahrzad is in beautiful Prague to present "On the Complexity of Sampling Vertices Uniformly from a Graph" at ICALP 2018

  • July 11, 2018: Flavio presents "Learning a Mixture of Two Multinomial Logits" , by Flavio Chierichetti, Ravi Kumar, Andrew Tomkins, at ICML 2018 in Stockholm

  • July 1, 2018: The paper "Sublinear algorithms for local graph centrality estimation" by Marco Bressan, Enoch Peserico, Luca Pretto has been accepted at FOCS 2018

  • June 3-7, 2018: We moved for the week to the stunning location of Rocca Sinibalda to participate in "RSE 2018: Research in Small Ensembles". Great workshop, amazing location!

  • May 14, 2018: "Learning a Mixture of Two Multinomial Logits" by Flavio Chierichetti, Ravi Kumar, Andrew Tomkins is accepted at ICML 2018

  • May 2, 2018: Erisa is leaving our group today to join Max Planck in Saarbrücken as a postdoc in Gerhard Weikum's group. Erisa we will miss you, all the best for your career!

  • April 24, 2018: "On Approximating PageRank Locally with Sublinear Query Complexity" by Marco Bressan, Enoch Peserico, Luca Pretto is accepted as a Brief Announcement at SPAA 2018

  • April 19, 2018: Flavio delivers a popular science talk in Palermo in front of eager high school students to inspire them to do great deeds in computer science. The context is that of the Lezioni Lincee di Scienze Informatiche

  • April 17, 2018: The paper "On the Complexity of Sampling Vertices Uniformly from a Graph" by Flavio Chierichetti and Shahrzad Haddadan has been accepted at ICALP 2018

  • April 10, 2018: The paper "Tracks from hell-- when when finding a proof may be easier than checking it" by Matteo Almanza, Stefano Leucci and Alessandro Panconesi has been accepted at FUN 2018

  • March 22, 2018: The paper "Songs of the Future Past, an Experimental Study of Online Persuaders" by Marzia Antenore, Alessandro Panconesi, and Erisa Terolli has been accepted at ICWSM-18

  • March 3, 2018: Marco presented "On approximating the stationary distribution of time-reversible Markov chains" by Marco Bressan, Enoch Peserico and Luca Pretto, at STACS 2018 in Caen, France

  • February 14, 2018: The paper "Motif counting beyond five nodes" by Marco Bressan, Flavio Chierichetti, Ravi Kumar, Stefano Leucci, and Alessandro Panconesi has been accepted for publication in ACM Transactions on Knowledge Discovery from Data (TKDD)

  • February 12, 2018: Erisa successfully defended her PhD thesis "Markets, Friends and Motifs-- Mining Social and Market Forces in the Online Domain" in front of the national committee. Congratulations!

  • January 7, 2018: Flavio presents "Discrete Choice, Permutations, and Reconstruction" by Flavio Chierichetti, Ravi Kumar, Andrew Tomkins at SODA '18, New Orleans, USA

  • December 22, 2017: The paper "On Similarity Prediction and Pairwise Clustering" by Stephen Pasteris, Fabio Vitale, Claudio Gentile and Mark Herbster is accepted at ALT 2018

  • December 13, 2017: Erisa, together with Lorenzo De Stefani, presented "Tiered Sampling: An Efficient Method for Approximate Counting of Sparse Motifs in Massive Graph Streams" by Lorenzo De Stefani, Erisa Terolli and Eli Upfal, at IEEE BigData '17, Boston, USA

  • December 11, 2017: The paper "On approximating the stationary distribution of time-reversible Markov chains" by Marco Bressan, Enoch Peserico, and Luca Pretto is accepted at STACS 2018

  • December 7, 2017: The paper "Rumour spreading and Conductance" by Flavio Chierichetti, George Giakkoupis, Silvio Lattanzi and Alessandro Panconesi is accepted for publication on JACM

  • December 6, 2017: Alessandro delivers an invited talk in the magic environment of Venice at Valuetools 2017 titled "The limits of recommendations, and the role of social ties"

  • November 5-10, 2017: Alessandro and Flavio participate in Data-driven Algorithmics, a great workshop in the beautiful venue of Bertinoro Castle

  • October 12, 2017 - "Tiered Sampling: An Efficient Method for Approximate Counting of Sparse Motifs in Massive Graph Streams" by Lorenzo de Stefani, Erisa Terolli, and Eli Upfal is accepted for presentation at IEEE BigData 2017

  • October 9, 2017 - "Discrete Choice, Permutations, and Reconstruction", by Flavio Chierichetti, Ravi Kumar, Andrew Tomkins is accepted for presentation at SODA 2018

  • September 27, 2017 - Flavio delivers an invited talk titled "Locality Sensitive Hashing, Similarities and Distortion" at SPIRE 2017 in Palermo

  • September 16-10, 2017 - We are participating in WAL-E 2017: Workshop on Approximating and Learning, Efficiently. Wonderful workshop, amazing location!

  • September 7, 2017 - "Fair Clustering Through Fairlets", by Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Sergei Vassilvitskii is accepted for presentation at NIPS 2017

  • August 9, 2017 - Flavio presented "On the Power Laws of Language: Word Frequency Distributions" by Flavio Chierichetti, Ravi Kumar, and Bo Pang, at SIGIR '17, Tokyo, Japan

  • June 28-30, 2017 - Nelly Litvak (U Twente & U Eindhoven) is visiting us

  • June 1, 2017 - Fabio Vitale joins our group. Welcome!

  • May 15, 2017 - "Algorithms for ℓp Low-Rank Approximation" by Flavio Chierichetti, Sreenivas Gollapudi, Ravi Kumar, Silvio Lattanzi, Rina Panigrahy, and David Woodruff is accepted for presentation at ICML 2017

  • May 11, 2017 - Mohsen Ghaffari (ETH Zürich) is visiting us. He gave today a very nice and well attended talk on "LOCAL Algorithms: The Chasm Between Randomized and Deterministic"

  • April 19, 2017 - The paper 'On the power laws of language: word frequency distributions' by Flavio Chierichetti, Ravi Kumar and Bo Pang is accepted for presentation at SIGIR 2017.

  • April 7, 2017 - Alessandro is one of the recipients of the WWW 2017 Outstanding Reviewer Award, given to reviewers "who went well beyond their call of duty, provided exceptional reviews and contributed a lot to discussions'' during the PC meetings of WWW 2017.

  • April 6, 2017 - Alessandro presented 'The Distortion of Locality Sensitive Hashing ' by F. Chierichetti, R. Kumar, A. Panconesi and E.Terolli in Dagsthul, Germany.

  • April 4, 2017 - On a balmy afternoon in Perth, Australia, Flavio is one of the panelist at BIG 2017 (and the only one from Academia), to discuss 'Deep learning for data analytics: panacea or snake oil?' together with Marc Najork, Andrew Tomkins, David Hawking, Mounia Lalmas, and Ed H. Chi

  • April 4, 2017 - On a sunny morning in Perth, Australia, Flavio delivers his invited talk at BIG 2017, the Big-data Innovators Gathering 2017, one of the satellite events of WWW 2017.

  • February 28, 2017 - Alessandro presented again 'The Distortion of Locality Sensitive Hashing ' by F. Chierichetti, R. Kumar, A. Panconesi and E.Terolli, this time at Google NY.

  • February 24, 2017 - Alessandro presented 'The Distortion of Locality Sensitive Hashing ' by F. Chierichetti, R. Kumar, A. Panconesi and E.Terolli at Brown University, Computer Science Department.

  • February 8, 2017 - Marco presented the paper 'Counting Graphlets: Space vs Time' by M. Bressan, F. Chierichetti, R. Kumar, S. Leucci, A. Panconesi at WSDM 2017 in Cambridge, UK.

  • January 11, 2017 - Erisa presented the paper 'The Distortion of Locality Sensitive Hashing ' by F. Chierichetti, R. Kumar, A. Panconesi and E.Terolli at ITCS 2017 in Berkeley, CA. [video]

  • November 28, 2016 - Morteza Zadimoghaddam (Google Research) is visiting us. He gave today a very nice and well attended talk on "Scalable algorithms for data summarization problems"

  • November 2016 - 'Counting Graphlets: Space vs Time' by M. Bressan, F. Chierichetti, R. Kumar, S. Leucci, A. Panconesi has been accepted for presentation at WSDM 2017.

  • August 31, 2016 - Alessandro presented 'The Limits of Popularity-Based Recommendations, and the Role of Social Ties' by M. Bressan, S. Leucci, A. Panconesi, P. Raghavan, and E. Terolli, at the University of Salzburg, the city that is the birthplace of Wolfgang Amadeus Mozart.

  • August 17, 2016 - Alessandro presented the paper 'The Limits of Popularity-Based Recommendations, and the Role of Social Ties' [pdf], by M. Bressan, S. Leucci, A. Panconesi, P. Raghavan, and E. Terolli, at the 22nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2016) in San Francisco

  • July 12, 2016 - Alessandro presented the paper 'The Computational Psychology of Digital Shop Assistants', by M. Antenore, G. Leone, A.Panconesi, and E. Terolli, at the 3rd ISA Forum of Sociology in Vienna. The paper was nominated for the 2016 Walter Buckley Award but, alas, did not get the prize.

  • June 8-10, 2016 - SINS 2016, an exciting workshop in glorious surroundings that we organised together with Marcello Pelillo of Ca' Foscari, University of Venice.