Randomization is a powerful tool that endows algorithms with remarkable properties. For instance, randomized algorithms excel in adversarial settings, often surpassing the worst-case performance of deterministic algorithms with large margins. Furthermore, their success probability can be amplified by simple strategies such as repetition and majority voting. In this paper, we enhance deep neural networks, in particular transformer models, with randomization. We demonstrate for the first time that randomized algorithms can be instilled in transformers through learning, in a purely data- and objective-driven manner. First, we analyze known adversarial objectives for which randomized algorithms offer a distinct advantage over deterministic ones. We then show that common optimization techniques, such as gradient descent or evolutionary strategies, can effectively learn transformer parameters that make use of the randomness provided to the model. To illustrate the broad applicability of randomization in empowering neural networks, we study three conceptual tasks: associative recall, graph coloring, and agents that explore grid worlds. In addition to demonstrating increased robustness against oblivious adversaries through learned randomization, our experiments reveal remarkable performance improvements due to the inherently random nature of the neural networks' computation and predictions.

Many complex tasks can be decomposed into simpler, independent parts. Discovering such underlying compositional structure has the potential to enable compositional generalization. Despite progress, our most powerful systems struggle to compose flexibly. It therefore seems natural to make models more modular to help capture the compositional nature of many tasks. However, it is unclear under which circumstances modular systems can discover hidden compositional structure. To shed light on this question, we study a teacher-student setting with a modular teacher where we have full control over the composition of ground truth modules. This allows us to relate the problem of compositional generalization to that of identification of the underlying modules. In particular we study modularity in hypernetworks representing a general class of multiplicative interactions. We show theoretically that identification up to linear transformation purely from demonstrations is possible without having to learn an exponential number of module combinations. We further demonstrate empirically that under the theoretically identified conditions, meta-learning from finite data can discover modular policies that generalize compositionally in a number of complex environments.

We design a randomized algorithm that finds a Hamilton cycle in 𝒪(n) time with high probability in a random graph G_{n,p} with edge probability p ≥ C log n / n. This closes a gap left open in a seminal paper by Angluin and Valiant from 1979.

Consider the following simple coloring algorithm for a graph on n vertices. Each vertex chooses a color from {1, ..., Δ(G) + 1} uniformly at random. While there exists a conflicted vertex choose one such vertex uniformly at random and recolor it with a randomly chosen color. This algorithm was introduced by Bhartia et al. [MOBIHOC'16] for channel selection in WIFI-networks. We show that this algorithm always converges to a proper coloring in expected O(n log Δ) steps, which is optimal and proves a conjecture of Chakrabarty and de Supinski [SOSA'20].

In the Maximum Label Propagation Algorithm (Max-LPA), each vertex draws a distinct random label. In each subsequent round, each vertex updates its label to the label that is most frequent among its neighbours (including its own label), breaking ties towards the larger label. It is known that this algorithm can detect communities in random graphs with planted communities if the graphs are very dense, by converging to a different consensus for each community. In [Kothapalli et al., 2013] it was also conjectured that the same result still holds for sparse graphs if the degrees are at least C log n. We disprove this conjecture by showing that even for degrees n^epsilon, for some epsilon>0, the algorithm converges without reaching consensus. In fact, we show that the algorithm does not even reach almost consensus, but converges prematurely resulting in orders of magnitude more communities.

One of the central goals of Recurrent Neural Networks (RNNs) is to learn long-term dependencies in sequential data. Nevertheless, the most popular training method, Truncated Backpropagation through Time (TBPTT), categorically forbids learning dependencies beyond the truncation horizon. In contrast, the online training algorithm Real Time Recurrent Learning (RTRL) provides untruncated gradients, with the disadvantage of impractically large computational costs. Recently published approaches reduce these costs by providing noisy approximations of RTRL. We present a new approximation algorithm of RTRL, Optimal Kronecker-Sum Approximation (OK). We prove that OK is optimal for a class of approximations of RTRL, which includes all approaches published so far. Additionally, we show that OK has empirically negligible noise: Unlike previous algorithms it matches TBPTT in a real world task (character-level Penn TreeBank) and can exploit online parameter updates to outperform TBPTT in a synthetic string memorization task. Code available at GitHub.

In computational neural network models, neurons are usually allowed to excite some and inhibit other neurons, depending on the weight of their synaptic connections. The traditional way to transform such networks into networks that obey Dale's law (i.e., a neuron can either excite or inhibit) is to accompany each excitatory neuron with an inhibitory one through which inhibitory signals are mediated. However, this requires an equal number of excitatory and inhibitory neurons, whereas a realistic number of inhibitory neurons is much smaller. In this letter, we propose a model of nonlinear interaction of inhibitory synapses on dendritic compartments of excitatory neurons that allows the excitatory neurons to mediate inhibitory signals through a subset of the inhibitory population. With this construction, the number of required inhibitory neurons can be reduced tremendously.

We study unbiased (1 + 1) evolutionary algorithms on linear functions with an unknown number n of bits with non-zero weight. Static algorithms achieve an optimal runtime of O(n(ln n)2+ε), however, it remained unclear whether more dynamic parameter policies could yield better runtime guarantees. We consider two setups: one where the mutation rate follows a fixed schedule, and one where it may be adapted depending on the history of the run. For the first setup, we give a schedule that achieves a runtime of (1±o(1))βn ln n, where β ≈ 3.552, which is an asymptotic improvement over the runtime of the static setup. Moreover, we show that no schedule admits a better runtime guarantee and that the optimal schedule is essentially unique. For the second setup, we show that the runtime can be further improved to (1 ± o(1))en ln n, which matches the performance of algorithms that know n in advance.

Despite all the impressive advances of recurrent neural networks, sequential data is still in need of better modelling. Truncated backpropagation through time (TBPTT), the learning algorithm most widely used in practice, suffers from the truncation bias, which drastically limits its ability to learn long-term dependencies.The Real Time Recurrent Learning algorithm (RTRL) addresses this issue, but its high computational requirements make it infeasible in practice. The Unbiased Online Recurrent Optimization algorithm (UORO) approximates RTRL with a smaller runtime and memory cost, but with the disadvantage of obtaining noisy gradients that also limit its practical applicability. In this paper we propose the Kronecker Factored RTRL (KF-RTRL) algorithm that uses a Kronecker product decomposition to approximate the gradients for a large class of RNNs. We show that KF-RTRL is an unbiased and memory efficient online learning algorithm. Our theoretical analysis shows that, under reasonable assumptions, the noise introduced by our algorithm is not only stable over time but also asymptotically much smaller than the one of the UORO algorithm. We also confirm these theoretical results experimentally. Further, we show empirically that the KF-RTRL algorithm captures long-term dependencies and almost matches the performance of TBPTT on real world tasks by training Recurrent Highway Networks on a synthetic string memorization task and on the Penn TreeBank task, respectively. These results indicate that RTRL based approaches might be a promising future alternative to TBPTT.

Processing sequential data of variable length is a major challenge in a wide range of applications, such as speech recognition, language modeling, generative image modeling and machine translation. Here, we address this challenge by proposing a novel recurrent neural network (RNN) architecture, the Fast-Slow RNN (FS-RNN). The FS-RNN incorporates the strengths of both multiscale RNNs and deep transition RNNs as it processes sequential data on different timescales and learns complex transition functions from one time step to the next. We evaluate the FS-RNN on two character based language modeling data sets, Penn Treebank and Hutter Prize Wikipedia, where we improve state of the art results to 1.19 and 1.25 bits-per-character (BPC), respectively. In addition, an ensemble of two FS-RNNs achieves 1.20 BPC on Hutter Prize Wikipedia outperforming the best known compression algorithm with respect to the BPC measure. We also present an empirical investigation of the learning and network dynamics of the FS-RNN, which explains the improved performance compared to other RNN architectures. Our approach is general as any kind of RNN cell is a possible building block for the FS-RNN architecture, and thus can be flexibly applied to different tasks.

Sequences of precisely timed neuronal activity are observed in many brain areas in various species. Synfire chains are a well-established model that can explain such sequences. However, it is unknown under which conditions synfire chains can develop in initially unstructured networks by self-organization. This work shows that with spike-timing dependent plasticity (STDP), modulated by global population activity, long synfire chains emerge in sparse random networks. The learning rule fosters neurons to participate multiple times in the chain or in multiple chains. Such reuse of neurons has been experimentally observed and is necessary for high capacity. Sparse networks prevent the chains from being short and cyclic and show that the formation of specific synapses is not essential for chain formation. Analysis of the learning rule in a simple network of binary threshold neurons reveals the asymptotically optimal length of the emerging chains. The theoretical results generalize to simulated networks of conductance-based leaky integrate-and-fire (LIF) neurons. As an application of the emerged chain, we propose a one-shot memory for sequences of precisely timed neuronal activity.

The connection density of nearby neurons in the cortex has been observed to be around 0.1, whereas the longer-range connections are present with much sparser density (Kalisman, Silberberg, & Markram, 2005 ). We propose a memory association model that qualitatively explains these empirical observations. The model we consider is a multiassociative, sparse, Willshaw-like model consisting of binary threshold neurons and binary synapses. It uses recurrent synapses for iterative retrieval of stored memories. We quantify the usefulness of recurrent synapses by simulating the model for small network sizes and by doing a precise mathematical analysis for large network sizes. Given the network parameters, we can determine the precise values of recurrent and afferent synapse densities that optimize the storage capacity of the network. If the network size is like that of a cortical column, then the predicted optimal recurrent density lies in a range that is compatible with biological measurements. Furthermore, we show that our model is able to surpass the standard Willshaw model in the multiassociative case if the information capacity is normalized per strong synapse or per bits required to store the model, as considered in Knoblauch, Palm, and Sommer ( 2010 ).

In this article, we consider a stochastic variant of the so-called Santa Claus problem. The Santa Claus problem is equivalent to the problem of scheduling a set of n jobs on m parallel machines without preemption, so as to maximize the minimum load. We consider the identical machine version of this scheduling problem with the additional restriction that the scheduler has only a guess of the processing times; that is, the processing time of a job is a random variable . We show that there is a critical value ρ ( n,m ) such that if the duration of the jobs is exponentially distributed and the expected values deviate by less than a multiplicative factor of ρ ( n,m ) from each other, then a greedy algorithm has an expected competitive ratio arbitrarily close to one; that is, it performs in expectation almost as good as an algorithm that knows the actual values in advance . On the other hand, if the expected values deviate by more than a multiplicative factor of ρ ( n,m ), then the expected performance is arbitrarily bad for all algorithms.

In 1976 Erdös, Kleitman, and Rothschild determined asymptotically the logarithm of the number of graphs without a clique of a fixed size $\ell$. In this note we extend their result to the case of forbidden cliques of increasing size. More precisely we prove that for $\ell_n \le (\log n)^{1/4}/2$ there are $2^{(1-1/(\ell_n-1))n^2/2+o(n^2/\ell_n)} K_{\ell_n}$-free graphs of order $n$. Our proof is based on the recent hypergraph container theorems of Saxton and Thomason and Balogh, Morris, and Samotij, in combination with a theorem of Lovász and Simonovits.

Cuckoo hashing is an efficient technique for creating large hash tables with high space utilization and guaranteed constant access times. There, each item can be placed in a location given by any one out of $k$ different hash functions. In this paper we investigate the random-walk heuristic for inserting in an online fashion new items into the hash table. Provided that $k \ge 3$ and that the number of items in the table is below (but arbitrarily close to) the theoretically achievable load threshold, we show a polylogarithmic bound for the maximum insertion time that holds with probability $1-o(1)$ as the size of the table grows large.

A common form of neural network consists of spatially arranged neurons, with weighted connections between the units providing both local excitation and long-range or global inhibition. Such networks, known as soft-winner-take-all networks or lateral-inhibition type neural fields, have been shown to exhibit desirable information-processing properties including balancing the influence of compatible inputs, deciding between incompatible inputs, signal restoration from noisy, weak, or overly strong input, and the ability to be used as trainable building blocks in larger networks. However, the local excitatory connections in such a network are typically hand-wired based on a fixed spatial arrangement which is chosen using prior knowledge of the dimensionality of the data to be learned by such a network, and neuroanatomical evidence is stubbornly inconsistent with these wiring schemes. Here we present a learning rule that allows networks with completely random internal connectivity to learn the weighted connections necessary for implementing the “local” excitation used by these networks, where the locality is with respect to the inherent topology of the input received by the network, rather than being based on an arbitrarily prescribed spatial arrangement of the cells in the network. We use the Siegert approximation to leaky integrate-and-fire neurons, obtaining networks with consistently sparse activity, to which we apply standard Hebbian learning with weight normalization, plus homeostatic activity regulation to ensure full network utilization. Our results show that such networks learn appropriate excitatory connections from the input, and do not require these connections to be hand-wired with a fixed topology as they traditionally have been for decades.

Let Pn denote a graph drawn uniformly at random from the class of all simple planar graphs with n vertices. We show that the maximum degree of a vertex in Pn is with probability 1 − o(1) asymptotically equal to c log n, where c ≈ 2.529 is determined explicitly. A similar result is also true for random 2-connected planar graphs. Our analysis combines two orthogonal methods that complement each other. First, in order to obtain the upper bound, we resort to exact methods, i.e., to generating functions and analytic combinatorics. This allows us to obtain fairly precise asymptotic estimates for the expected number of vertices of any given degree in Pn. On the other hand, for the lower bound we use Boltzmann sampling. In particular, by tracing the execution of an adequate algorithm that generates a random planar graph, we are able to explicitly find vertices of sufficiently high degree in Pn.

Biological systems process visual input using a distributed representation, with different areas encoding different aspects of the visual interpretation. While current engineering habits tempt us to think of this processing in terms of a pipelined sequence of filters and other feed-forward processing stages, cortical anatomy suggests quite a different architecture, using strong recurrent connectivity between visual areas. Here we design a network to interpret input from a neuromorphic sensor by means of recurrently interconnected areas, each of which encodes a different aspect of the visual interpretation, such as light intensity or optic flow. As each area of the network tries to be consistent with the information in neighboring areas, the visual interpretation converges towards global mutual consistency. Rather than applying input in a traditional feed-forward manner, the sensory input is only used to weakly influence the information flowing both ways through the middle of the network. Even with this seemingly weak use of input, this network of interacting maps is able to maintain its interpretation of the visual scene in real time, proving the viability of this interacting map approach to computation.

Let Pn be the class of all planar graphs with n labeled vertices, and let Pn be a graph drawn uniformly at random from Pn. In this paper we study the degree sequence of Pn. We show that with probability 1 − o(1) the number of vertices of degree k in Pn is very close to a quantity μkn that we determine explicitly, for all k ≤ c log n and an appropriate c > 0. A similar statement is true for random biconnected planar graphs as well. The main tool in our analysis is a framework that allows us under certain conditions to derive universal results about the degree distribution of random graphs from general classes with structural constraints. In particular, we address so-called critical graph classes, which due to their intricate structure have posed significant technical difficulties in the past.

The dynamics of large networks is an important and fascinating problem. Key examples are the Internet, social networks, and the human brain. In this paper we consider a model introduced by DeVille and Peskin [6] for a stochastic pulse-coupled neural network. The key feature and novelty in their approach is that they describe the interactions of a neuronal system as a discrete-state stochastic dynamical network. This idealization has two benefits: it captures essential features of neuronal behavior, and it allows the study of spontaneous synchronization, an important phenomenon in neuronal networks that is well-studied but unfortunately far from being well-understood. In synchronous behavior the firing of one neuron leads to the firing of other neurons, which in turn may set off a chain reaction that often involves a substantial proportion of the neurons. In this paper we rigorously analyze their model. In particular, by applying methods and tools that are frequently used in theoretical computer science, we provide a very precise picture of the dynamics and the evolution of the given system. In particular, we obtain insights into the coexistence of synchronous and asynchronous behavior and the conditions that trigger a “spontaneous” transition from one state to another.

Let C be a class of labeled connected graphs, and let C n be a graph drawn uniformly at random from graphs in C that contain exactly n vertices. Denote by b (ℓ; C n ) the number of blocks (i.e., maximal biconnected subgraphs) of C n that contain exactly ℓ vertices, and let lb (C n ) be the number of vertices in a largest block of C n . We show that under certain general assumptions on C , C n belongs with high probability to one of the following categories: (1) lb (C n ) ∼ cn , for some explicitly given c = c ( C ), and the second largest block is of order n α , where 1 > α = α( C ), or (2) lb (C n ) = O (log n ), that is, all blocks contain at most logarithmically many vertices. Moreover, in both cases we show that the quantity b (ℓ; C n ) is concentrated for all ℓ and we determine its expected value. As a corollary we obtain that the class of planar graphs belongs to category (1). In contrast to that, outerplanar and series-parallel graphs belong to category (2).

Let be the class of simple labeled planar graphs with n vertices, and denote by Pn a graph drawn uniformly at random from this set. Basic properties of Pn were first investigated by Denise, Vasconcellos, and Welsh [7]. Since then, the random planar graph has attracted considerable attention, and is nowadays an important and challenging model for evaluating methods that are developed to study properties of random graphs from classes with structural side constraints. In this paper we study closely the structure of Pn. More precisely, let b(ℓ; Pn) be the number of blocks (i.e. maximal biconnected subgraphs) of Pn that contain exactly ℓ vertices, and let lb(Pn) be the number of vertices in the largest block of Pn. We show that with high probability Pn contains a giant block that includes up to lower order terms cn vertices, where c ≈ 0.959 is an analytically given constant. Moreover, we show that the second largest block contains only (n2/3) vertices, and prove sharp concentration results for b(ℓ; Pn), for all 2 ≤ ℓ ≤ n2/3 (here (.) stands for “up to logarithmic factors”). In fact, we obtain this result as a consequence of a much more general result that we prove in this paper. Let be a class of labeled connected graphs, and let Cn be a graph drawn uniformly at random from graphs in that contain exactly n vertices. Under certain assumptions on , and depending on the behavior of the singularity of the generating function enumerating the elements of , Cn belongs with high probability to one of the following three categories, which differ vastly in complexity. Cn either (1) behaves like a random planar graph, i.e. lb(Cn) ∼ cn, for some analytically given c = c, and the second largest block is of order nα, where 1 > α = α, or (2) lb(Cn) = (log n), i.e., all blocks contain at most logarithmically many vertices, or (3) , for some α = α < 1. Planar graphs belong to category (1). In contrast to that, outerplanar and series-parallel graphs belong to category (2).

The Minimum Weight Triangulation problem is to find a triangulation T* of minimum length for a given set of points P in the Euclidean plane. It was one of the few longstanding open problems from the famous list of twelve problems with unknown complexity status, published by Garey and Johnson [1979]. Very recently, the problem was shown to be NP -hard by Mulzer and Rote [2006]. In this article, we present a quasi-polynomial time approximation scheme for Minimum Weight Triangulation.

The MINIMUM WEIGHT TRIANGULATION problem is to find a triangulation T* of minimum length for a given set of points P in the Euclidean plane. It was one of the few longstanding open problems from the famous list of twelve problems with unknown complexity status, published by Garey and Johnson [8] in 1979. Very recently the problem was shown to be NP-hard by Mulzer and Rote. In this paper, we present a quasi-polynomial time approximation scheme for MINIMUM WEIGHT TRIANGULATION.

We present a new average case analysis for the problem of scheduling n jobs on m machines so that the sum of job completion times is minimized. Our goal is to use the concept of competitive ratio---which is a typical worst case notion---also within an average case analysis. We show that the classic SEPT scheduling strategy with Ω( n ) worst-case competitive ratio achieves an average of O(1) under several natural distributions, among them the exponential distribution. Our analysis technique allows to also roughly estimate the probability distribution of the competitive ratio. Thus, our result bridges the gap between worst case and average case performance guarantee.

We investigate balls-into-bins processes allocating m balls into n bins based on the multiple-choice paradigm. In the classical single-choice variant each ball is placed into a bin selected uniformly at random. In a multiple-choice process each ball can be placed into one out of $d \ge 2$ randomly selected bins. It is known that in many scenarios having more than one choice for each ball can improve the load balance significantly. Formal analyses of this phenomenon prior to this work considered mostly the lightly loaded case, that is, when $m \approx n$. In this paper we present the first tight analysis in the heavily loaded case, that is, when $m \gg n$ rather than $m \approx n$. The best previously known results for the multiple-choice processes in the heavily loaded case were obtained using majorization by the single-choice process. This yields an upper bound of the maximum load of bins of $m/n + {\mbox{$\cal O$}}(\sqrt{m \ln n \,/\, n})$ with high probability. We show, however, that the multiple-choice processes are fundamentally different from the single-choice variant in that they have "short memory." The great consequence of this property is that the deviation of the multiple-choice processes from the optimal allocation (that is, the allocation in which each bin has either $\lfloor m/n \rfloor$ or $\lceil m/n \rceil$ balls) does not increase with the number of balls as in the case of the single-choice process. In particular, we investigate the allocation obtained by two different multiple-choice allocation schemes, the greedy scheme due to Azar et al. and the always-go-left scheme due to Vöcking. We show that these schemes result in a maximum load of only $m/n + {\mbox{$\cal O$}}(\ln \ln n)$ with high probability. All our detailed bounds on the maximum load are tight up to an additive constant. Furthermore, we investigate the two multiple-choice algorithms in a comparative study. We present a majorization result showing that the always-go-left scheme obtains a better load balancing than the greedy scheme for any choice of n, m, and d.

(MATH) We present a new average case analysis for the problem of scheduling n jobs on $m$ machines so that the sum of job completion times is minimized. Our analysis transfers the concept of competitive analysis --- which is a typical worst case notion --- to the average case. We show that the classic SEPT scheduling strategy with Ω(n) worst case competitive ratio achieves ${\cal O}(1)$ on the average. Moreover, bounds on the probability distribution of the competitive ratio are derived which provide an in-depth understanding of the stochastic version of the min sum scheduling problem.

We investigate load balancing processes based on the multiplechoice paradigm.In these randomized processes m balls are inserted into n bins.In the classical single-choice variant each ball is placed simply into a randomly selected bin.In a multiple-choice process each ball can be placed into one out of d _> 2 randomly selected bins.It is well known that having more than one choice for each ball can improve the load balance significantly.In contrast to previous work on multiple-choice processes, we investigate the heavily loaded case, that is, we assume m >> n rather than m ,.~ n.The best previously known results for the multiple-choice processes in the heavily loaded case were obtained by majorization from the single-choice process.This yields an upper bound of m/n + O(~n).We show, however, that the multiplechoice processes are fundamentally different from the singlechoice variant in that they have "short memory".The great consequence of this property is that the deviation of the multiple-choice processes from the optimal allocation (i.e., at most [m/n] balls in every bin) does not increase with the number of balls as in case of the single-choice process.In particular, we investigate the allocation obtained by two different multiple-choice allocation schemes, the original greedy scheme and the recently presented always-go-left scheme.We show that

In this paper we consider dynamic load balancing algorithms for randomized and adversarial load generation models. Consider a system of n processors. In our randomized generation models every processor may generate a task with a certain probability at each time step, leading to an expected system load of O(n). We present a load balancing algorithm that assures that with high probability no processor has a load exceeding O(log log n) at an arbitrary point of time. This improves upon the O ((log log n) 2 ) bound of [4] In the case of the adversarial load generation model every processor can change its load by some constant at each time step. Thus, the system load may become arbitrarily large. We present a balancing algorithm and show that if at some point of time r no processor has a load exceeding some constant times the average, with high probability this holds for the next polynomial number of steps. Furthermore, we show that if the system is unstable at some point of time (meaning that there are processors with load much more than the average), then our algorithm recovers the system within expected poly(n) steps.

Circuit partitioning plays a fundamental role in hierarchical layout systems. Identifying the strongly connected subcircuits, the clusters, of the logic can significantly reduce the delay of the circuit and the total interconnection length. Finding such a cluster partition however, is NP-complete. The authors propose a fast heuristic algorithm based on a simple, local criterion. They are able to prove that for highly structured circuits the clusters found by this algorithm correspond with high probability to the 'natural' clusters. An application to large scale real world circuits shows that by this method the number of nets cut is reduced by up to 46% compared to the standard mincut approach.>

A report is presented on the partitioning algorithm of a novel automatic layout system for the sea-of-cells design. The algorithm is based on graph partitioning. The principal novelty of the approach is that a global routing is obtained after each iteration to precisely estimate the number of nets crossing a cut. The author also report on the successful application to CMOS chips of the IBM ES/370 chip set.>