C. Seshadhri (Seshadhri Comandur)

Professor
University of California, Santa Cruz
 
1156 High Street
Baskin School of Engineering, Engineering 2, Mail Stop: 310
Santa Cruz, CA
 
Office: E2-347A
Phone: 831-502-8036

Students, please read this before emailing.
Office hours (Fall 2020): Tu 11-12, Zoom (passcode 104)
Th 3:15-4:15, Zoom (passcode 101)

Brief Bio

C. Seshadhri (Sesh) is a professor of Computer Science at the University of California, Santa Cruz. Prior to joining UCSC, he was a researcher at Sandia National Labs, Livermore in the Information Security Sciences department, during 2010-2014. His primary interest is in mathematical foundations of big data, especially modeling and algorithms. By and large, Sesh works at the boundary of theoretical computer science (TCS) and data mining. His work spans many areas: sublinear algorithms, graph algorithms, graph modeling, scalable computation, and data mining. In the theory world, his work has resolved numerous open problems in monotonicity testing and graph property testing. A number of his papers in the interface of TCS and applied algorithms have received paper awards at KDD, WWW, ICDM, SDM, and WSDM. He received the 2019 SDM/IBM Early Career Award for Excellence in Data Analytics. Sesh got his Ph.D from Princeton University and spent two years as a postdoc in IBM Almaden Labs.


CV: (old) pdf


Program Committees

FSTTCS 2020, RANDOM 2019, WWW 2019, SDM 2019, WWW 2018, ITCS 2018, WSDM 2018, ALENEX 2018, KDD 2017, SIAM CSC 2016, SIAMNS 2015, ITCS 2015, SODA 2014, FSTTCS 2013, FOCS 2012


Selected papers (Full list)

• The impossibility of low-rank representations for triangle-rich complex networks, with Aneesh Sharma, Andrew Stolman, and Ashish Goel
PNAS 2020   UCSC news link     Youtube, part 1     Youtube, part 2
• The power of pivoting for exact clique counting, with Shweta Jain
WSDM 2020 (Best paper)
• Faster sublinear approximation of the number of $k$-cliques in low-arboricity graphs, with Talya Eden and Dana Ron
SODA 2020
• Random walks and forbidden minors II: A $poly(d\varepsilon^{-1})$-query tester for minor-closed properties of bounded-degree graphs, with Akash Kumar and Andrew Stolman
STOC 2019 (Invited to special issue)
• Finding forbidden minors in sublinear time: a $O(n^{1/2+o(1)})$-query one-sided tester for minor closed properties on bounded degree graphs, with Akash Kumar and Andrew Stolman
FOCS 2018 (Invited to special issue)
• A Fast and Provable Method for Estimating Clique Counts Using Tur\'{a}n's Theorem, with Shweta Jain
WWW 2017 (Best paper)
• When Hashes Met Wedges: A Distributed Algorithm for Finding High Similarity Vectors, with A. Sharma, A. Goel
WWW 2017
• Approximately Counting Triangles in Sublinear Time, with T. Eden, A. Levi, D. Ron
FOCS 2015
• Diamond Sampling for Approximate Maximum All-pairs Dot-product (MAD) Search, with G. Ballard, T. Kolda, A. Pinar
ICDM 2015 (Best paper)
• Finding the Hierarchy of Dense Subgraphs using Nucleus Decompositions, with A. Sariyuce, A. Pinar, U. Catalyurek
WWW 2015 (Best paper finalist)
• Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties, with D. Chakrabarty, K. Dixit, M. Jha
SODA 2015 (Invited to special issue)
• Decompositions of Triangle-Dense Graphs, with R. Gupta, T. Roughgarden
ITCS 2014
• A Space Efficient Streaming Algorithm for Triangle Counting using the Birthday Paradox, with M. Jha, A. Pinar
KDD 2013 (Best student paper)
• An o(n) Monotonicity Tester for Boolean Functions over the Hypercube, with D. Chakrabarty
STOC 2013 (Invited to special issue)
• Optimal Bounds for Monotonicity and Lipschitz Testing over Hypercubes and Hypergrids, with D. Chakrabarty
STOC 2013
• Triadic Measures on Graphs: The Power of Wedge Sampling, with A. Pinar, T. Kolda
SDM 2013 (Best research paper)


Postdocs

Suman Kalyan Bera
Caleb Levy

PhD Students

Andrew Stolman
Noujan Pashanasangi
Konstantinos Zampetakis
William Bolden
Sabyasachi Basu

Graduated Students

Shweta Jain (PhD, 2020)
Hadley Black (MS, 2018), PhD student at UCLA


PTReview

Eric Blais, Sourav Chakraborty, and I started a blog called Property Testing Review, a monthly digest of property testing and sublinear algorithms papers. Currently, it is edited by Clement Canonne, Gauram Kamath, and myself.