Source author record

Daniel Reichman

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics math.CO Data Structures and Algorithms Computational Complexity Computer Science and Game Theory Information Theory Machine Learning math.IT math.PR math.ST Neural and Evolutionary Computing Statistics Theory

Catalog footprint

Research overview

14works

12topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

The Computational Complexity of Counting Linear Regions in ReLU Neural Networks

An established measure of the expressive power of a given ReLU neural network is the number of linear regions into which it partitions the input space. There exist many different, non-equivalent definitions of what a linear region actually is. We systematically assess which papers use which definitions and discuss how they relate to each other. We then analyze the computational complexity of counting the number of such regions for the various definitions. Generally, this turns out to be an intractable problem. We prove NP- and #P-hardness results already for networks with one hidden layer and strong hardness of approximation results for two or more hidden layers. Finally, on the algorithmic side, we demonstrate that counting linear regions can at least be achieved in polynomial space for some common definitions.

preprint2023arXiv

The Learning and Communication Complexity of Subsequence Containment

We consider the learning and communication complexity of subsequence containment. In the learning problem, we seek to learn a classifier that positively labels a binary string $x$ if it contains a fixed binary string $y$ as a subsequence. In the communication problem, $x$ and $y$ are partitioned between two players, Alice and Bob, who wish to determine if $x$ contains $y$ as a subsequence using a minimal amount of communication. We devise asymptotically tight bounds for the sample complexity (VC dimension) of the learning problem and the communication complexity of the communication problem. Our results illustrate that the sample complexity of our learning problem can be considerably larger when the subsequence occurs in non-contiguous locations.

preprint2022arXiv

Local treewidth of random and noisy graphs with applications to stopping contagion in networks

We study the notion of local treewidth in sparse random graphs: the maximum treewidth over all $k$ -vertex subgraphs of an $n$ -vertex graph. When $k$ is not too large, we give nearly tight bounds for this local treewidth parameter; we also derive tight bounds for the local treewidth of noisy trees, trees where every non-edge is added independently with small probability. We apply our upper bounds on the local treewidth to obtain fixed parameter tractable algorithms (on random graphs and noisy trees) for edge-removal problems centered around containing a contagious process evolving over a network. In these problems, our main parameter of study is $k$ , the number of initially ``infected'' vertices in the network. For the random graph models we consider and a certain range of parameters the running time of our algorithms on $n$ -vertex graphs is $2^{o(k)}\textrm{poly}(n)$ , improving upon the $2^{Ω(k)}\textrm{poly}(n)$ performance of the best-known algorithms designed for worst-case instances of these edge deletion problems.

preprint2020arXiv

A note on the largest induced matching in graphs avoiding a fixed bipartite graph

We give a simple proof that every $n$ -vertex graph $d$ -regular graph that does not contain a fixed bipartite graph as a subgraph has an induced matching of size $Ω((n/d)(\log d))$ .

preprint2016arXiv

Contagious Sets in Random Graphs

preprint2015arXiv

Contagious Sets in Dense Graphs

We study the activation process in undirected graphs known as bootstrap percolation: a vertex is active either if it belongs to a set of initially activated vertices or if at some point it had at least r active neighbors, for a threshold r that is identical for all vertices. A contagious set is a vertex set whose activation results with the entire graph being active. Let m(G,r) be the size of a smallest contagious set in a graph G on n vertices. We examine density conditions that ensure m(G,r) = r for all r >= 2. With respect to the minimum degree, we prove that such a smallest possible contagious set is guaranteed to exist if and only if G has minimum degree at least (k-1)/k * n. Moreover, we study the speed with which the activation spreads and provide tight upper bounds on the number of rounds it takes until all nodes are activated in such a graph. We also investigate what average degree asserts the existence of small contagious sets. For n >= k >= r, we denote by M(n,k,r) the maximum number of edges in an n-vertex graph G satisfying m(G,r)>k. We determine the precise value of M(n,k,2) and M(n,k,k), assuming that n is sufficiently large compared to k.

preprint2015arXiv

On Percolation and $NP$ -Hardness

We consider the robustness of computational hardness of problems whose input is obtained by applying independent random deletions to worst-case instances. For some classical $NP$ -hard problems on graphs, such as Coloring, Vertex-Cover, and Hamiltonicity, we examine the complexity of these problems when edges (or vertices) of an arbitrary graph are deleted independently with probability $1-p > 0$ . We prove that for $n$ -vertex graphs, these problems remain as hard as in the worst-case, as long as $p > \frac{1}{n^{1-ε}}$ for arbitrary $ε\in (0,1)$ , unless $NP \subseteq BPP$ . We also prove hardness results for Constraint Satisfaction Problems, where random deletions are applied to clauses or variables, as well as the Subset-Sum problem, where items of a given instance are deleted at random.

preprint2015arXiv

On the Non-Existence of Nash Equilibrium in Games with Resource-Bounded Players

We consider sequences of games $\mathcal{G}=\{G_1,G_2,\ldots\}$ where, for all $n$ , $G_n$ has the same set of players. Such sequences arise in the analysis of running time of players in games, in electronic money systems such as Bitcoin and in cryptographic protocols. Assuming that one-way functions exist, we prove that there is a sequence of 2-player zero-sum Bayesian games $\mathcal{G}$ such that, for all $n$ , the size of every action in $G_n$ is polynomial in $n$ , the utility function is polynomial computable in $n$ , and yet there is no polynomial-time Nash equilibrium, where we use a notion of Nash equilibrium that is tailored to sequences of games. We also demonstrate that Nash equilibrium may not exist when considering players that are constrained to perform at most $T$ computational steps in each of the games $\{G_i\}_{i=1}^{\infty}$ . These examples may shed light on competitive settings where the availability of more running time or faster algorithms lead to a "computational arms race", precluding the existence of equilibrium. They also point to inherent limitations of concepts such "best response" and Nash equilibrium in games with resource-bounded players.

preprint2015arXiv

Smoothed analysis on connected graphs

The main paradigm of smoothed analysis on graphs suggests that for any large graph $G$ in a certain class of graphs, perturbing slightly the edges of $G$ at random (usually adding few random edges to $G$ ) typically results in a graph having much "nicer" properties. In this work we study smoothed analysis on trees or, equivalently, on connected graphs. Given an $n$ -vertex connected graph $G$ , form a random supergraph $G^*$ of $G$ by turning every pair of vertices of $G$ into an edge with probability $\fracε{n}$ , where $ε$ is a small positive constant. This perturbation model has been studied previously in several contexts, including smoothed analysis, small world networks, and combinatorics. Connected graphs can be bad expanders, can have very large diameter, and possibly contain no long paths. In contrast, we show that if $G$ is an $n$ -vertex connected graph then typically $G^*$ has edge expansion $Ω(\frac{1}{\log n})$ , diameter $O(\log n)$ , vertex expansion $Ω(\frac{1}{\log n})$ , and contains a path of length $Ω(n)$ , where for the last two properties we additionally assume that $G$ has bounded maximum degree. Moreover, we show that if $G$ has bounded degeneracy, then typically the mixing time of the lazy random walk on $G^*$ is $O(\log^2 n)$ . All these results are asymptotically tight.

preprint2014arXiv

Contagious Sets in Expanders

We consider the following activation process in undirected graphs: a vertex is active either if it belongs to a set of initially activated vertices or if at some point it has at least $r$ active neighbors, where $r>1$ is the activation threshold. A \emph{contagious set} is a set whose activation results with the entire graph being active. Given a graph $G$ , let $m(G,r)$ be the minimal size of a contagious set. Computing $m(G,r)$ is NP-hard. It is known that for every $d$ -regular or nearly $d$ -regular graph on $n$ vertices, $m(G,r) \le O(\frac{nr}{d})$ . We consider such graphs that additionally have expansion properties, parameterized by the spectral gap and/or the girth of the graphs. The general flavor of our results is that sufficiently strong expansion (e.g., $λ(G)=O(\sqrt{d})$ , or girth $Ω(\log \log d)$ ) implies that $m(G,2) \le O(\frac{n}{d^2})$ (and more generally, $m(G,r) \le O(\frac{n}{d^{r/(r-1)}})$ ). Significantly weaker expansion properties suffice in order to imply that $m(G,2)\le O(\frac{n \log d}{d^2})$ . For example, we show this for graphs of girth at least~7, and for graphs with $λ(G)<(1-ε)d$ , provided the graph has no 4-cycles. Nearly $d$ -regular expander graphs can be obtained by considering the binomial random graph $G(n,p)$ with $p \simeq \frac{d}{n}$ and $d > \log n$ . For such graphs we prove that $Ω(\frac{n}{d^2 \log d}) \le m(G,2) \le O(\frac{n\log\log d}{d^2\log d})$ almost surely. Our results are algorithmic, entailing simple and efficient algorithms for selecting contagious sets.

preprint2014arXiv

On the limitation of spectral methods: From the Gaussian hidden clique problem to rank one perturbations of Gaussian tensors

We consider the following detection problem: given a realization of a symmetric matrix ${\mathbf{X}}$ of dimension $n$ , distinguish between the hypothesis that all upper triangular variables are i.i.d. Gaussians variables with mean 0 and variance $1$ and the hypothesis where ${\mathbf{X}}$ is the sum of such matrix and an independent rank-one perturbation. This setup applies to the situation where under the alternative, there is a planted principal submatrix ${\mathbf{B}}$ of size $L$ for which all upper triangular variables are i.i.d. Gaussians with mean $1$ and variance $1$ , whereas all other upper triangular elements of ${\mathbf{X}}$ not in ${\mathbf{B}}$ are i.i.d. Gaussians variables with mean 0 and variance $1$ . We refer to this as the `Gaussian hidden clique problem.' When $L=(1+ε)\sqrt{n}$ ( $ε>0$ ), it is possible to solve this detection problem with probability $1-o_n(1)$ by computing the spectrum of ${\mathbf{X}}$ and considering the largest eigenvalue of ${\mathbf{X}}$ . We prove that this condition is tight in the following sense: when $L<(1-ε)\sqrt{n}$ no algorithm that examines only the eigenvalues of ${\mathbf{X}}$ can detect the existence of a hidden Gaussian clique, with error probability vanishing as $n\to\infty$ . We prove this result as an immediate consequence of a more general result on rank-one perturbations of $k$ -dimensional Gaussian tensors. In this context we establish a lower bound on the critical signal-to-noise ratio below which a rank-one signal cannot be detected.

preprint2011arXiv

Recoverable Values for Independent Sets

The notion of {\em recoverable value} was advocated in work of Feige, Immorlica, Mirrokni and Nazerzadeh [Approx 2009] as a measure of quality for approximation algorithms. There this concept was applied to facility location problems. In the current work we apply a similar framework to the maximum independent set problem (MIS). We say that an approximation algorithm has {\em recoverable value} $ρ$ , if for every graph it recovers an independent set of size at least $\max_I \sum_{v\in I} \min[1,ρ/(d(v) + 1)]$ , where $d(v)$ is the degree of vertex $v$ , and $I$ ranges over all independent sets in $G$ . Hence, in a sense, from every vertex $v$ in the maximum independent set the algorithm recovers a value of at least $ρ/(d_v + 1)$ towards the solution. This quality measure is most effective in graphs in which the maximum independent set is composed of low degree vertices. It easily follows from known results that some simple algorithms for MIS ensure $ρ\ge 1$ . We design a new randomized algorithm for MIS that ensures an expected recoverable value of at least $ρ\ge 7/3$ . In addition, we show that approximating MIS in graphs with a given $k$ -coloring within a ratio larger than $2/k$ is unique games hard. This rules out a natural approach for obtaining $ρ\ge 2$ .

preprint2011arXiv

Tight Approximation of Image Matching

In this work we consider the {\em image matching} problem for two grayscale $n \times n$ images, $M_1$ and $M_2$ (where pixel values range from 0 to 1). Our goal is to find an affine transformation $T$ that maps pixels from $M_1$ to pixels in $M_2$ so that the differences over pixels $p$ between $M_1(p)$ and $M_2(T(p))$ is minimized. Our focus here is on sublinear algorithms that give an approximate result for this problem, that is, we wish to perform this task while querying as few pixels from both images as possible, and give a transformation that comes close to minimizing the difference. We give an algorithm for the image matching problem that returns a transformation $T$ which minimizes the sum of differences (normalized by $n^2$ ) up to an additive error of $ε$ and performs $\tilde{O}(n/ε^2)$ queries. We give a corresponding lower bound of $Ω(n)$ queries showing that this is the best possible result in the general case (with respect to $n$ and up to low order terms). In addition, we give a significantly better algorithm for a natural family of images, namely, smooth images. We consider an image smooth when the total difference between neighboring pixels is O(n). For such images we provide an approximation of the distance between the images to within an additive error of $ε$ using a number of queries depending polynomially on $1/ε$ and not on $n$ . To do this we first consider the image matching problem for 2 and 3-dimensional {\em binary} images, and then reduce the grayscale image matching problem to the 3-dimensional binary case.

preprint2010arXiv

Influence is a Matter of Degree: New Algorithms for Activation Problems

We consider the target set selection problem. In this problem, a vertex is active either if it belongs to a set of initially activated vertices or if at some point it has at least $k$ active neighbors ( $k$ is identical for all vertices of the graph). Our goal is to find a set of minimum size whose activation will result with the entire graph being activated. Call such a set \emph{contagious}. We prove that if $G=(V,E)$ is an undirected graph, the size of a contagious set is bounded by $\sum_{v\in V}{\min \{1,\frac{k}{d(v)+1}\}}$ (where $d(v)$ is the degree of $v$ ). We present a simple and efficient algorithm that finds a contagious set that is not larger than the aforementioned bound and discuss algorithmic applications of this algorithm to finding contagious sets in dense graphs.

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.

Daniel Reichman

Research overview

Is this your work?

14 publications

The Computational Complexity of Counting Linear Regions in ReLU Neural Networks

The Learning and Communication Complexity of Subsequence Containment

Local treewidth of random and noisy graphs with applications to stopping contagion in networks

A note on the largest induced matching in graphs avoiding a fixed bipartite graph

Contagious Sets in Random Graphs

Contagious Sets in Dense Graphs

On Percolation and $NP$ -Hardness

On the Non-Existence of Nash Equilibrium in Games with Resource-Bounded Players

Smoothed analysis on connected graphs

Contagious Sets in Expanders

On the limitation of spectral methods: From the Gaussian hidden clique problem to rank one perturbations of Gaussian tensors

Recoverable Values for Independent Sets

Tight Approximation of Image Matching

Influence is a Matter of Degree: New Algorithms for Activation Problems

See the researcher in context

Building this map preview

Daniel Reichman

Research overview

Is this your work?

14 publications

The Computational Complexity of Counting Linear Regions in ReLU Neural Networks

The Learning and Communication Complexity of Subsequence Containment

Local treewidth of random and noisy graphs with applications to stopping contagion in networks

A note on the largest induced matching in graphs avoiding a fixed bipartite graph

Contagious Sets in Random Graphs

Contagious Sets in Dense Graphs

On Percolation and NPNPNP-Hardness

On the Non-Existence of Nash Equilibrium in Games with Resource-Bounded Players

Smoothed analysis on connected graphs

Contagious Sets in Expanders

On the limitation of spectral methods: From the Gaussian hidden clique problem to rank one perturbations of Gaussian tensors

Recoverable Values for Independent Sets

Tight Approximation of Image Matching

Influence is a Matter of Degree: New Algorithms for Activation Problems

See the researcher in context

Building this map preview

On Percolation and $NP$ -Hardness