It is known that random k-SAT instances with at least $cn$ clauses, where $c =\nobreak c_k$ is a suitable constant, are unsatisfiable (with high probability). We consider the problem to certify efficiently the unsatisfiability of such formulas. A backtracking-based algorithm of Beame et al. [SIAM J. Comput.,} 31 (2002), pp. 1048--1075] shows that k-SAT instances with at least $n^{k-1}/(\log n)^{k-2}$ clauses can be certified unsatisfiable in polynomial time. We employ spectral methods to improve on this bound. For even $k\ge 4$ we present a polynomial time algorithm which certifies random k-SAT instances with at least $n^{(k/2)+o(1)}$ clauses as unsatisfiable (with high probability). For odd k we focus on 3-SAT instances and obtain an efficient algorithm for formulas with at least $n^{3/2+\varepsilon}$ clauses, where $\varepsilon >0$ is an arbitrary constant.

In this paper we describe several theorems that give lower bounds on the second eigenvalue of any quotient of a given size of a fixed graph, G. These theorems generalize Alon--Boppana-type theorems, where G is a regular (infinite) tree. When G is a hypercube, our theorems give minimum distance upper bounds on linear binary codes of a given size and information rate. Our bounds at best equal the current best bounds for codes and apply only to linear codes. However, it is of interest to note that (1) one very simple Alon--Boppana argument yields nontrivial code bound, and (2) our Alon--Boppana argument that equals a current best bound for codes has some hope of improvement. We also improve the bound in sharpest known Alon--Boppana theorem (i.e., when G is a regular tree).

A d-regular graph has largest or first (adjacency matrix) eigenvalue λ1 = d. In this paper we show the following conjecture of Alon. Fix an integer d > 2 and a real ε > 0. Then for sufficiently large n we have that "most" d-regular graphs on n vertices have all their eigenvalues except λ1 = d bounded above by 2√d-1 + ε. Our methods, being trace methods, also bound those eigenvalues below by -2√d-1 - ε.

Optical burst switching (OBS) is an experimental network technology that enables the construction of very high-capacity routers, using optical data paths and electronic control. We study wavelength converting switches using tunable lasers and wavelength grating routers, that are suitable for use in OBS systems and evaluate their performance. We show how the routing problem for these switches can be formulated as a combinatorial puzzle or game, in which the design of the game board corresponds to the pattern of permutation used at the input sections of the switch. We use this to show how the permutation pattern affects the performance of the switch, and to facilitate the design of permutation patterns that yield the best performance. We give upper bounds on the number of different wavelength channels that can be routed through such switches (regardless of the permutation pattern), and show that for 2×2 switches, there is a simple permutation pattern that achieves these bounds. For larger switches, randomized permutation patterns produce the best results. We study the performance of optical burst switches using wavelength converting switches based on several different permutation patterns. We also present a novel routing algorithm called the most available wavelength assignment and evaluate its benefits in improving the switch throughput. Our results show that for a typical configuration, the switch with the best permutation pattern has more than 87% of the throughput of a fully nonblocking switch.

We use the Laplacian and power method to compute Betti numbers of simplicial complexes. This has a number of advantages over other methods, both in theory and in practice. It requires small storage space in many cases. It seems to run quickly in practice, but its running time depends on a ratio, ν , of eigenvalues which we have yet to understand fully.

This note describes how varying the geometric representation of a poset can be applied to “poset balancing.” It is shown that the ${1 / 3}$, ${2 / 3}$ balancing property holds for a certain class of posets whose number of relations is sufficiently small, in a certain sense.

Consider a coloring of the n-dimensional Boolean cube with c=2/sup s/ colors in such a way that every k-dimensional subcube is equicolored, i.e. each color occurs the same number of times. The author shows that for such a coloring one necessarily has (k-1)/n>or= theta /sub c/=(c/2-1)/(c-1). This resolves the 'bit extraction' or 't-resilient functions' problem (also a special case of the privacy amplification problem) in many cases, such as c-1/n, proving that XOR type colorings are optimal, and always resolves this question to within c/4 in determining the optimal value of k (for any fixed n and c). He also studies the problem of finding almost equicolored colorings when (k-1)/n>

A model of regular infinite hypertrees is developed to mimic for hypergraphs what infinite trees do for graphs. Two notions of spectra, or “first eigenvalue,” are then examined for the infinite tree, obtaining a precise value for the first notion and obtaining some estimates for the second. The results indicate agreement of the first eigenvalue of the infinite hypertree with the ”second eigenvalue“ of a random hypergraph of the same degree, to within logarithmic factors, at least for the first notion of first eigenvalue.

In this paper a wide class of purely iterative root finding methods is proved to work for all complex valued polynomials with a positive probability depending only, on the method and the degree of the polynomial. More precisely, if the set of polynomials with roots in the knit ball is considered, then for fixed degree the area of convergent points in the ball of radius 2 is bounded below by some constant for any purely iterative method $z_{i + 1} \leftarrow T_f (z_i )$ where $T_f (z)$ is a rational function of z and $f_{i}$ and its derivatives, for which (1) $\infty $ is repelling fixed point for all f of degree greater than 1 and (2) $T_f (z)$ depends only on z and f’s roots and commutes with linear maps on the complex plane.

In this paper the authors study the size of the set of “approximate zeros” for Newton’s method, for a randomly chosen polynomial over certain distributions. For a degree d monic polynomial with coefficients chosen uniformly and independently in the unit ball, the results of this paper show, for example, that the set of approximate zeros is at least $Cd^{(-1.5-\varepsilon)}$ for any positive $\varepsilon$, with C depending only on $\varepsilon$.

Article Free Access Share on On the second eigenvalue of random regular graphs Authors: J. Friedman Department of Computer Science, Princeton University, Princeton, NJ Department of Computer Science, Princeton University, Princeton, NJView Profile , J. Kahn Dept. of Mathematics and Center for O. R., Rutgers University, New Brunswick, NJ Dept. of Mathematics and Center for O. R., Rutgers University, New Brunswick, NJView Profile , E. Szemerédi Dept. of Computer Science, Rutgers University, New Brunswick, NJ and Mathematical Institute of the Hungarian Academy of Sciences Dept. of Computer Science, Rutgers University, New Brunswick, NJ and Mathematical Institute of the Hungarian Academy of SciencesView Profile Authors Info & Claims STOC '89: Proceedings of the twenty-first annual ACM symposium on Theory of computingFebruary 1989 Pages 587–598https://doi.org/10.1145/73007.73063Published:01 February 1989Publication History 104citation2,261DownloadsMetricsTotal Citations104Total Downloads2,261Last 12 Months122Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A number of efficient probabilistic algorithms based on the combination of divide-and-conquer and random sampling have been recently discovered. It is shown that all those algorithms can be derandomized with only polynomial overhead. In the process. results of independent interest concerning the covering of hypergraphs are established, and various probabilistic bounds in geometry complexity are improved. For example, given n hyperplanes in d-space and any large enough integer r, it is shown how to compute, in polynomial time, a simplicial packing of size O(r/sup d/) that covers d-space, each of whose simplices intersects O(n/r) hyperplanes. It is also shown how to locate a point among n hyperplanes in d-space in O(log n) query time, using O(n/sup d/) storage and polynomial preprocessing.>

A new method for constructing wide-sense nonblocking networks is presented. Application of this method yields (among other things) wide-sense nonblocking generalized connectors with n inputs and outputs and size $O( n\log n )$, and with depth k and size $O ( n^{1 + 1/k} ( \log n )^{1 - 1/k} )$.

Let Pd be the set of polynomials over the complex numbers of degree d with all its roots in the unit ball. For f ∈ Pd, let Γf be the set of points for which Newton's method converges to a root, and let Af ≡ |Γf ∩ B2(O)|/|B2(O)|, i.e. the density of Γf in the ball of radius 2. For each d we consider Ad, the worst-case density Af for f ∈ Pd. In |S|, S. Smale conjectured that Ad ≫ 0 for all d ≥ 3 (it was wellknown that A1 = A2 = 1). In this paper we prove that (1/d)cd2 log d ≤ Ad for some constant c. In particular, Ad ≫ 0 for all d.

Two variants of the concept "non-blocking" have been defined in the literature: "strictly" non-blocking and "wide-sense" non-blocking. Hitherto, only toy examples were known of connectors that are wide-sense non-blocking but not strictly non-blocking, and these examples are more expensive than comparable strictly non-blocking connectors. In this paper we show for the first time how wide-sense non-blocking connectors can be less expensive than comparable strictly non- blocking connectors. In the simplest case we show that strictly non-blocking n-connectors with depth 2 must have ~2(n 2) edges, but wide-sense non-blocking n-connectors with depth 2 can have O(n 3/2 (log n) I/2) edges.

In this paper we construct formulae for the kth elementary symmetric polynomial of n Boolean variables, using only conjunction and disjunction, which for fixed k are of size $O(n\log n)$, with the construction taking time polynomial in n. We also prove theorems involving $n\log n \cdot $ (polynomial in k) upper bounds on such formulae. Our methods involve solving the following combinatorial problem: for fixed k and any n construct a collection of $r = O(\log n)$ functions $f_1 , \cdots ,f_r $ from $\{ 1, \cdots ,n\} $ to $\{ 1, \cdots ,k\} $ such that any subset of $\{ 1, \cdots ,n\} $ of order k is mapped 1–1 to $\{ 1, \cdots ,k\} $ by at least one $f_i $.

The state splitting algorithm of Adler, Coppersmith, and Hassner for graphs with edges of fixed length is extended to graphs with edges of variable lengths. This has the potential to improve modulation code construction techniques. Although the ideas of state splitting come from dynamical systems, completely graph-theoretic terms are used.

We consider the following adversarial situation. Let n, m and t be arbitrary integers, and let f : {0, 1}n → {0, 1}m be a function. An adversary, knowing the function f, sets t of the n input bits, while the rest (n-t input, bits) are chosen at random (independently and with uniform probability distribution) The adversary tries to prevent the outcome of f from being uniformly distributed in {0, 1}m. The question addressed is for what values of n, m and t does the adversary necessarily fail in biasing the outcome of f : {0,1}n → {0, 1}m, when being restricted to set t of the input bits of f. We present various lower and upper bounds on m's allowing an affirmative answer. These bounds are relatively close for t ≤ n/3 and for t ≥ 2n/3. Our results have applications in the fields of faulttolerance and cryptography.