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 is in algorithms, both theoretical and applied, with special emphasis on probabilistic algorithms. Our current, but by no means exclusive, focus are problems arising from the study of social networks and the Web.

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

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