Arrow Research search

Author name cluster

Leonard J. Schulman

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.

45 papers
1 author row

Possible papers

45

UAI Conference 2025 Conference Paper

Lower Bounds on the Size of Markov Equivalence Classes

  • Erik Jahn
  • Frederick Eberhardt
  • Leonard J. Schulman

Causal discovery algorithms typically recover causal graphs only up to their Markov equivalence classes unless additional parametric assumptions are made. The sizes of these equivalence classes reflect the limits of what can be learned about the underlying causal graph from purely observational data. Under the assumptions of acyclicity, causal sufficiency, and a uniform model prior, Markov equivalence classes are known to be small on average. In this paper, we show that this is no longer the case when any of these assumptions is relaxed. Specifically, we prove exponentially large lower bounds for the expected size of Markov equivalence classes in three settings: sparse random directed acyclic graphs, uniformly random acyclic directed mixed graphs, and uniformly random directed cyclic graphs.

Details

UAI Conference 2021 Conference Paper

Condition number bounds for causal inference

  • Spencer Gordon
  • Vinayak M. Kumar
  • Leonard J. Schulman
  • Piyush Srivastava 0001

An important achievement in the field of causal inference was a complete characterization of when a causal effect, in a system modeled by a causal graph, can be determined uniquely from purely observational data. The identification algorithms resulting from this work produce exact symbolic expressions for causal effects, in terms of the observational probabilities. More recent work has looked at the numerical properties of these expressions, in particular using the classical notion of the condition number. In its classical interpretation, the condition number quantifies the sensitivity of the output values of the expressions to small numerical perturbations in the input observational probabilities. In the context of causal identification, the condition number has also been shown to be related to the effect of certain kinds of uncertainties in the structure of the causal graphical model. In this paper, we first give an upper bound on the condition number for the interesting case of causal graphical models with small “confounded components”. We then develop a tight characterization of the condition number of any given causal identification problem. Finally, we use our tight characterization to give a specific example where the condition number can be much lower than that obtained via generic bounds on the condition number, and to show that even “equivalent” expressions for causal identification can behave very differently with respect to their numerical stability properties.

Details

SODA Conference 2020 Conference Paper

Edge Expansion and Spectral Gap of Nonnegative Matrices

  • Jenish C. Mehta
  • Leonard J. Schulman

The classic graphical Cheeger inequalities state that if M is an n × n symmetric doubly stochastic matrix, then where is the edge expansion of M, and λ 2 ( M ) is the second largest eigenvalue of M. We study the relationship between φ ( A ) and the spectral gap 1 – Re λ 2 ( A ) for any doubly stochastic matrix A (not necessarily symmetric), where λ 2 ( A ) is a nontrivial eigenvalue of A with maximum real part. Fiedler showed that the upper bound on φ ( A ) is unaffected, i. e. ,. With regards to the lower bound on φ ( A ), there are known constructions with indicating that at least a mild dependence on n is necessary to lower bound φ ( A ). In our first result, we provide an exponentially better construction of n × n doubly stochastic matrices A n, for which In fact, all nontrivial eigenvalues of our matrices are 0, even though the matrices are highly nonexpanding. We further show that this bound is in the correct range (up to the exponent of n ), by showing that for any doubly stochastic matrix A, As a consequence, unlike the symmetric case, there is a (necessary) loss of a factor of in lower bounding φ by the spectral gap in the nonsymmetric setting. Our second result extends these bounds to general matrices R with nonnegative entries, to obtain a two-sided gapped refinement of the Perron-Frobenius theorem. Recall from the Perron-Frobenius theorem that for such R, there is a nonnegative eigenvalue r such that all eigenvalues of R lie within the closed disk of radius r about 0. Further, if R is irreducible, which means φ ( R ) > 0 (for suitably defined φ ), then r is positive and all other eigenvalues lie within the open disk, so (with eigenvalues sorted by real part), Re λ 2 ( R ) < r. An extension of Fiedler's result provides an upper bound and our result provides the corresponding lower bound on φ ( R ) in terms of r – Re λ 2 ( R ), obtaining a two-sided quantitative version of the Perron-Frobenius theorem.

Details

STOC Conference 2018 Conference Paper

Explicit binary tree codes with polylogarithmic size alphabet

  • Gil Cohen
  • Bernhard Haeupler
  • Leonard J. Schulman

This paper makes progress on the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size. We give an explicit binary tree code with constant distance and alphabet size poly (log n ), where n is the depth of the tree. This is the first improvement over a two-decade-old construction that has an exponentially larger alphabet of size poly ( n ). At the core of our construction is the first explicit tree code with constant rate and constant distance, though with non-constant arity - a result of independent interest. This construction adapts the polynomial interpolation framework to the online setting.

Details

SODA Conference 2018 Conference Paper

Quasi-regular sequences and optimal schedules for security games

  • David Kempe 0001
  • Leonard J. Schulman
  • Omer Tamuz

We study security games in which a defender commits to a mixed strategy for protecting a finite set of targets of different values. An attacker, knowing the defender's strategy, chooses which target to attack and for how long. If the attacker spends time t at a target i of value α i, and if he leaves before the defender visits the target, his utility is t · a i; if the defender visits before he leaves, his utility is 0. The defender's goal is to minimize the attacker's utility. The defender's strategy consists of a schedule for visiting the targets; it takes her unit time to switch between targets. Such games are a simplified model of a number of real-world scenarios such as protecting computer networks from intruders, crops from thieves, etc. We show that optimal defender play for such security games, although played in continuous time, reduces to the solution of a combinatorial question regarding the existence of infinite sequences over a finite alphabet, with the following properties for each symbol i: (1) i constitutes a prescribed limiting fraction p i of the sequence. (2) The occurrences of i are spread apart close to evenly, in that the ratio of the longest to shortest interval between consecutive occurrences is bounded by a parameter K. We call such sequences K -quasi-regular; a 1-quasi-regular sequence is one in which the occurrences of each symbol form an arithmetic sequence. As we show, a 1-quasi-regular sequence ensures an optimal defender strategy for these security games: the intuition for this fact lies in the famous “inspection paradox. ” However, as we demonstrate, for K < 2 and general p i, K -quasi-regular sequences may not exist. Fortunately, this does not turn out to be an obstruction: we show that, surprisingly, 2-quasi-regular sequences also suffice for optimal defender play. What is more, even randomized 2-quasi-regular sequences suffice for optimality. We show that such sequences always exist, and can be calculated efficiently. Thus, we can ensure optimal defender play for these security games. The question of the least K for which deterministic K -quasi-regular sequences exist is fascinating. Using an ergodic theoretical approach, we proceed to show that deterministic 3-quasi-regular sequences always exist (and can be calculated efficiently). We also show that these deterministic 3-regular sequences give rise to a ≈ 1. 006-approximation algorithm for the defender's optimal strategy. For 2 ≤ K < 3 we do not know whether deterministic K -quasi-regular sequences always exist; however, when the pi are all small, improved bounds are possible, and in fact, (1 + ∊ )-quasi-regular deterministic sequences exist for any ∊ > 0 for sufficiently small p i.

Details

FOCS Conference 2016 Conference Paper

Extractors for Near Logarithmic Min-Entropy

  • Gil Cohen
  • Leonard J. Schulman

The main contribution of this work is an explicit construction of extractors for near logarithmic min-entropy. For any δ > 0 we construct an extractor for O(1/δ) n-bit sources with min-entropy (logn) 1+δ. This is most interesting when δ is set to a small constant, though the result also yields an extractor for O(log logn) sources with logarithmic min-entropy. Prior to this work, the best explicit extractor in terms of supporting least-possible min-entropy, due to Li (FOCS'15), requires min-entropy (logn) 2+δ from its O(1/δ) sources. Further, all current techniques for constructing multi-source extractors "break" below min-entropy (log n) 2. In fact, existing techniques do not provide even a disperser for o(log n) sources each with min-entropy (log n) 1. 99. Apart from being a natural problem, supporting logarithmic min-entropy has applications to combinatorics. A two-source disperser, let alone an extractor, for min-entropy O(log n) induces a (log, nO(1))-Ramsey graph on n vertices. Thus, constructing such dispersers would be a significant step towards constructively matching Erdös' proof for the existence of (2log n)-Ramsey graphs on n vertices. Our construction does not rely on the sophisticated primitives that were key to the substantial recent progress on multi-source extractors, such as non-malleable extractors, correlation breakers, the lightest-bin condenser, or extractors for non-oblivious bit-fixing sources, although some of these primitives can be combined with our construction so to improve the output length and the error guarantee. Instead, at the heart of our construction is a new primitive called an independence-preserving merger. The construction of the latter builds on the alternating extraction technique.

Details

UAI Conference 2016 Conference Paper

Stability of Causal Inference

  • Leonard J. Schulman
  • Piyush Srivastava 0001

We consider the sensitivity of causal identification to small perturbations in the input. A long line of work culminating in papers by Shpitser and Pearl (2006) and Huang and Valtorta (2008) led to a complete procedure for the causal identification problem. In our main result in this paper, we show that the identification function computed by these procedures is in some cases extremely unstable numerically. Specifically, the “condition number” of causal identification can be of the order of Ω(exp(n0. 49 )) on an identifiable semiMarkovian model with n visible nodes. That is, in order to give an output accurate to d bits, the empirical probabilities of the observable events need to be obtained to accuracy d + Ω(n0. 49 ) bits.

Details

SODA Conference 2016 Conference Paper

The Adversarial Noise Threshold for Distributed Protocols

  • William M. Hoza
  • Leonard J. Schulman

We consider the problem of implementing distributed protocols, despite adversarial channel errors, on synchronous-messaging networks with arbitrary topology. In our first result we show that any n -party T -round protocol on an undirected communication network G can be compiled into a robust simulation protocol on a sparse ( ℴ ( n ) edges) subnetwork so that the simulation tolerates an adversarial error rate of; the simulation has a round complexity of, where m is the number of edges in G. (So the simulation is work-preserving up to a log factor.) The adversary's error rate is within a constant factor of optimal. Given the error rate, the round complexity blowup is within a factor of ℴ ( k log n ) of optimal, where k is the edge connectivity of G. We also determine that the maximum tolerable error rate on directed communication networks is ⊝(1/ s ) where s is the number of edges in a minimum equivalent digraph. Next we investigate adversarial per-edge error rates, where the adversary is given an error budget on each edge of the network. We determine the limit for tolerable per-edge error rates on an arbitrary directed graph to within a factor of 2. However, the construction that approaches this limit has exponential round complexity, so we give another compiler, which transforms T -round protocols into ℴ ( mT )-round simulations, and prove that for polynomial-query black box compilers, the per-edge error rate tolerated by this last compiler is within a constant factor of optimal.

Details

STOC Conference 2015 Conference Paper

Analysis of a Classical Matrix Preconditioning Algorithm

  • Leonard J. Schulman
  • Alistair Sinclair

We study a classical iterative algorithm for the problem of balancing matrices in the L ∞ norm via a scaling transformation. This algorithm, which goes back to Osborne and Parlett & Reinsch in the 1960s, is implemented as a standard preconditioner in many numerical linear algebra packages. Surprisingly, despite its widespread use over several decades, no bounds were known on its rate of convergence. In this paper we prove that, for a large class of irreducible n x n (real or complex) input matrices~$A$, a natural variant of the algorithm converges in O(n 3 log(nρ/ε)) elementary balancing operations, where ρ measures the initial imbalance of A and ε is the target imbalance of the output matrix. (The imbalance of A is max i |log(a i out /a i in )|, where a i out ,a i in are the maximum entries in magnitude in the ith row and column respectively.) This bound is tight up to the log n factor. A balancing operation scales the ith row and column so that their maximum entries are equal, and requires O(m/n) arithmetic operations on average, where m is the number of non-zero elements in A. Thus the running time of the iterative algorithm is ~O(n 2 m). This is the first time bound of any kind on any variant of the Osborne-Parlett-Reinsch algorithm. The class of matrices for which the above analysis holds are those which satisfy a condition we call Unique Balance , meaning that the limit of the iterative balancing process does not depend on the order in which balancing operations are performed. We also prove a combinatorial characterization of the Unique Balance property, which had earlier been conjectured by Chen.

Details

STOC Conference 2015 Conference Paper

Learning Arbitrary Statistical Mixtures of Discrete Distributions

  • Jian Li 0015
  • Yuval Rabani
  • Leonard J. Schulman
  • Chaitanya Swamy

We study the problem of learning from unlabeled samples very general statistical mixture models on large finite sets. Specifically, the model to be learned, mix, is a probability distribution over probability distributions p, where each such p is a probability distribution over [n] = {1,2,...,n}. When we sample from mix, we do not observe p directly, but only indirectly and in very noisy fashion, by sampling from [n] repeatedly, independently K times from the distribution p. The problem is to infer mix to high accuracy in transportation (earthmover) distance.

Details

FOCS Conference 2015 Conference Paper

Symbolic Integration and the Complexity of Computing Averages

  • Leonard J. Schulman
  • Alistair Sinclair
  • Piyush Srivastava 0001

We study the computational complexity of several natural problems arising in statistical physics and combinatorics. In particular, we consider the following problems: the mean magnetization and mean energy of the Ising model (both the ferromagnetic and the anti-ferromagnetic settings), the average size of an independent set in the hard core model, and the average size of a matching in the monomer-dimer model. We prove that for all non-trivial values of the underlying model parameters, exactly computing these averages is #P-hard. In contrast to previous results of Sinclair and Srivastava (2013) for the mean magnetization of the ferromagnetic Ising model, our approach does not use any Lee-Yang type theorems about the complex zeros of partition functions. Indeed, it was due to the lack of suitable Lee-Yang theorems for models such as the anti-ferromagnetic Ising model that some of the problems we study here were left open by Sinclair and Srivastava. In this paper, we instead use some relatively simple and well-known ideas from the theory of automatic symbolic integration to complete our hardness reductions.

Details

FOCS Conference 2014 Conference Paper

Achieving Target Equilibria in Network Routing Games without Knowing the Latency Functions

  • Umang Bhaskar
  • Katrina Ligett
  • Leonard J. Schulman
  • Chaitanya Swamy

The analysis of network routing games typically assumes, right at the onset, precise and detailed information about the latency functions. Such information may, however, be unavailable or difficult to obtain. Moreover, one is often primarily interested in enforcing a desirable target flow as the equilibrium by suitably influencing player behavior in the routing game. We ask whether one can achieve target flows as equilibria without knowing the underlying latency functions. Our main result gives a crisp positive answer to this question. We show that, under fairly general settings, one can efficiently compute edge tolls that induce a given target multicommodity flow in a nonatomic routing game using a polynomial number of queries to an oracle that takes candidate tolls as input and returns the resulting equilibrium flow. This result is obtained via a novel application of the ellipsoid method, and applies to arbitrary multicommodity settings and non-linear latency functions. Our algorithm extends easily to many other settings, such as (i) when certain edges cannot be tolled or there is an upper bound on the total toll paid by a user, and (ii) general nonatomic congestion games. We obtain tighter bounds on the query complexity for series-parallel networks, and single-commodity routing games with linear latency functions, and complement these with a query-complexity lower bound applicable even to single-commodity routing games on parallel-link graphs with linear latency functions. We also explore the use of Stackelberg routing to achieve target equilibria and obtain strong positive results for series-parallel graphs. Our results build upon various new techniques that we develop pertaining to the computation of, and connections between, different notions of approximate equilibrium, properties of multicommodity flows and tolls in series-parallel graphs, and sensitivity of equilibrium flow with respect to tolls. Our results demonstrate that one can indeed circumvent the potentially-onerous task of modeling latency functions, and yet obtain meaningful results for the underlying routing game.

Details

SODA Conference 2013 Conference Paper

Clustering Affine Subspaces: Hardness and Algorithms

  • Euiwoong Lee
  • Leonard J. Schulman

We study a generalization of the famous k -center problem where each object is an affine subspace of dimension Δ, and give either the first or significantly improved algorithms and hardness results for many combinations of parameters. This generalization from points (Δ = 0) is motivated by the analysis of incomplete data, a pervasive challenge in statistics: incomplete data objects in ℝ d can be modeled as affine subspaces. We give three algorithmic results for different values of k, under the assumption that all subspaces are axis-parallel, the main case of interest because of the correspondence to missing entries in data tables. 1) k = 1: Two polynomial time approximation schemes which runs in poly (Δ, 1/∊) nd. 2) k = 2: O (Δ 1/4 )-approximation algorithm which runs in poly ( n, d, Δ) 3) General k: Polynomial time approximation scheme which runs in We also prove nearly matching hardness results; in both the general (not necessarily axis-parallel) case (for k ≥ 2) and in the axis-parallel case (for k ≥ 3), the running time of an approximation algorithm with any approximation ratio cannot be polynomial in even one of k and Δ, unless P = NP. Furthermore, assuming that the 3-SAT problem cannot be solved sub-exponentially, the dependence on both k and Δ must be exponential in the general case (in the axis-parallel case, only the dependence on k drops to. The simplicity of the first and the third algorithm suggests that they might be actually used in statistical applications. The second algorithm, which demonstrates a theoretical gap between the axis-parallel and general case for k = 2, displays a strong connection between geometric clustering and classical coloring problems on graphs and hypergraphs, via a new Helly-type theorem.

Details

STOC Conference 2008 Conference Paper

On partitioning graphs via single commodity flows

  • Lorenzo Orecchia
  • Leonard J. Schulman
  • Umesh V. Vazirani
  • Nisheeth K. Vishnoi

In this paper we obtain improved upper and lower bounds for the best approximation factor for Sparsest Cut achievable in the cut-matching game framework proposed in Khandekar et al. [9]. We show that this simple framework can be used to design combinatorial algorithms that achieve O(log n) approximation factor and whose running time is dominated by a poly-logarithmic number of single-commodity max-flow computations. This matches the performance of the algorithm of Arora and Kale [2]. Moreover, we also show that it is impossible to get an approximation factor of better than Ω(√log n) in the cut-matching game framework. These results suggest that the simple and concrete abstraction of the cut-matching game may be powerful enough to capture the essential features of the complexity of Sparsest Cut.

Details

FOCS Conference 2007 Conference Paper

Quantum Algorithms for Hidden Nonlinear Structures

  • Andrew M. Childs
  • Leonard J. Schulman
  • Umesh V. Vazirani

Attempts to find new quantum algorithms that outperform classical computation have focused primarily on the nonAbelian hidden subgroup problem, which generalizes the central problem solved by Shor's factoring algorithm. We suggest an alternative generalization, namely to problems of finding hidden nonlinear structures over finite fields. We give examples of two such problems that can be solved efficiently by a quantum computer, but not by a classical computer. We also give some positive results on the quantum query complexity of finding hidden nonlinear structures.

Details

FOCS Conference 2006 Conference Paper

The Effectiveness of Lloyd-Type Methods for the k-Means Problem

  • Rafail Ostrovsky
  • Yuval Rabani
  • Leonard J. Schulman
  • Chaitanya Swamy

We investigate variants of Lloyd's heuristic for clustering high dimensional data in an attempt to explain its popularity (a half century after its introduction) among practitioners, and in order to suggest improvements in its application. We propose and justify a clusterability criterion for data sets. We present variants of Lloyd's heuristic that quickly lead to provably near-optimal clustering solutions when applied to well-clusterable instances. This is the first performance guarantee for a variant of Lloyd's heuristic. The provision of a guarantee on output quality does not come at the expense of speed: some of our algorithms are candidates for being faster in practice than currently used variants of Lloyd's method. In addition, our other algorithms are faster on well-clusterable instances than recently proposed approximation algorithms, while maintaining similar guarantees on clustering quality. Our main algorithmic contribution is a novel probabilistic seeding process for the starting configuration of a Lloyd-type iteration

Details

FOCS Conference 2005 Conference Paper

Error-Correcting Codes for Automatic Control

  • Rafail Ostrovsky
  • Yuval Rabani
  • Leonard J. Schulman

In many control-theory applications one can classify all possible states of the device by an infinite state graph with polynomially-growing expansion. In order for a controller to control or estimate the state of such a device, it must receive reliable communications from its sensors; if there is channel noise, the encoding task is subject to a stringent real-time constraint. We show a constructive on-line error correcting code that works for this class of applications. Our code is computationally efficient and enables on-line estimation and control in the presence of channel noise. It establishes a constructive (and optimal-within-constants) analog, for control applications, of the Shannon coding theorem.

Details

FOCS Conference 2005 Conference Paper

The Symmetric Group Defies Strong Fourier Sampling

  • Cristopher Moore
  • Alexander Russell
  • Leonard J. Schulman

We resolve the question of whether Fourier sampling can efficiently solve the hidden subgroup problem in general groups. Specifically, we show that the hidden subgroup problem in the symmetric group cannot be efficiently solved by strong Fourier sampling. Indeed we prove the stronger statement that no measurement of a single coset state can reveal more than an exponentially small amount of information about the identity of the hidden subgroup, in the special case relevant to the graph isomorphism problem.

Details

UAI Conference 2000 Conference Paper

A Two-Round Variant of EM for Gaussian Mixtures

  • Sanjoy Dasgupta
  • Leonard J. Schulman

Given a set of possible models (e.g., Bayesian network structures) and a data sample, in the unsupervised model selection problem the task is to choose the most accurate model with respect to the domain joint probability distribution. In contrast to this, in supervised model selection it is a priori known that the chosen model will be used in the future for prediction tasks involving more ``focused' predictive distributions. Although focused predictive distributions can be produced from the joint probability distribution by marginalization, in practice the best model in the unsupervised sense does not necessarily perform well in supervised domains. In particular, the standard marginal likelihood score is a criterion for the unsupervised task, and, although frequently used for supervised model selection also, does not perform well in such tasks. In this paper we study the performance of the marginal likelihood score empirically in supervised Bayesian network selection tasks by using a large number of publicly available classification data sets, and compare the results to those obtained by alternative model selection criteria, including empirical crossvalidation methods, an approximation of a supervised marginal likelihood measure, and a supervised version of Dawids prequential(predictive sequential) principle.The results demonstrate that the marginal likelihood score does NOT perform well FOR supervised model selection, WHILE the best results are obtained BY using Dawids prequential r napproach.

Details

FOCS Conference 1998 Conference Paper

Pattern Matching for Spatial Point Sets

  • David E. Cardoze
  • Leonard J. Schulman

Two sets of points in d-dimensional space are given: a data set D consisting of N points, and a pattern set or probe P consisting of k points. We address the problem of determining whether there is a transformation, among a specified group of transformations of the space, carrying P into or near (meaning at a small directed Hausdorff distance of) D. The groups we consider are translations and rigid motions. Runtimes of approximately O(nlogn) and O(n/sup d/logn) respectively are obtained (letting n=max{N, k} and omitting the effects of several secondary parameters). For translations, a runtime of approximately O(n(ak+1)log/sup 2/n) is obtained for the case that a constant fraction /spl alpha/<1 of the points of the probe is allowed to fail to match.

Details

FOCS Conference 1998 Conference Paper

The Quantum Communication Complexity of Sampling

  • Andris Ambainis
  • Leonard J. Schulman
  • Amnon Ta-Shma
  • Umesh V. Vazirani
  • Avi Wigderson

Sampling is an important primitive in probabilistic and quantum algorithms. In the spirit of communication complexity, given a function f: X/spl times/Y/spl rarr/{0, 1} and a probability distribution D over X/spl times/Y, we define the sampling complexity of (f, D) as the minimum number of bits Alice and Bob must communicate for Alice to pick x/spl isin/X and Bob to pick y/spl isin/Y as well as a valve z s. t. the resulting distribution of (x, y, z) is close to the distribution (D, f(D)). In this paper we initiate the study of sampling complexity, in both the classical and quantum model. We give several variants of the definition. We completely characterize some of these tasks, and give upper and lower bounds on others. In particular this allows us to establish an exponential gap between quantum and classical sampling complexity, for the set disjointness function. This is the first exponential gap for any task where the classical probabilistic algorithm is allowed to err.

Details

FOCS Conference 1996 Conference Paper

Verifying Identities (extended abstract)

  • Sridhar Rajagopalan
  • Leonard J. Schulman

The authors provide an O/spl tilde/(n/sup 2/) time randomized algorithm to check whether a given operation f: S/spl times/S/spl rarr/S is associative (letting n=|S|). They prove this performance is optimal (up to polylogarithmic factors) even in case the operation is "cancellative". No sub-n/sup 3/ algorithm was previously known for this task. More generally they give an O(n/sup c/) time randomized algorithm to check whether a collection of c-ary operations satisfy any given "read-once" identity.

Details

FOCS Conference 1995 Conference Paper

Splitters and Near-Optimal Derandomization

  • Moni Naor
  • Leonard J. Schulman
  • Aravind Srinivasan

We present a fairly general method for finding deterministic constructions obeying what we call k-restrictions; this yields structures of size not much larger than the probabilistic bound. The structures constructed by our method include (n, k)-universal sets (a collection of binary vectors of length n such that for any subset of size k of the indices, all 2/sup k/ configurations appear) and families of perfect hash functions. The near-optimal constructions of these objects imply the very efficient derandomization of algorithms in learning, of fixed-subgraph finding algorithms, and of near optimal /spl Sigma/II/spl Sigma/ threshold formulae. In addition, they derandomize the reduction showing the hardness of approximation of set cover. They also yield deterministic constructions for a local-coloring protocol, and for exhaustive testing of circuits.

Details

FOCS Conference 1993 Conference Paper

Signal Propagation, with Application to a Lower Bound on the Depth of Noisy Formulas

  • William S. Evans
  • Leonard J. Schulman

We study the decay of an information signal propagating through a series of noisy channels. We obtain exact bounds on such decay, and as a result provide a new lower bound on the depth of formulas with noisy components. This improves upon previous work of N. Pippenger (1988) and significantly decreases the gap between his lower bound and the classical upper bound of von Neumann. We also discuss connections between our work and the study of mixing rates of Markov chains. >

Details

FOCS Conference 1992 Conference Paper

Communication on Noisy Channels: A Coding Theorem for Computation

  • Leonard J. Schulman

Communication is critical to distributed computing, parallel computing, or any situation in which automata interact-hence its significance as a resource in computation. In view of the likelihood of errors occurring in a lengthy interaction, it is desirable to incorporate this possibility in the model of communication. The author relates the noisy channel and the standard (noise less channel) complexities of a communication problem by establishing a 'two-way' or interactive analogue of Shanon's coding theorem: every noiseless channel protocol can be simulated by a private-coin noisy channel protocol whose time bound is proportional to the original (noiseless) time bound and inversely proportional to the capacity of the channel, while the protocol errs with vanishing probability. The method involves simulating the original protocol while implementing a hierarchical system of progress checks which ensure that errors of any magnitude in the simulation are, with high probability, rapidly eliminated. >

Details

FOCS Conference 1991 Conference Paper

The Maintenance of Common Data in a Distributed System

  • Baruch Awerbuch
  • Leonard J. Schulman

A basic task in distributed computation is the maintenance at each processor of the network, of a current and accurate copy of a common database. Such a database must be updated in the wake of locally generated changes to its contents. Due to previous disconnections of parts of the network, a maintenance protocol may need to update processors holding widely varying versions of the database. A deterministic protocol, which has only polylogarithmic overhead in its time and communication complexities, is provided for this problem. Previous deterministic solutions required polynomial overhead in at least one of these measures. >

Details
v2026.09.13