Consider an algorithm performing a computation on a huge random object (for example a random graph or a "long" random walk). Is it necessary to generate the entire object prior to the computation, or is it possible to provide query access to the object and sample it incrementally "onthefly" (as requested by the algorithm)? Such an implementation should emulate the random object by answering queries in a manner consistent with an instance of the random object sampled from the true distribution (or close to it). This paradigm is useful when the algorithm is sublinear and thus, sampling the entire objectmore »
Realization Problems on Reachability Sequences
The classical ErdösGallai theorem kicked off the study ofgraph realizability by characterizing degree sequences. We extend this line of research by investigating realizability of directed acyclic graphs (DAGs)given both a local constraint via degree sequences and a global constraint via a sequence of reachability values (number of nodes reachable from a given node). We show that, without degree constraints, DAG reachability realization is solvable in linear time, whereas it is strongly NPcomplete given upper bounds on indegree or outdegree. After defining a suitable notion of bicriteria approximation based on consistency, we give two approximation algorithms achieving O(logn)reachability consistency and O(logn)degree consistency; the first, randomized, uses LP (Linear Program) rounding, while the second, deterministic, employs aksetpacking heuristic. We end with two conjectures that we hope motivate further study of realizability with reachability constraints.
 Award ID(s):
 1718286
 Publication Date:
 NSFPAR ID:
 10183166
 Journal Name:
 COCOON
 Sponsoring Org:
 National Science Foundation
More Like this


There has been an increasing interest in using neural networks in closedloop control systems to improve performance and reduce computational costs for online implementation. However, providing safety and stability guarantees for these systems is challenging due to the nonlinear and compositional structure of neural networks. In this paper, we propose a novel forward reachability analysis method for the safety verification of linear timevarying systems with neural networks in feedback interconnection. Our technical approach relies on abstracting the nonlinear activation functions by quadratic constraints, which leads to an outerapproximation of forward reachable sets of the closedloop system. We show that wemore »

The densest subgraph problem in a graph (\dsg), in the simplest form, is the following. Given an undirected graph $G=(V,E)$ find a subset $S \subseteq V$ of vertices that maximizes the ratio $E(S)/S$ where $E(S)$ is the set of edges with both endpoints in $S$. \dsg and several of its variants are wellstudied in theory and practice and have many applications in data mining and network analysis. In this paper we study fast algorithms and structural aspects of \dsg via the lens of \emph{supermodularity}. For this we consider the densest supermodular subset problem (\dssp): given a nonnegative supermodular function $f:more »

We consider the classical Minimum Crossing Number problem: given an nvertex graph G, compute a drawing of G in the plane, while minimizing the number of crossings between the images of its edges. This is a fundamental and extensively studied problem, whose approximability status is widely open. In all currently known approximation algorithms, the approximation factor depends polynomially on Δ – the maximum vertex degree in G. The best current approximation algorithm achieves an O(n1/2−· (Δ·logn))approximation, for a small fixed constant є, while the best negative result is APXhardness, leaving a large gap in our understanding of this basic problem.more »

Abstract We consider the problem of covering multiple submodular constraints. Given a finite ground set N , a weight function $$w: N \rightarrow \mathbb {R}_+$$ w : N → R + , r monotone submodular functions $$f_1,f_2,\ldots ,f_r$$ f 1 , f 2 , … , f r over N and requirements $$k_1,k_2,\ldots ,k_r$$ k 1 , k 2 , … , k r the goal is to find a minimum weight subset $$S \subseteq N$$ S ⊆ N such that $$f_i(S) \ge k_i$$ f i ( S ) ≥ k i for $$1 \le i \le r$$ 1 ≤more »