# Seshadhri Comandur

According to our database

Collaborative distances:

^{1}, Seshadhri Comandur authored at least 116 papers between 2006 and 2020.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepage:

#### On csauthors.net:

## Bibliography

2020

Finding Cliques in Social Networks: A New Distribution-Free Model.

SIAM J. Comput., 2020

How to Count Triangles, without Seeing the Whole Graph.

CoRR, 2020

The impossibility of low rank representations for triangle-rich complex networks.

CoRR, 2020

Provably and Efficiently Approximating Near-cliques using the Turán Shadow: PEANUTS.

Proceedings of the WWW '20: The Web Conference 2020, Taipei, Taiwan, April 20-24, 2020, 2020

Efficiently Counting Vertex Orbits of All 5-vertex Subgraphs, by EVOKE.

Proceedings of the WSDM '20: The Thirteenth ACM International Conference on Web Search and Data Mining, 2020

The Power of Pivoting for Exact Clique Counting.

Proceedings of the WSDM '20: The Thirteenth ACM International Conference on Web Search and Data Mining, 2020

Faster sublinear approximation of the number of

*k*-cliques in low-arboricity graphs.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Domain Reduction for Monotonicity Testing: A

*o*(*d*) Tester for Boolean Functions in*d*-Dimensions.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

How the Degeneracy Helps for Triangle Counting in Graph Streams.

Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2020

Linear Time Subgraph Counting, Graph Degeneracy, and the Chasm at Size Six.

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

2019

Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection.

SIAM J. Discret. Math., 2019

andom walks and forbidden minors II: A $\poly(d\eps^{-1})$-query tester for minor-closed properties of bounded degree graphs.

Electronic Colloquium on Computational Complexity (ECCC), 2019

Random walks and forbidden minors II: A poly(dε

^{-1})-query tester for minor-closed properties of bounded-degree graphs.
CoRR, 2019

Random walks and forbidden minors II: a poly(

*d ε*^{-1})-query tester for minor-closed properties of bounded degree graphs.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

2018

Local Algorithms for Hierarchical Dense Subgraph Discovery.

Proc. VLDB Endow., 2018

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.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Adaptive Boolean Monotonicity Testing in Total Influence Time.

Electronic Colloquium on Computational Complexity (ECCC), 2018

Domain Reduction for Monotonicity Testing: A $o(d)$ Tester for Boolean Functions on Hypergrids.

Electronic Colloquium on Computational Complexity (ECCC), 2018

Finding forbidden minors in sublinear time: a n

^{1/2+o(1)}-query one-sided tester for minor closed properties on bounded degree graphs.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Faster sublinear approximations of k-cliques for low arboricity graphs.

CoRR, 2018

Fiding forbidden minors in sublinear time: a O(n

^{1/2 + o(1)})-query one-sided tester for minor closed properties on bounded degree graphs.
CoRR, 2018

Provable and Practical Approximations for the Degree Distribution using Sublinear Graph Samples.

Proceedings of the 2018 World Wide Web Conference on World Wide Web, 2018

On approximating the number of k-cliques in sublinear time.

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Finding Forbidden Minors in Sublinear Time: A n^1/2+o(1)-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs.

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

Nucleus Decompositions for Identifying Hierarchy of Dense Subgraphs.

ACM Trans. Web, 2017

Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties.

ACM Trans. Algorithms, 2017

Estimating the Longest Increasing Sequence in Polylogarithmic Time.

SIAM J. Comput., 2017

Approximately Counting Triangles in Sublinear Time.

SIAM J. Comput., 2017

A o(d) · polylog n Monotonicity Tester for Boolean Functions over the Hypergrid [n]

^{d}.
Electronic Colloquium on Computational Complexity (ECCC), 2017

A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube.

Electronic Colloquium on Computational Complexity (ECCC), 2017

Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps.

Electronic Colloquium on Computational Complexity (ECCC), 2017

Avoiding the Global Sort: A Faster Contour Tree Algorithm.

Discret. Comput. Geom., 2017

A $o(d) \cdot \text{polylog}~n$ Monotonicity Tester for Boolean Functions over the Hypergrid [n]

^{d}.
CoRR, 2017

Parallel Local Algorithms for Core, Truss, and Nucleus Decompositions.

CoRR, 2017

Directed closure measures for networks with reciprocity.

J. Complex Networks, 2017

When Hashes Met Wedges: A Distributed Algorithm for Finding High Similarity Vectors.

Proceedings of the 26th International Conference on World Wide Web, 2017

ESCAPE: Efficiently Counting All 5-Vertex Subgraphs.

Proceedings of the 26th International Conference on World Wide Web, 2017

A Fast and Provable Method for Estimating Clique Counts Using Turán's Theorem.

Proceedings of the 26th International Conference on World Wide Web, 2017

Accurate and Nearly Optimal Sublinear Approximations to Ulam Distance.

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Sublinear Time Estimation of Degree Distribution Moments: The Degeneracy Connection.

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

Local Reconstruction.

Encyclopedia of Algorithms, 2016

Trigger Detection for Adaptive Scientific Workflows Using Percentile Sampling.

SIAM J. Scientific Computing, 2016

Decompositions of Triangle-Dense Graphs.

SIAM J. Comput., 2016

An o(n) Monotonicity Tester for Boolean Functions over the Hypercube.

SIAM J. Comput., 2016

A Õ(n) Non-Adaptive Tester for Unateness.

Electronic Colloquium on Computational Complexity (ECCC), 2016

A $\widetilde{O}(n)$ Non-Adaptive Tester for Unateness.

CoRR, 2016

2015

A Space-Efficient Streaming Algorithm for Estimating Transitivity and Triangle Counts Using the Birthday Paradox.

ACM Trans. Knowl. Discov. Data, 2015

Why Do Simple Algorithms for Triangle Enumeration Work in the Real World?

Internet Math., 2015

A simpler sublinear algorithm for approximating the triangle count.

CoRR, 2015

A stopping criterion for Markov chains when generating independent random graphs.

J. Complex Networks, 2015

Finding the Hierarchy of Dense Subgraphs using Nucleus Decompositions.

Proceedings of the 24th International Conference on World Wide Web, 2015

Path Sampling: A Fast and Provable Method for Estimating 4-Vertex Subgraph Counts.

Proceedings of the 24th International Conference on World Wide Web, 2015

Catching the Head, Tail, and Everything in Between: A Streaming Algorithm for the Degree Distribution.

Proceedings of the 2015 IEEE International Conference on Data Mining, 2015

Diamond Sampling for Approximate Maximum All-Pairs Dot-Product (MAD) Search.

Proceedings of the 2015 IEEE International Conference on Data Mining, 2015

Counting triangles in real-world graph streams: Dealing with repeated edges and time windows.

Proceedings of the 49th Asilomar Conference on Signals, Systems and Computers, 2015

Sublinear Algorithms for Extreme-Scale Data Analysis.

Proceedings of the Green in Software Engineering, 2015

2014

An Optimal Lower Bound for Monotonicity Testing over Hypergrids.

Theory Comput., 2014

Counting Triangles in Massive Graphs with MapReduce.

SIAM J. Scientific Computing, 2014

A Scalable Generative Graph Model with Community Structure.

SIAM J. Scientific Computing, 2014

Self-Improving Algorithms for Coordinatewise Maxima and Convex Hulls.

SIAM J. Comput., 2014

Wedge sampling for computing clustering coefficients and triangle counts on large graphs.

Statistical Analysis and Data Mining, 2014

Characterizing short-term stability for Boolean networks over any distribution of transfer functions.

CoRR, 2014

A Mountaintop View Requires Minimal Sorting: A Faster Contour Tree Algorithm.

CoRR, 2014

Is Submodularity Testable?

Algorithmica, 2014

FAST-PPR: scaling personalized pagerank estimation for large graphs.

Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2014

2013

Noise Tolerance of Expanders and Sublinear Expansion Reconstruction.

SIAM J. Comput., 2013

An in-depth analysis of stochastic Kronecker graphs.

J. ACM, 2013

From sylvester-gallai configurations to rank bounds: Improved blackbox identity test for depth-3 circuits.

J. ACM, 2013

A o(n) monotonicity tester for Boolean functions over the hypercube.

Electronic Colloquium on Computational Complexity (ECCC), 2013

The importance of directed triangles with reciprocity: patterns and algorithms

CoRR, 2013

When a Graph is not so Simple: Counting Triangles in Multigraph Streams.

CoRR, 2013

Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids.

Proceedings of the Symposium on Theory of Computing Conference, 2013

Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance.

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Triadic Measures on Graphs: The Power of Wedge Sampling.

Proceedings of the 13th SIAM International Conference on Data Mining, 2013

A scalable null model for directed graphs matching all degree distributions: In, out, and reciprocal.

Proceedings of the 2nd IEEE Network Science Workshop, 2013

A provably-robust sampling method for generating colormaps of large data.

Proceedings of the IEEE Symposium on Large-Scale Data Analysis and Visualization, 2013

A space efficient streaming algorithm for triangle counting using the birthday paradox.

Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2013

2012

Finding Cycles and Trees in Sublinear Time.

Electronic Colloquium on Computational Complexity (ECCC), 2012

Optimal bounds for monotonicity and Lipschitz testing over the hypercube.

Electronic Colloquium on Computational Complexity (ECCC), 2012

From the Birthday Paradox to a Practical Sublinear Space Streaming Algorithm for Triangle Counting

CoRR, 2012

Self-improving Algorithms for Coordinate-Wise Maxima and Convex Hulls

CoRR, 2012

A scalable directed graph model with reciprocal edges

CoRR, 2012

Degree Relations of Triangles in Real-world Networks and Models

CoRR, 2012

Fast Triangle Counting through Wedge Sampling

CoRR, 2012

Are We There Yet? When to Stop a Markov Chain while Generating Random Graphs.

Proceedings of the Algorithms and Models for the Web Graph - 9th International Workshop, 2012

The Similarity Between Stochastic Kronecker and Chung-Lu Graph Models.

Proceedings of the Twelfth SIAM International Conference on Data Mining, 2012

Vertex neighborhoods, low conductance cuts, and good seeds for local community methods.

Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2012

Self-improving algorithms for coordinate-wise maxima.

Proceedings of the Symposuim on Computational Geometry 2012, 2012

Degree relations of triangles in real-world networks and graph models.

Proceedings of the 21st ACM International Conference on Information and Knowledge Management, 2012

2011

An Expansion Tester for Bounded Degree Graphs.

SIAM J. Comput., 2011

Self-Improving Algorithms.

SIAM J. Comput., 2011

Online geometric reconstruction.

J. ACM, 2011

Community structure and scale-free collections of Erdös-Rényi graphs

CoRR, 2011

Neighborhoods are good communities

CoRR, 2011

Influence and Dynamic Behavior in Random Boolean Networks

CoRR, 2011

A Hitchhiker's Guide to Choosing Parameters of Stochastic Kronecker Graphs

CoRR, 2011

Combinatorial Approximation Algorithms for MaxCut using Random Walks.

Proceedings of the Innovations in Computer Science, 2011

An In-depth Study of Stochastic Kronecker Graphs.

Proceedings of the 11th IEEE International Conference on Data Mining, 2011

2010

Local Monotonicity Reconstruction.

SIAM J. Comput., 2010

Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter.

Electronic Colloquium on Computational Complexity (ECCC), 2010

From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits.

Electronic Colloquium on Computational Complexity (ECCC), 2010

Self-improving Algorithms for Convex Hulls.

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Local Property Reconstruction and Monotonicity.

Proceedings of the Property Testing - Current Research and Surveys, 2010

2009

Testing cycle-freeness: Finding a certificate

CoRR, 2009

Efficient learning algorithms for changing environments.

Proceedings of the 26th Annual International Conference on Machine Learning, 2009

2008

An Almost Optimal Rank Bound for Depth-3 Identities.

Electronic Colloquium on Computational Complexity (ECCC), 2008

Property-Preserving Data Reconstruction.

Algorithmica, 2008

Parallel monotonicity reconstruction.

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Noise Tolerance of Expanders and Sublinear Expander Reconstruction.

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Self-improving algorithms for delaunay triangulations.

Proceedings of the 24th ACM Symposium on Computational Geometry, 2008

2007

Estimating the distance to a monotone function.

Random Struct. Algorithms, 2007

RAM Simulation of BGS Model of Abstract-state Machines.

Fundam. Inform., 2007

Testing Expansion in Bounded Degree Graphs.

Electronic Colloquium on Computational Complexity (ECCC), 2007

Adaptive Algorithms for Online Decision Problems.

Electronic Colloquium on Computational Complexity (ECCC), 2007

2006

Self-improving algorithms.

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006