enter search term and/or author name
On the trade-off between network connectivity, round complexity, and communication complexity of reliable message transmission
Ashwinkumar Badanidiyuru, Arpita Patra, Ashish Choudhury, Kannan Srinathan, C. Pandu Rangan
Article No.: 22
Perfectly reliable message transmission (PRMT) is one of the fundamental problems in distributed computing. It allows a sender to reliably transmit a message to a receiver in an unreliable network, even in the presence of a computationally...
In this article we describe and analyze sublinear-time approximation algorithms for some optimization problems arising in machine learning, such as training linear classifiers and finding minimum enclosing balls. Our algorithms can be extended to...
The Lovász Local Lemma (LLL) is a powerful tool in probability theory to show the existence of combinatorial objects meeting a prescribed collection of “weakly dependent” criteria. We show that the LLL extends to a much more...
Approximating the partition function of the ferromagnetic Potts model
Leslie Ann Goldberg, Mark Jerrum
Article No.: 25
We provide evidence that it is computationally difficult to approximate the partition function of the ferromagnetic q-state Potts model when q > 2. Specifically, we show that the partition function is hard for the complexity class...
Fixed-point definability and polynomial time on graphs with excluded minors
Article No.: 27
We give a logical characterization of the polynomial-time properties of graphs embeddable in some surface. For every surface S, a property P of graphs embeddable in S is decidable in polynomial time if and only if it is definable in...