Zobrazeno 1 - 10
of 36
pro vyhledávání: '"Fischer, Orr"'
Contrastive learning is a highly successful technique for learning representations of data from labeled tuples, specifying the distance relations within the tuple. We study the sample complexity of contrastive learning, i.e. the minimum number of lab
Externí odkaz:
http://arxiv.org/abs/2312.00379
Autor:
Fischer, Orr, Parter, Merav
In their seminal PODC 1991 paper, Ostrovsky and Yung introduced the study of distributed computation in the presence of mobile adversaries which can dynamically appear throughout the network. Over the years, this setting has been studied mostly under
Externí odkaz:
http://arxiv.org/abs/2305.14300
Massively-parallel graph algorithms have received extensive attention over the past decade, with research focusing on three memory regimes: the superlinear regime, the near-linear regime, and the sublinear regime. The sublinear regime is the most des
Externí odkaz:
http://arxiv.org/abs/2302.14692
Autor:
Avdiukhin, Dmitrii, Yaroslavtsev, Grigory, Vainstein, Danny, Fischer, Orr, Das, Sauman, Mirza, Faraz
We study the problem of learning a hierarchical tree representation of data from labeled samples, taken from an arbitrary (and possibly adversarial) distribution. Consider a collection of data tuples labeled according to their hierarchical structure.
Externí odkaz:
http://arxiv.org/abs/2302.04492
The possibilities offered by quantum computing have drawn attention in the distributed computing community recently, with several breakthrough results showing quantum distributed algorithms that run faster than the fastest known classical counterpart
Externí odkaz:
http://arxiv.org/abs/2201.03000
Autor:
Censor-Hillel, Keren, Fischer, Orr, Gonen, Tzlil, Gall, François Le, Leitersdorf, Dean, Oshman, Rotem
In this paper we give fast distributed graph algorithms for detecting and listing small subgraphs, and for computing or approximating the girth. Our algorithms improve upon the state of the art by polynomial factors, and for girth, we obtain an const
Externí odkaz:
http://arxiv.org/abs/2101.07590
In the distributed subgraph-freeness problem, we are given a graph $H$, and asked to determine whether the network graph contains $H$ as a subgraph or not. Subgraph-freeness is an extremely local problem: if the network had no bandwidth constraints,
Externí odkaz:
http://arxiv.org/abs/1711.06920
In this paper we initiate the study of property testing in simultaneous and non-simultaneous multi-party communication complexity, focusing on testing triangle-freeness in graphs. We consider the $\textit{coordinator}$ model, where we have $k$ player
Externí odkaz:
http://arxiv.org/abs/1705.08438
In the subgraph-freeness problem, we are given a constant-size graph $H$, and wish to determine whether the network contains $H$ as a subgraph or not. The \emph{property-testing} relaxation of the problem only requires us to distinguish graphs that a
Externí odkaz:
http://arxiv.org/abs/1705.04033
Autor:
Brandt, Sebastian, Fischer, Orr, Hirvonen, Juho, Keller, Barbara, Lempiäinen, Tuomo, Rybicki, Joel, Suomela, Jukka, Uitto, Jara
We show that any randomised Monte Carlo distributed algorithm for the Lov\'asz local lemma requires $\Omega(\log \log n)$ communication rounds, assuming that it finds a correct assignment with high probability. Our result holds even in the special ca
Externí odkaz:
http://arxiv.org/abs/1511.00900