Here's a list of my publications. If you want some extra information or have some questions, please feel free to email me. My email addresses are sesh[at]ucsc[dot]edu and csesha[at]gmail[dot]com.

Manuscripts


Refereed Conference and Journal Papers

• Sublinear Time Estimation of Degree Distribution Moments: The Degeneracy Connection
Talya Eden, Dana Ron, and C. Seshadhri
International Colloquium on Automata, Languages, and Programming (ICALP) 2017
abstract     arxiv:1604.03661

• Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps
Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and C. Seshadhri
International Colloquium on Automata, Languages, and Programming (ICALP) 2017
abstract     arxiv:1703.05199

• A Fast and Provable Method for Estimating Clique Counts Using Tur\'{a}n's Theorem
Shweta Jain and C. Seshadhri
World Wide Web (WWW) 2017 (Best paper)
abstract     arxiv:1611.05561

• ESCAPE: Efficiently Counting All 5-Vertex Subgraphs
Ali Pinar, C. Seshadhri, and V. Vishal
World Wide Web (WWW) 2017
abstract     arxiv:1601.09411

• When Hashes Met Wedges: A Distributed Algorithm for Finding High Similarity Vectors
Aneesh Sharma, C. Seshadhri, and Ashish Goel
World Wide Web (WWW) 2017
abstract     arxiv:1703.01054

• Accurate and Nearly Optimal Sublinear Approximations to Ulam Distance
Timothy Naumovitz, Michael Saks, and C. Seshadhri
Symposium on Discrete Algorithms (SODA) 2017
abstract

• Directed Closure Measures for Networks with Reciprocity
C. Seshadhri, Ali Pinar, Nurcan Durak, and Tamara G. Kolda
Journal of Complex Networks 2017
abstract     arxiv:1302.6220

• Trigger Detection for Adaptive Scientific Workflows Using Percentile Sampling
Janine C. Bennett, Ankit Bhagatwala, Jacqueline H. Chen, Ali Pinar, Maher Salloum, and C. Seshadhri
SIAM Journal on Scientific Computing 2016
abstract     arxiv:1411.2689

• A Mountaintop View Requires Minimal Sorting: A Faster Contour Tree Algorithm
Benjamin Raichel and C. Seshadhri
Symposium on Computational Geometry (SOCG) 2016 (Invited to special issue)
Discrete and Computational Geometry 2016
abstract     arxiv:1411.2689

• Characterizing short-term stability for Boolean networks over any distribution of transfer functions
C. Seshadhri, Andrew M. Smith, Yevgeniy Vorobeychik, Jackson Mayo, and Robert C. Armstrong
Physical Review E 2016
abstract     APS     arxiv:1409.4360


• Approximately Counting Triangles in Sublinear Time
Talya Eden, Amit Levi, Dana Ron, and C. Seshadhri
Foundations of Computer Science (FOCS) 2015
abstract     arxiv:1504.00954

• Diamond Sampling for Approximate Maximum All-pairs Dot-product (MAD) Search
Grey Ballard, Tamara G. Kolda, Ali Pinar, and C. Seshadhri
International Conference on Data Mining (ICDM) 2015 (Best paper)
abstract     arxiv:1506.03872

• Catching the head, the tail, and everything in between: a streaming algorithm for the degree distribution
Olivia Simpson, C. Seshadhri, and Andrew McGregor
International Conference on Data Mining (ICDM) 2015
abstract     github code     arxiv:1506.02574

• When a Graph is not so Simple: Counting Triangles in Multigraph Streams
Madhav Jha, C. Seshadhri, and Ali Pinar
Asilomar Conference on Signals, Systems and Computers, ACSSC 2015
abstract     arxiv:1310.7665


• Path Sampling: A Fast and Provable Method for Estimating 4-Vertex Subgraph Counts
Madhav Jha, C. Seshadhri, and Ali Pinar
World Wide Web (WWW) 2015
abstract     arxiv:1411.4942

• Finding the Hierarchy of Dense Subgraphs using Nucleus Decompositions
Ahmet Erdem Sariyuce, C. Seshadhri, Ali Pinar, and Umit V. Catalyurek
World Wide Web (WWW) 2015 (Best paper finalist)
abstract     arxiv:1411.3312

• Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties
Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha, and C. Seshadhri
Symposium on Discrete Algorithms (SODA) 2015 (Invited to special issue)
abstract     arxiv:1404.0718     ECCC-TR14-042

• FAST-PPR: Scaling Personalized PageRank Estimation for Large Graphs
Peter Lofgren, Siddhartha Banerjee, Ashish Goel, and C. Seshadhri
SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) 2014
abstract     arxiv:1404.3181

• A Scalable Generative Graph Model with Community Structure
Tamara G. Kolda, Ali Pinar, Todd Plantenga, and C. Seshadhri
SIAM Journal of Scientific Computing (SISC) 2014
abstract     arxiv:1302.6636

• Counting Triangles in Massive Graphs with MapReduce
Tamara G. Kolda, Ali Pinar, Todd Plantenga, C. Seshadhri, and Christine Task
SIAM Journal of Scientific Computing (SISC) 2014
abstract     arxiv:1301.5887

• Why do Simple Algorithms for Triangle Enumeration work in the Real World?
Jonathan Berry, Luke Fostvedt, Daniel Nordman, Cynthia Phillips, C. Seshadhri, and Alyson Wilson
Innovations in Theoretical Computer Science (ITCS) 2014
abstract     conf

• Decompositions of Triangle-Dense Graphs
Rishi Gupta and Tim Roughgarden and C. Seshadhri
Innovations in Theoretical Computer Science (ITCS) 2014
abstract     conf     arxiv:1309.7440

• A Provably-Robust Sampling Method for Generating Colormaps of Large Data
David Thompson and Janine Bennett and C. Seshadhri and Ali Pinar
IEEE Symposium on Large-Scale Data and Visualization (LDAV) 2013
abstract     conf

• An Optimal Lower Bound for Monotonicity Testing over Hypergrids
Deeparnab Chakrabarty and C. Seshadhri
International Workshop on Randomization and Computation (RANDOM) 2013
abstract     conf     arxiv:1304.5264     ECCC-TR13-062

• A Space Efficient Streaming Algorithm for Triangle Counting using the Birthday Paradox
Madhav Jha, C. Seshadhri, and Ali Pinar
SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) 2013 (Best student paper)
abstract     conf     arxiv:1212.2264

• A Scalable Null Model for Directed Graphs Matching All Degree Distributions: In, Out, and Reciprocal
Nurcan Durak, Tamara G. Kolda, Ali Pinar, C. Seshadhri
IEEE Workshop on Network Science (NSW) 2013
abstract     conf     arxiv:1210.5288

• An o(n) Monotonicity Tester for Boolean Functions over the Hypercube
Deeparnab Chakrabarty and C. Seshadhri
Symposium on Theory of Compting (STOC) 2013 (Invited to special issue)
abstract     conf     ECCC-TR13-029

• Optimal Bounds for Monotonicity and Lipschitz Testing over Hypercubes and Hypergrids
Deeparnab Chakrabarty and C. Seshadhri
Symposium on Theory of Compting (STOC) 2013
abstract     conf     ECCC-TR12-030

• Triadic Measures on Graphs: The Power of Wedge Sampling
C. Seshadhri, Ali Pinar, and Tamara G. Kolda
SIAM Conference on Data Mining (SDM) 2013 (Best research paper)
abstract     conf     arxiv:1202.5230

• Space Efficient Streaming Algorithms for the Distance to Monotonicity and Asymmetric Edit Distance
Michael Saks and C. Seshadhri
Symposium on Discrete Algorithms (SODA) 2013
abstract     conf     arxiv:1204.1098

• Finding Cycles and Trees in Sublinear Time
Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, and Christian Sohler
Random Structures and Algorithms 2012
abstract     arxiv:1007.4230

• Degree Relations of Triangles in Real-world Networks and Graph Models
Nurcan Durak, Ali Pinar, Tamara G. Kolda, and C. Seshadhri
Conference on Information and Knowledge Management (CIKM) 2012
abstract     conf     arxiv:1207.7125

• Vertex Neighborhoods, Low Conductance Cuts, and Good Seeds for Local Community Methods
David F. Gleich and C. Seshadhri
SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) 2012
abstract     conf     arxiv:1112.0031 (old version)     Code and data

• Self-improving Algorithms for Coordinate-wise Maxima
Ken Clarkson, Wolfgang Mulzer, and C. Seshadhri
Symposium on Computation Geometry (SoCG) 2012
SIAM Journal on Computing 2014
abstract     conf     journal(arxiv:1211.0952)

• Community Structure and Scale-free Collections of Erdos-Renyi Graphs
C. Seshadhri, Tamara G. Kolda, and Ali Pinar
Physical Review E 2012
abstract     arxiv:1112.3644     journal     Code and data

• Are we there yet? When to stop a Markov Chain while Generating Random Graphs
Jaideep Ray, Ali Pinar, C. Seshadhri
Workshop on Algorithms and Models for the Web Graph (WAW) 2012
abstract     conf     arxiv:1202.3473

• The Similarity between Stochastic Kronecker and Chung-Lu Graph Models
Ali Pinar, C. Seshadhri, and Tamara G. Kolda
SIAM Conference on Data Mining (SDM) 2012
abstract     conf     arxiv:1110.4925

• An In-Depth Analysis of Stochastic Kronecker Graphs
C. Seshadhri, Ali Pinar, and Tamara G. Kolda
International Conference on Data Mining (ICDM) 2011
Journal of the ACM 2013
abstract     conf     journal (arxiv:1102.5046)

• Influence and Dynamic Behavior in Random Boolean Networks
C. Seshadhri, Yevgeniy Vorobeychik, Jackson R. Mayo, Robert C. Armstrong, and Joseph R. Ruthruff
Physical Review Letters 2011
abstract     journal (arxiv:1107.3792)

• Blackbox Identity Testing for Bounded Top Fanin Depth-3 Circuits: the Field doesn't matter
Nitin Saxena and C. Seshadhri
Symposium on Theory of Computing (STOC) 2011 (Invited to special issue)
SIAM Journal on Computing 2012
abstract     conf     ECCC TR10-167     journal

• Combinatorial Approximation Algorithms for MaxCut using Random Walks
Satyen Kale and C. Seshadhri
Innovations in Computer Science (ICS) 2010
abstract     conf     arxiv:1008.3938

• Is Submodularity Testable?
C. Seshadhri and Jan Vondrak
Innovations in Computer Science (ICS) 2010
Algorithmica 2012
abstract     conf     arxiv:1008.0831     journal

• Estimating the Longest Increasing Sequence in Polylogarithmic Time
Michael Saks and C. Seshadhri
Foundations of Computer Science (FOCS) 2010
abstract     conf     arXiv:1308.0626

• From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits
Nitin Saxena and C. Seshadhri
Foundations of Computer Science (FOCS) 2010
Journal of the ACM 2013
abstract     conf     ECCC TR10-013     journal

• Self-Improving Algorithms for Convex Hulls
Ken Clarkson, Wolfgang Mulzer, and C. Seshadhri
Symposium on Discrete Algorithms (SODA) 2010
(The conference version has a fatal flaw. The journal version fixes the problem, but gets a suboptimal result. This is merged with the self-improving maxima result, so check the link there for the full version.)
abstract   conf

• Efficient Learning Algorithms for Changing Environments
Elad Hazan and C. Seshadhri
International Conference on Machine Learning (ICML) 2009
abstract   ECCC TR07-088

• An Almost Optimal Rank Bound for Depth-3 Identities
Nitin Saxena and C. Seshadhri
Conference on Computational Complexity (CCC) 2009
SIAM Journal on Computing 2011
abstract   conf   ECCC TR08-108   journal

• Noise Tolerance of Expanders and Sublinear Expander Reconstruction
Satyen Kale, Yuval Peres, and C. Seshadhri
Foundations of Computer Science (FOCS) 2008
SIAM Journal on Computing 2013
abstract   conf   journal

• Testing Expansion in Bounded Degree Graphs
Satyen Kale and C. Seshadhri
International Colloquium on Automata, Languages and Programming (ICALP) 2008
SIAM Journal on Computing 2011
abstract   conf   ECCC TR07-076   journal

• Self-Improving Algorithms for Delaunay Triangulations
Ken Clarkson and C. Seshadhri
Symposium on Computational Geometry (SoCG) 2008
Full version in paper "Self-improving algorithms"
abstract   conf   full (arXiv:0907.0884)

• Local Monotonicity Reconstruction
Michael Saks and C. Seshadhri
Symposium on Discrete Algorithms (SODA) 2008 (Version titled "Parallel Monotonicity Reconstruction")
SIAM Journal on Computing 2010
abstract   conf   journal

• Online Geometric Reconstruction
Bernard Chazelle and C. Seshadhri
Symposium on Computational Geometry 2006
Journal of the ACM 2011
abstract   conf   journal

• Self-Improving Algorithms
Nir Ailon, Bernard Chazelle, Ding Liu, and C. Seshadhri
Symposium on Discrete Algorithms 2006
Nir Ailon, Bernard Chazelle, Ken Clarkson, Ding Liu, Wolfgang Mulzer, and C. Seshadhri
SIAM Journal on Computing 2011
abstract   journal

• RAM Simulation of BGS Model of Abstract State Machines
C. Seshadhri, Anil Seth, and Somenath Biswas
Abstract State Machines (ASM) 2005
abstract   full

• Property-Preserving Data Reconstruction
Nir Ailon, Bernard Chazelle, Ding Liu, and C. Seshadhri
International Symposium on Algorithms and Computation (ISAAC) 2004
Algorithmica 2008
abstract   journal

• Estimating the Distance to a Monotone Function
Nir Ailon, Bernard Chazelle, Ding Liu, and C. Seshadhri
International Workshop on Randomization and Computation (RANDOM) 2004
Random Structures and Algorithms 2007
abstract   journal