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:
"Flattening a Hierarchical Clustering through Active Learning" by Fabio Vitale, Anand Rajagopalan, and Claudio Gentile
"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:
"MaxHedge: Maximising a Maximum Online with Theoretical Performance Guarantees" by Stephen Pasteris, Fabio Vitale, Kevin Chan, and Shiqiang Wang.
"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:
"A Reduction for Efficient LDA Topic Reconstruction" by Matteo Almanza, Flavio Chierichetti, Alessandro Panconesi, Andrea Vattani
"Top-k Lists: Models and Algorithms" by Flavio Chierichetti, Anirban Dasgupta, Shahrzad Haddadan, Ravi Kumar, Silvio Lattanzi
"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.