55 citations · 62 across the 8 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2015★ 4 cited
ETH Hardness for Densest--Subgraph with Perfect Completeness
Mark Braverman, Young Kun Ko, Aviad Rubinstein +1
We show that, assuming the (deterministic) Exponential Time Hypothesis, distinguishing between a graph with an induced -clique and a graph in which all k-subgraphs have density…
cs.CC2015★ 1 cited
Information Complexity and the Quest for Interactive Compression (A Survey)
Omri Weinstein
Information complexity is the interactive analogue of Shannon's classical information theory. In recent years this field has emerged as a powerful tool for proving strong communica…