Zobrazeno 1 - 10
of 61
pro vyhledávání: '"Lapinskas, John"'
In this paper we study a version of (non-Markovian) first passage percolation on graphs, where the transmission time between two connected vertices is non-iid, but increases by a penalty factor polynomial in their expected degrees. Based on the expon
Externí odkaz:
http://arxiv.org/abs/2309.11880
One-dependent first passage percolation is a spreading process on a graph where the transmission time through each edge depends on the direct surroundings of the edge. In particular, the classical iid transmission time $L_{xy}$ is multiplied by $(W_x
Externí odkaz:
http://arxiv.org/abs/2309.11840
We study a query model of computation in which an n-vertex k-hypergraph can be accessed only via its independence oracle or via its colourful independence oracle, and each oracle query may incur a cost depending on the size of the query. In each of t
Externí odkaz:
http://arxiv.org/abs/2211.03874
Autor:
Goldberg, Leslie Ann, Lapinskas, John
In contention resolution, multiple processors are trying to coordinate to send discrete messages through a shared channel with sharply limited communication. If two processors inadvertently send at the same time, the messages collide and are not tran
Externí odkaz:
http://arxiv.org/abs/2203.17144
Counting the independent sets of a graph is a classical #P-complete problem, even in the bipartite case. We give an exponential-time approximation scheme for this problem which is faster than the best known algorithm for the exact problem. The runnin
Externí odkaz:
http://arxiv.org/abs/2005.05070
We study the spread of information in finite and infinite inhomogeneous spatial random graphs. We assume that each edge has a transmission cost that is a product of an i.i.d. random variable L and a penalty factor: edges between vertices of expected
Externí odkaz:
http://arxiv.org/abs/2004.01149
In this paper, we design efficient algorithms to approximately count the number of edges of a given $k$-hypergraph, and to sample an approximately uniform random edge. The hypergraph is not given explicitly, and can be accessed only through its colou
Externí odkaz:
http://arxiv.org/abs/1907.04826
The Moran process is a random process that models the spread of genetic mutations through graphs. If the graph is connected, the process eventually reaches "fixation", where every vertex is a mutant, or "extinction", where no vertex is a mutant. Our
Externí odkaz:
http://arxiv.org/abs/1804.02293
Autor:
Farach-Colton, Gwendolyn, Farach-Colton, Martin, Goldberg, Leslie Ann, Komlos, Hanna, Lapinskas, John, Levi, Reut, Medina, Moti, Mosteiro, Miguel A.
Ranking functions such as PageRank assign numeric values (ranks) to nodes of graphs, most notably the web graph. Node rankings are an integral part of Internet search algorithms, since they can be used to order the results of queries. However, these
Externí odkaz:
http://arxiv.org/abs/1803.05001
Autor:
Dell, Holger, Lapinskas, John
In this paper, we introduce a general framework for fine-grained reductions of approximate counting problems to their decision versions. (Thus we use an oracle that decides whether any witness exists to multiplicatively approximate the number of witn
Externí odkaz:
http://arxiv.org/abs/1707.04609