Testing cluster structure of graphs
- Submitting institution
-
The University of Warwick
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 5902
- Type
- E - Conference contribution
- DOI
-
10.1145/2746539.2746618
- Title of conference / published proceedings
- Forty-Seventh Annual ACM on Symposium on Theory of Computing
- First page
- 723
- Volume
- -
- Issue
- -
- ISSN
- -
- Open access status
- -
- Month of publication
- June
- Year of publication
- 2015
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
2
- Research group(s)
-
T - Theory and Foundations
- Citation count
- 12
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This paper was published in one of the two strongest theoretical computer science conferences. A follow-up work appeared at FOCS'18 (by researchers from EPFL, University of Pennsylvania, and Microsoft Research), and cited this paper as "an ingenious sublinear time algorithm for testing k-clusterability". Some further extensions have been studied and resolved by researchers from MIT, and then at SODA'20 and at SODA'21. This research was partly funded by EPSRC and ERC, and has been presented at several international conferences, workshops and seminars, including the prestigious HALG'16 conference and workshops at Bertinoro, Rome, Moscow, Warsaw, IBM.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -