BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Gregory Schwartzman

Gregory Schwartzman appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsDistributed, Parallel, and Cluster ComputingMachine Learning

Catalog footprint

What is connected

7works
3topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

7 published item(s)

preprint2022arXiv

Fully Polynomial-Time Distributed Computation in Low-Treewidth Graphs

We consider global problems, i.e. problems that take at least diameter time, even when the bandwidth is not restricted. We show that all problems considered admit efficient solutions in low-treewidth graphs. By ``efficient'' we mean that the running time has polynomial dependence on the treewidth, a linear dependence on the diameter (which is unavoidable), and only a polylogarithmic dependence on $n$, the number of nodes in the graph. We present the algorithms solving the following problems in the CONGEST model which all attain $\tilde{O(τ^{O(1)}D)}$-round complexity (where $τ$ and $D$ denote the treewidth and diameter of the graph, respectively): (1) Exact single-source shortest paths (actually, the more general problem of computing a distance labeling scheme) for weighted and directed graphs, (2) exact bipartite unweighted maximum matching, and (3) the weighted girth for both directed and undirected graphs. We derive all of our results using a single unified framework, which consists of two novel technical ingredients, The first is a fully polynomial-time distributed tree decomposition algorithm, which outputs a decomposition of width $O(τ^2\log n)$ in $\tilde{O}(τ^{O(1)}D)$ rounds (where $n$ is the number of nodes in the graph). The second ingredient, and the technical highlight of this paper, is the novel concept of a \emph{stateful walk constraint}, which naturally defines a set of feasible walks in the input graph based on their local properties (e.g., augmenting paths). Given a stateful walk constraint, the constrained version of the shortest paths problem (or distance labeling) requires the algorithm to output the shortest \emph{constrained} walk (or its distance) for a given source and sink vertices. We show that this problem can be efficiently solved in the CONGEST model by reducing it to an \emph{unconstrained} version of the problem.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

SGD Through the Lens of Kolmogorov Complexity

We prove that stochastic gradient descent (SGD) finds a solution that achieves $(1-ε)$ classification accuracy on the entire dataset. We do so under two main assumptions: (1. Local progress) The model accuracy improves on average over batches. (2. Models compute simple functions) The function computed by the model is simple (has low Kolmogorov complexity). It is sufficient that these assumptions hold only for a tiny fraction of the epochs. Intuitively, the above means that intermittent local progress of SGD implies global progress. Assumption 2 trivially holds for underparameterized models, hence, our work gives the first convergence guarantee for general, underparameterized models. Furthermore, this is the first result which is completely model agnostic - we do not require the model to have any specific architecture or activation function, it may not even be a neural network. Our analysis makes use of the entropy compression method, which was first introduced by Moser and Tardos in the context of the Lovász local lemma.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Finding Subgraphs in Highly Dynamic Networks

In this paper we consider the fundamental problem of finding subgraphs in highly dynamic distributed networks - networks which allow an arbitrary number of links to be inserted / deleted per round. We show that the problems of $k$-clique membership listing (for any $k\geq 3$), 4-cycle listing and 5-cycle listing can be deterministically solved in $O(1)$-amortized round complexity, even with limited logarithmic-sized messages. To achieve $k$-clique membership listing we introduce a very useful combinatorial structure which we name the robust $2$-hop neighborhood. This is a subset of the 2-hop neighborhood of a node, and we prove that it can be maintained in highly dynamic networks in $O(1)$-amortized rounds. We also show that maintaining the actual 2-hop neighborhood of a node requires near linear amortized time, showing the necessity of our definition. For $4$-cycle and $5$-cycle listing, we need edges within hop distance 3, for which we similarly define the robust $3$-hop neighborhood and prove it can be maintained in highly dynamic networks in $O(1)$-amortized rounds. We complement the above with several impossibility results. We show that membership listing of any other graph on $k\geq 3$ nodes except $k$-clique requires an almost linear number of amortized communication rounds. We also show that $k$-cycle listing for $k\geq 6$ requires $Ω(\sqrt{n} / \log n)$ amortized rounds. This, combined with our upper bounds, paints a detailed picture of the complexity landscape for ultra fast graph finding algorithms in this highly dynamic environment.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Improved Distributed Approximations for Maximum Independent Set

We present improved results for approximating maximum-weight independent set ($\MaxIS$) in the CONGEST and LOCAL models of distributed computing. Given an input graph, let $n$ and $Δ$ be the number of nodes and maximum degree, respectively, and let $\MIS(n,Δ)$ be the the running time of finding a \emph{maximal} independent set ($\MIS$) in the CONGEST model. Bar-Yehuda et al. [PODC 2017] showed that there is an algorithm in the CONGEST model that finds a $Δ$-approximation for $\MaxIS$ in $O(\MIS(n,Δ)\log W)$ rounds, where $W$ is the maximum weight of a node in the graph, which can be as high as $\poly (n)$. Whether their algorithm is deterministic or randomized depends on the $\MIS$ algorithm that is used as a black-box. Our main result in this work is a randomized $(\poly(\log\log n)/ε)$-round algorithm that finds, with high probability, a $(1+ε)Δ$-approximation for $\MaxIS$ in the CONGEST model. That is, by sacrificing only a tiny fraction of the approximation guarantee, we achieve an \emph{exponential} speed-up in the running time over the previous best known result. Due to a lower bound of $Ω(\sqrt{\log n/\log \log n})$ that was given by Kuhn, Moscibroda and Wattenhofer [JACM, 2016] on the number of rounds for any (possibly randomized) algorithm that finds a maximal independent set (even in the LOCAL model) this result implies that finding a $(1+ε)Δ$-approximation for $\MaxIS$ is exponentially easier than $\MIS$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Distributed $(2+ε)$-Approximation for Vertex Cover in $O(\logΔ/ε\log\logΔ)$ Rounds

We present a simple deterministic distributed $(2+ε)$-approximation algorithm for minimum weight vertex cover, which completes in $O(\logΔ/ε\log\logΔ)$ rounds, where $Δ$ is the maximum degree in the graph, for any $ε>0$ which is at most $O(1)$. For a constant $ε$, this implies a constant approximation in $O(\logΔ/\log\logΔ)$ rounds, which contradicts the lower bound of [KMW10].

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Derandomizing Local Distributed Algorithms under Bandwidth Restrictions

This paper addresses the cornerstone family of \emph{local problems} in distributed computing, and investigates the curious gap between randomized and deterministic solutions under bandwidth restrictions. Our main contribution is in providing tools for derandomizing solutions to local problems, when the $n$ nodes can only send $O(\log n)$-bit messages in each round of communication. We combine bounded independence, which we show to be sufficient for some algorithms, with the method of conditional expectations and with additional machinery, to obtain the following results. Our techniques give a deterministic maximal independent set (MIS) algorithm in the CONGEST model, where the communication graph is identical to the input graph, in $O(D\log^2 n)$ rounds, where $D$ is the diameter of the graph. The best known running time in terms of $n$ alone is $2^{O(\sqrt{\log n})}$, which is super-polylogarithmic, and requires large messages. For the CONGEST model, the only known previous solution is a coloring-based $O(Δ+ \log^* n)$-round algorithm, where $Δ$ is the maximal degree in the graph. On the way to obtaining the above, we show that in the \emph{Congested Clique} model, which allows all-to-all communication, there is a deterministic MIS algorithm that runs in $O(\log Δ\log n)$ rounds.%, where $Δ$ is the maximum degree. When $Δ=O(n^{1/3})$, the bound improves to $O(\log Δ)$ and holds also for $(Δ+1)$-coloring. In addition, we deterministically construct a $(2k-1)$-spanner with $O(kn^{1+1/k}\log n)$ edges in $O(k \log n)$ rounds. For comparison, in the more stringent CONGEST model, the best deterministic algorithm for constructing a $(2k-1)$-spanner with $O(kn^{1+1/k})$ edges runs in $O(n^{1-1/k})$ rounds.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Fast Distributed Algorithms for Testing Graph Properties

We initiate a thorough study of \emph{distributed property testing} -- producing algorithms for the approximation problems of property testing in the CONGEST model. In particular, for the so-called \emph{dense} testing model we emulate sequential tests for nearly all graph properties having $1$-sided tests, while in the \emph{sparse} and \emph{general} models we obtain faster tests for triangle-freeness and bipartiteness respectively. In most cases, aided by parallelism, the distributed algorithms have a much shorter running time as compared to their counterparts from the sequential querying model of traditional property testing. The simplest property testing algorithms allow a relatively smooth transitioning to the distributed model. For the more complex tasks we develop new machinery that is of independent interest. This includes a method for distributed maintenance of multiple random walks.

0 citations0 reviewsNo code linkedOpen access