On triangle estimation using tripartite independent set queries
type: Item
instance of: scholarly article
title: On triangle estimation using tripartite independent set queries
author: Anup Bhattacharya
author: Arijit Bishnu
author: Arijit Ghosh
author: Gopinath Mishra
published in: Theory of Computing Systems
publication date: 2021-12-18T00:00:00Z
full work available at URL: https://arxiv.org/abs/1808.00691
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/11515/
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 7449499
zbMATH Keywords: triangle estimation
zbMATH Keywords: query complexity
zbMATH Keywords: sublinear algorithm
MaRDI profile type: Publication
OpenAlex ID: W3166345458
cites work: Finding and counting given length cycles
cites work: Q5091015
cites work: Q4993304
cites work: Listing Triangles
cites work: Q4828992
cites work: A second look at counting triangles in graph streams (corrected)
cites work: Optimal query complexity bounds for finding graphs
cites work: Fine-grained reductions from approximate counting to decision
cites work: Approximately counting and sampling small witnesses using a colourful decision oracle
cites work: Concentration of measure for the analysis of randomized algorithms.
cites work: Approximately Counting Triangles in Sublinear Time
cites work: On approximating the number of k-cliques in sublinear time
cites work: On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
cites work: Approximating average parameters of graphs
cites work: Counting Stars and Other Small Subgraphs in Sublinear-Time
cites work: Finding a Minimum Circuit in a Graph
cites work: Large deviations for sums of partly dependent random variables
cites work: Computing and Combinatorics
cites work: Counting Arbitrary Subgraphs in Data Streams
cites work: A Hybrid Sampling Scheme for Triangle Counting
cites work: Q4993305
cites work: The Power of an Example
cites work: On Approximation Algorithms for # P
DOI: 10.1007/S00224-021-10043-Y
description: scientific article; zbMATH DE number 7449499