Author name cluster

Daniel Reichman

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

1 author row

TCS Journal 2025 Journal Article

Inoculation strategies for bounded degree graphs

Mason DiCicco
Henry Poskanzer
Daniel Reichman

We study the inoculation game, a game-theoretic abstraction of epidemic containment played on an undirected graph G: each player is associated with a node in G and can either acquire protection from a contagious process or risk infection. After decisions are made, an infection starts at a random node v and propagates through all unprotected nodes reachable from v. It is known that the price of anarchy (PoA) in n-node graphs can be as large as Θ ( n ). Our main result is a tight upper bound of O ( n Δ ) on the PoA, where Δ is the maximum degree of the graph. Indeed, we provide constructions of graphs with maximum degree Δ for which the PoA is Ω ( n Δ ). We also study additional factors that can reduce the PoA, such as higher thresholds for contagion and varying the costs of becoming infected vs. acquiring protection.

Details DOI

NeurIPS Conference 2025 Conference Paper

Protocols for Verifying Smooth Strategies in Bandits and Games

Miranda Christ
Daniel Reichman
Jonathan Shafer

We study protocols for verifying approximate optimality of strategies in multi-armed bandits and normal-form games. As the number of actions available to each player is often large, we seek protocols where the number of queries to the utility oracle is sublinear in the number of actions. We prove that such verification is possible for sufficiently smooth strategies that do not put too much probability mass on any specific action and provide protocols for verifying that a smooth policy for a multi-armed bandit is close to optimal. Our verification protocols require provably fewer arm queries than learning. Furthermore, we show how to use cryptographic tools to reduce the communication cost of our protocols. We complement our protocol by proving a nearly tight lower bound on the query complexity of verification in our settings. As an application, we use our bandit verification protocol to build a protocol for verifying approximate optimality of a strong smooth Nash equilibrium, with sublinear query complexity.

PDF Details

NeurIPS Conference 2025 Conference Paper

The Computational Complexity of Counting Linear Regions in ReLU Neural Networks

Moritz Stargalla
Christoph Hertrich
Daniel Reichman

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.

PDF Details

NeurIPS Conference 2022 Conference Paper

Size and depth of monotone neural networks: interpolation and approximation

Dan Mikulincer
Daniel Reichman

Monotone functions and data sets arise in a variety of applications. We study the interpolation problem for monotone data sets: The input is a monotone data set with $n$ points, and the goal is to find a size and depth efficient monotone neural network with \emph{non negative parameters} and threshold units that interpolates the data set. We show that there are monotone data sets that cannot be interpolated by a monotone network of depth $2$. On the other hand, we prove that for every monotone data set with $n$ points in $\mathbb{R}^d$, there exists an interpolating monotone network of depth $4$ and size $O(nd)$. Our interpolation result implies that every monotone function over $[0, 1]^d$ can be approximated arbitrarily well by a depth-4 monotone network, improving the previous best-known construction of depth $d+1$. Finally, building on results from Boolean circuit complexity, we show that the inductive bias of having positive parameters can lead to a super-polynomial blow-up in the number of neurons when approximating monotone functions.

PDF Details

NeurIPS Conference 2017 Conference Paper

A graph-theoretic approach to multitasking

Noga Alon
Daniel Reichman
Igor Shinkar
Tal Wagner
Sebastian Musslick
Jonathan Cohen
Tom Griffiths
Biswadip Dey

A key feature of neural network architectures is their ability to support the simultaneous interaction among large numbers of units in the learning and processing of representations. However, how the richness of such interactions trades off against the ability of a network to simultaneously carry out multiple independent processes -- a salient limitation in many domains of human cognition -- remains largely unexplored. In this paper we use a graph-theoretic analysis of network architecture to address this question, where tasks are represented as edges in a bipartite graph $G=(A \cup B, E)$. We define a new measure of multitasking capacity of such networks, based on the assumptions that tasks that \emph{need} to be multitasked rely on independent resources, i. e. , form a matching, and that tasks \emph{can} be performed without interference if they form an induced matching. Our main result is an inherent tradeoff between the multitasking capacity and the average degree of the network that holds \emph{regardless of the network architecture}. These results are also extended to networks of depth greater than $2$. On the positive side, we demonstrate that networks that are random-like (e. g. , locally sparse) can have desirable multitasking properties. Our results shed light into the parallel-processing limitations of neural systems and provide insights that may be useful for the analysis and design of parallel architectures.

PDF Details

NeurIPS Conference 2015 Conference Paper

On the Limitation of Spectral Methods: From the Gaussian Hidden Clique Problem to Rank-One Perturbations of Gaussian Tensors

Andrea Montanari
Daniel Reichman
Ofer Zeitouni

We consider the following detection problem: given a realization of asymmetric matrix $X$ of dimension $n$, distinguish between the hypothesisthat all upper triangular variables are i. i. d. Gaussians variableswith mean 0 and variance $1$ and the hypothesis that there is aplanted principal submatrix $B$ of dimension $L$ for which all upper triangularvariables are i. i. d. Gaussians with mean $1$ and variance $1$, whereasall other upper triangular elements of $X$ not in $B$ are i. i. d. Gaussians variables with mean 0 and variance $1$. We refer to this asthe `Gaussian hidden clique problem'. When $L=( 1 + \epsilon) \sqrt{n}$ ($\epsilon > 0$), it is possible to solve thisdetection problem with probability $1 - o_n(1)$ by computing thespectrum of $X$ and considering the largest eigenvalue of $X$. We prove that when$L < (1-\epsilon)\sqrt{n}$ no algorithm that examines only theeigenvalues of $X$can detect the existence of a hiddenGaussian clique, with error probability vanishing as $n \to \infty$. The result above is an immediate consequence of a more general result on rank-oneperturbations of $k$-dimensional Gaussian tensors. In this context we establish a lower bound on the criticalsignal-to-noise ratio below which a rank-one signal cannot be detected.

PDF Details