A central and longstanding open problem in coding theory is the rate-versus-distance trade-off for binary error-correcting codes. In a seminal work, Delsarte introduced a family of linear programs establishing relaxations on the size of optimum codes. To date, the state-of-the-art upper bounds for binary codes come from dual feasible solutions to these LPs. Still, these bounds are exponentially far from the best-known existential constructions. Recently, hierarchies of linear programs extending and strengthening Delsarte's original LPs were introduced for linear codes, which we refer to as higher-order Delsarte LPs. These new hierarchies were shown to provably converge to the actual value of optimum codes, namely, they are complete hierarchies. Therefore, understanding them and their dual formulations becomes a valuable line of investigation. Nonetheless, their higher-order structure poses challenges. In fact, analysis of all known convex programming hierarchies strengthening Delsarte's original LPs has turned out to be exceedingly difficult and essentially nothing is known, stalling progress in the area since the 1970s. Our main result is an analysis of the higher-order Delsarte LPs via their dual formulation. Although quantitatively, our current analysis only matches the best-known upper bounds, it shows, for the first time, how to tame the complexity of analyzing a hierarchy strengthening Delsarte's original LPs. In doing so, we reach a better understanding of the structure of the hierarchy, which may serve as the foundation for further quantitative improvements. We provide two additional structural results for this hierarchy. First, we show how to \emph{explicitly} lift any feasible dual solution from level $k$ to a (suitable) larger level $\ell$ while retaining the objective value. Second, we give a novel proof of completeness using the dual formulation.

Abstract A consistent path system in a graph G is an intersection-closed collection of paths, with exactly one path between any two vertices in G . We call G metrizable if every consistent path system in it is the system of geodesic paths defined by assigning some positive lengths to its edges. We show that metrizable graphs are, in essence, subdivisions of a small family of basic graphs with additional compliant edges. In particular, we show that every metrizable graph with 11 vertices or more is outerplanar plus one vertex.

Abstract The collection of all n-point metric spaces of diameter $$\le 1$$ ≤ 1 constitutes a polytope $$\mathcal {M}_n \subset \mathbb {R}^{\left( {\begin{array}{c}n\\ 2\end{array}}\right) }$$ M n ⊂ R n 2 , called the Metric Polytope. In this paper, we consider the best approximations of $$\mathcal {M}_n$$ M n by ellipsoids. We give an exact explicit description of the largest volume ellipsoid contained in $$\mathcal {M}_n$$ M n . When inflated by a factor of $$\Theta (n)$$ Θ ( n ) , this ellipsoid contains $$\mathcal {M}_n$$ M n . It also turns out that the least volume ellipsoid containing $$\mathcal {M}_n$$ M n is a ball. When shrunk by a factor of $$\Theta (n)$$ Θ ( n ) , the resulting ball is contained in $$\mathcal {M}_n$$ M n . We note that the general theorems on such ellipsoid posit only that the pertinent inflation/shrinkage factors can be made as small as $$O(n^2)$$ O ( n 2 ) .

We develop a new family of linear programs, that yield upper bounds on the rate of binary linear codes of a given distance. Our bounds apply only to linear codes. Delsarte’s LP is the weakest member of this family and our LP yields increasingly tighter upper bounds on the rate as its control parameter increases. Numerical experiments show significant improvement compared to Delsarte. These convincing numerical results, and the large variety of tools available for asymptotic analysis, give us hope that our work will lead to new improved asymptotic upper bounds on the possible rate of linear codes. A slightly prior work by Coregliano, Jeronimo and Jones offers a closely related family of linear programs which converges to the true bound. Here we provide a new proof of convergence for the same LPs.

In the 3-players exactly-N problem the players need to decide whether x+y+z = N for inputs x,y,z and fixed N. This is the first problem considered in the multiplayer Number On the Forehead (NOF) model. Even though this is such a basic problem, no progress has been made on it throughout the years. Only recently have explicit protocols been found for the first time, yet no improvement in complexity has been achieved to date. The present paper offers the first improved protocol for the exactly-N problem. This improved protocol has also interesting consequences in additive combinatorics. As we explain below, it yields a higher lower bound on the possible density of corner-free sets in [N]×[N].

We study the multiparty communication complexity of high dimensional permutations, in the Number On the Forehead (NOF) model. This model is due to Chandra, Furst and Lipton (CFL) who also gave a nontrivial protocol for the Exactly-n problem where three players receive integer inputs and need to decide if their inputs sum to a given integer $n$. There is a considerable body of literature dealing with the same problem, where $(\mathbb{N},+)$ is replaced by some other abelian group. Our work can be viewed as a far-reaching extension of this line of work. We show that the known lower bounds for that group-theoretic problem apply to all high dimensional permutations. We introduce new proof techniques that appeal to recent advances in Additive Combinatorics and Ramsey theory. We reveal new and unexpected connections between the NOF communication complexity of high dimensional permutations and a variety of well known and thoroughly studied problems in combinatorics. Previous protocols for Exactly-n all rely on the construction of large sets of integers without a 3-term arithmetic progression. No direct algorithmic protocol was previously known for the problem, and we provide the first such algorithm. This suggests new ways to significantly improve the CFL protocol. Many new open questions are presented throughout.

Mature microRNAs (miRNAs) regulate most human genes through direct base-pairing with mRNAs. We investigate the underlying principles of miRNA regulation in living cells. To this end, we overexpressed miRNAs in different cell types and measured the mRNA decay rate under a paradigm of a transcriptional arrest. Based on an exhaustive matrix of mRNA-miRNA binding probabilities, and parameters extracted from our experiments, we developed a computational framework that captures the cooperative action of miRNAs in living cells. The framework, called COMICS, simulates the stochastic binding events between miRNAs and mRNAs in cells. The input of COMICS is cell-specific profiles of mRNAs and miRNAs, and the outcome is the retention level of each mRNA at the end of 100,000 iterations. The results of COMICS from thousands of miRNA manipulations reveal gene sets that exhibit coordinated behavior with respect to all miRNAs (total of 248 families). We identified a small set of genes that are highly responsive to changes in the expression of almost any of the miRNAs. In contrast, about 20% of the tested genes remain insensitive to a broad range of miRNA manipulations. The set of insensitive genes is strongly enriched with genes that belong to the translation machinery. These trends are shared by different cell types. We conclude that the stochastic nature of miRNAs reveals unexpected robustness of gene expression in living cells. By applying a systematic probabilistic approach some key design principles of cell states are revealed, emphasizing in particular, the immunity of the translational machinery vis-a-vis miRNA manipulations across cell types. We propose COMICS as a valuable platform for assessing the outcome of miRNA regulation of cells in health and disease.

Many popular learning algorithms (E.g. Regression, Fourier-Transform based algorithms, Kernel SVM and Kernel ridge regression) operate by reducing the problem to a convex optimization problem over a set of functions. These methods offer the currently best approach to several central problems such as learning half spaces and learning DNF’s. In addition they are widely used in numerous application domains. Despite their importance, there are still very few proof techniques to show limits on the power of these algorithms. We study the performance of this approach in the problem of (agnostically and improperly) learning halfspaces with margin γ. Let D be a distribution over labeled examples. The γ-margin error of a hyperplane h is the probability of an example to fall on the wrong side of h or at a distance \leγfrom it. The γ-margin error of the best h is denoted \mathrmErr_γ(D). An α(γ)-approximation algorithm receives γ,εas input and, using i.i.d. samples of D, outputs a classifier with error rate \le α(γ)\mathrmErr_γ(D) + ε. Such an algorithm is efficient if it uses \mathrmpoly(\frac1γ,\frac1ε) samples and runs in time polynomial in the sample size. The best approximation ratio achievable by an efficient algorithm is O\left(\frac1/γ\sqrt\log(1/γ)\right) and is achieved using an algorithm from the above class. Our main result shows that the approximation ratio of every efficient algorithm from this family must be \ge Ω\left(\frac1/γ\mathrmpoly\left(\log\left(1/γ\right)\right)\right), essentially matching the best known upper bound.

The basic problem in the PAC model of computational learning theory is to determine which hypothesis classes are effficiently learnable. There is presently a dearth of results showing hardness of learning problems. Moreover, the existing lower bounds fall short of the best known algorithms.

MOTIVATION: Modern protein sequencing techniques have led to the determination of >50 million protein sequences. ProtoNet is a clustering system that provides a continuous hierarchical agglomerative clustering tree for all proteins. While ProtoNet performs unsupervised classification of all included proteins, finding an optimal level of granularity for the purpose of focusing on protein functional groups remain elusive. Here, we ask whether knowledge-based annotations on protein families can support the automatic unsupervised methods for identifying high-quality protein families. We present a method that yields within the ProtoNet hierarchy an optimal partition of clusters, relative to manual annotation schemes. The method's principle is to minimize the entropy-derived distance between annotation-based partitions and all available hierarchical partitions. We describe the best front (BF) partition of 2 478 328 proteins from UniRef50. Of 4,929,553 ProtoNet tree clusters, BF based on Pfam annotations contain 26,891 clusters. The high quality of the partition is validated by the close correspondence with the set of clusters that best describe thousands of keywords of Pfam. The BF is shown to be superior to naïve cut in the ProtoNet tree that yields a similar number of clusters. Finally, we used parameters intrinsic to the clustering process to enrich a priori the BF's clusters. We present the entropy-based method's benefit in overcoming the unavoidable limitations of nested clusters in ProtoNet. We suggest that this automatic information-based cluster selection can be useful for other large-scale annotation schemes, as well as for systematically testing and comparing putative families derived from alternative clustering methods. AVAILABILITY AND IMPLEMENTATION: A catalog of BF clusters for thousands of Pfam keywords is provided at http://protonet.cs.huji.ac.il/bestFront/.

In the musical chairs game $MC(n,m)$, a team of $n$ players plays against an adversarial scheduler. The scheduler wins if the game proceeds indefinitely, while termination after a finite number of rounds is declared a win of the team. At each round of the game each player occupies one of the $m$ available chairs. Termination (and a win of the team) is declared as soon as each player occupies a unique chair. Two players that simultaneously occupy the same chair are said to be in conflict. In other words, termination (and a win for the team) is reached as soon as there are no conflicts. The only means of communication throughout the game is this: At every round of the game, the scheduler selects an arbitrary nonempty set of players who are currently in conflict, and notifies each of them separately that it must move. A player who is thus notified changes its chair according to its deterministic program. As we show, for $m\ge 2n-1$ chairs the team has a winning strategy. Moreover, using topological arguments we show that this bound is tight. For $m\leq 2n-2$ the scheduler has a strategy that is guaranteed to make the game continue indefinitely and thus win. We also have some results on additional interesting questions. For example, if $m \ge 2n-1$ (so that the team can win), how quickly can they achieve victory?

The increased availability of data in recent years led several authors to ask whether it is possible to use data as a {\em computational} resource. That is, if more data is available, beyond the sample complexity limit, is it possible to use the extra examples to speed up the computation time required to perform the learning task? We give the first positive answer to this question for a {\em natural supervised learning problem} --- we consider agnostic PAC learning of halfspaces over $3$-sparse vectors in $\{-1,1,0\}^n$. This class is inefficiently learnable using $O\left(n/\epsilon^2\right)$ examples. Our main contribution is a novel, non-cryptographic, methodology for establishing computational-statistical gaps, which allows us to show that, under a widely believed assumption that refuting random $\mathrm{3CNF}$ formulas is hard, efficiently learning this class using $O\left(n/\epsilon^2\right)$ examples is impossible. We further show that under stronger hardness assumptions, even $O\left(n^{1.499}/\epsilon^2\right)$ examples do not suffice. On the other hand, we show a new algorithm that learns this class efficiently using $\tilde{\Omega}\left(n^2/\epsilon^2\right)$ examples. This formally establishes the tradeoff between sample and computational complexity for a natural supervised learning problem.

For many optimization problems, the instances of practical interest often occupy just a tiny part of the algorithm's space of instances. Following (Y. Bilu and N. Linial, 2010), we apply this perspective to MAXCUT, viewed as a clustering problem. Using a variety of techniques, we investigate practically interesting instances of this problem. Specifically, we show how to solve in polynomial time distinguished, metric, expanding and dense instances of MAXCUT under mild stability assumptions. In particular, (1 + epsilon)-stability (which is optimal) suffices for metric and dense MAXCUT. We also show how to solve in polynomial time Omega(sqrt(n))-stable instances of MAXCUT, substantially improving the best previously known result.

Fair allocation has been studied intensively in both economics and computer science. This subject has aroused renewed interest with the advent of virtualization and cloud computing. Prior work has typically focused on mechanisms for fair sharing of a single resource. We consider a variant where each user is entitled to a certain fraction of the system's resources, and has a fixed usage profile describing how much he would want from each resource. We provide a new definition for the simultaneous fair allocation of multiple continuously-divisible resources that we call bottleneck-based fairness (BBF). Roughly speaking, an allocation of resources is considered fair if every user either gets all the resources he wishes for, or else gets at least his entitlement on some bottleneck resource, and therefore cannot complain about not receiving more. We show that BBF has several desirable properties such as providing an incentive for sharing, and also promotes high overall utilization of resources; we also compare BBF carefully to another notion of fairness proposed recently, dominant resource fairness.

Online reputation systems collect, maintain and disseminate reputations as a summary numerical score of past interactions of an establishment with its users. As reputation systems, including web search engines, gain in popularity and become a common method for people to select sought services, a dynamical system unfolds: Experts' reputation attracts the potential customers. The experts' expertise affects the probability of satisfying the customers. This rate of success in turn influences the experts' reputation. We consider here several models where each expert has innate, constant, but unknown level of expertise and a publicly known, dynamically varying, reputation.

MOTIVATION: Large-scale RNA expression measurements are generating enormous quantities of data. During the last two decades, many methods were developed for extracting insights regarding the interrelationships between genes from such data. The mathematical and computational perspectives that underlie these methods are usually algebraic or probabilistic. RESULTS: Here, we introduce an unexplored geometric view point where expression levels of genes in multiple experiments are interpreted as vectors in a high-dimensional space. Specifically, we find, for the expression profile of each particular gene, its approximation as a linear combination of profiles of a few other genes. This method is inspired by recent developments in the realm of compressed sensing in the machine learning domain. To demonstrate the power of our approach in extracting valuable information from the expression data, we independently applied it to large-scale experiments carried out on the yeast and malaria parasite whole transcriptomes. The parameters extracted from the sparse reconstruction of the expression profiles, when fed to a supervised learning platform, were used to successfully predict the relationships between genes throughout the Gene Ontology hierarchy and protein-protein interaction map. Extensive assessment of the biological results shows high accuracy in both recovering known predictions and in yielding accurate predictions missing from the current databases. We suggest that the geometrical approach presented here is suitable for a broad range of high-dimensional experimental data.

MOTIVATION: Much of the large-scale molecular data from living cells can be represented in terms of networks. Such networks occupy a central position in cellular systems biology. In the protein-protein interaction (PPI) network, nodes represent proteins and edges represent connections between them, based on experimental evidence. As PPI networks are rich and complex, a mathematical model is sought to capture their properties and shed light on PPI evolution. The mathematical literature contains various generative models of random graphs. It is a major, still largely open question, which of these models (if any) can properly reproduce various biologically interesting networks. Here, we consider this problem where the graph at hand is the PPI network of Saccharomyces cerevisiae. We are trying to distinguishing between a model family which performs a process of copying neighbors, represented by the duplication-divergence (DD) model, and models which do not copy neighbors, with the Barabási-Albert (BA) preferential attachment model as a leading example. RESULTS: The observed property of the network is the distribution of maximal bicliques in the graph. This is a novel criterion to distinguish between models in this area. It is particularly appropriate for this purpose, since it reflects the graph's growth pattern under either model. This test clearly favors the DD model. In particular, for the BA model, the vast majority (92.9%) of the bicliques with both sides ≥4 must be already embedded in the model's seed graph, whereas the corresponding figure for the DD model is only 5.1%. Our results, based on the biclique perspective, conclusively show that a naïve unmodified DD model can capture a key aspect of PPI networks.

This paper has two main focal points. We first consider an important class of machine learning algorithms - large margin classifiers, such as support vector machines. The notion of margin complexity quantifies the extent to which a given class of functions can be learned by large margin classifiers. We prove that up to a small multiplicative constant, margin complexity is equal to the inverse of discrepancy. This establishes a strong tie between seemingly very different notions from two distinct areas. In the same way that matrix rigidity is related to rank, we introduce the notion of rigidity of margin complexity. We prove that sign matrices with small margin complexity rigidity are very rare. This leads to the question of proving lower bounds on the rigidity of margin complexity. Quite surprisingly, this question turns out to be closely related to basic open problems in communication complexity, e.g., whether PSPACE can be separated from the polynomial hierarchy in communication complexity. There are numerous known relations between the field of learning theory and that of communication complexity, as one might expect since communication is an inherent aspect of learning. The results of this paper constitute another link in this rich web of relations. This link has already proved significant as it was used in the solution of a few open problems in communication complexity.

We introduce a new method to derive lower bounds on randomized and quantum communication complexity. Our method is based on factorization norms, a notion from Banach Space theory. This approach gives us access toseveral powerful tools from this area such as normed spaces duality and Grothendiek's inequality. This extends the arsenal of methods for deriving lower bounds in communication complexity. As we show,our method subsumes most of the previously known general approaches to lower bounds on communication complexity. Moreover, we extend all (but one) of these lower bounds to the realm of quantum communication complexity with entanglement. Our results also shed some light on the question how much communication can be saved by using entanglement.It is known that entanglement can save one of every two qubits, and examples for which this is tight are also known. It follows from our results that this bound on the saving in communication is tight almost always.

BACKGROUND: Proteins are comprised of one or several building blocks, known as domains. Such domains can be classified into families according to their evolutionary origin. Whereas sequencing technologies have advanced immensely in recent years, there are no matching computational methodologies for large-scale determination of protein domains and their boundaries. We provide and rigorously evaluate a novel set of domain families that is automatically generated from sequence data. Our domain family identification process, called EVEREST (EVolutionary Ensembles of REcurrent SegmenTs), begins by constructing a library of protein segments that emerge in an all vs. all pairwise sequence comparison. It then proceeds to cluster these segments into putative domain families. The selection of the best putative families is done using machine learning techniques. A statistical model is then created for each of the chosen families. This procedure is then iterated: the aforementioned statistical models are used to scan all protein sequences, to recreate a library of segments and to cluster them again. RESULTS: Processing the Swiss-Prot section of the UniProt Knoledgebase, release 7.2, EVEREST defines 20,230 domains, covering 85% of the amino acids of the Swiss-Prot database. EVEREST annotates 11,852 proteins (6% of the database) that are not annotated by Pfam A. In addition, in 43,086 proteins (20% of the database), EVEREST annotates a part of the protein that is not annotated by Pfam A. Performance tests show that EVEREST recovers 56% of Pfam A families and 63% of SCOP families with high accuracy, and suggests previously unknown domain families with at least 51% fidelity. EVEREST domains are often a combination of domains as defined by Pfam or SCOP and are frequently sub-domains of such domains. CONCLUSION: The EVEREST process and its output domain families provide an exhaustive and validated view of the protein domain world that is automatically generated from sequence data. The EVEREST library of domain families, accessible for browsing and download at 1, provides a complementary view to that provided by other existing libraries. Furthermore, since it is automatic, the EVEREST process is scalable and we will run it in the future on larger databases as well. The EVEREST source files are available for download from the EVEREST web site.

We present a new explicit construction for expander graphs with nearly optimal spectral gap. The construction is based on a series of 2-lift operations. Let G be a graph on n vertices. A 2-lift of G is a graph H on 2n vertices, with a covering map /spl pi/ : H /spl rarr/ G. It is not hard to see that all eigenvalues of G are also eigenvalues of H. In addition, H has n "new" eigenvalues. We conjecture that every d-regular graph has a 2-lift such that all new eigenvalues are in the range [-2/spl radic/d-1, /spl radic/d-1] (If true, this is tight , e.g. by the Alon-Boppana bound). Here we show that every graph of maximal degree d has a 2-lift such that all "new" eigenvalues are in the range [-c/spl radic/d log/sup 3/d, c/spl radic/d log/sup 3/ d] for some constant c. This leads to a polynomial time algorithm for constructing arbitrarily large d-regular graphs, with second eigenvalue O(/spl radic/d log/sup 3/ d). The proof uses the following lemma (Lemma 3.6): Let A be a real symmetric matrix with zeros on the diagonal. Let d be such that the l/sub 1/ norm of each row in A is at most d. Suppose that (|xAy|)/(/spl par/x/spl par//spl par/y/spl par/) /spl les/ /spl alpha/ for every x,y /spl isin/ {0, l}/sup n/ with (x,y)= 0. Then the spectral radius of A is O(/spl alpha/(log(d//spl alpha/) + 1)). An interesting consequence of this lemma is a converse to the expander mixing lemma.

This paper deals with Ramsey-type theorems for metric spaces. Such a theorem states that every n point metric space contains a large subspace which can be embedded with some fixed distortion in a metric space from some special class.Our main theorem states that for any ε>0, every n point metric space contains a subspace of size at least n1-ε which is embeddable in an ultrametric with O(log(1/ε)/ε distortion. This in particular provides a bound for embedding in Euclidean spaces. The bound on the distortion is tight up to the log(1/ε) factor even for embedding in arbitrary Euclidean spaces. This result can be viewed as a non-linear analog of Dvoretzky's theorem, a cornerstone of modern Banach space theory and convex geometry.Our main Ramsey-type theorem and techniques naturally extend to give theorems for classes of hierarchically well-separated trees which have algorithmic implications, and can be viewed as the solution of a natural clustering problem.We further include a comprehensive study of various other aspects of the metric Ramsey problem.

(MATH) In the one-round Voronoi game, the first player chooses an n-point set $\PFRST$ in a square $Q$, and then the second player places another n-point set $\PSCND$ into $Q$. The payoff for the second player is the fraction of the area of $Q$ occupied by the regions of the points of $\PSCND$ in the Voronoi diagram of $\PFRST\cup\PSCND$. We give a strategy for the second player that always guarantees him a payoff of at least $\frac12+\alpha$, for a constant $\alpha>0$ independent of n. This contrasts with the one-dimensional situation, with $Q=[0,1]$, where the first player can always win more than 1/2.

In the last several years a number of very interesting results were proved about finite metric spaces. Some of this work is motivated by practical considerations: Large data sets (coming e.g. from computational molecular biology, brain research or data mining) can be viewed as large metric spaces that should be analyzed (e.g. correctly clustered).On the other hand, these investigations connect to some classical areas of geometry - the asymptotic theory of finite-dimensional normed spaces and differential geometry. Finally, the metric theory of finite graphs has proved very useful in the study of graphs per se and the design of approximation algorithms for hard computational problems. In this talk I will try to explain some of the results and review some of the emerging new connections and the many fascinating open problems in this area.

Abstract Motivation: A large fraction of biological research concentrates on individual proteins and on small families of proteins. One of the current major challenges in bioinformatics is to extend our knowledge to very large sets of proteins. Several major projects have tackled this problem. Such undertakings usually start with a process that clusters all known proteins or large subsets of this space. Some work in this area is carried out automatically, while other attempts incorporate expert advice and annotation. Results: We propose a novel technique that automatically clusters protein sequences. We consider all proteins in SWISSPROT, and carry out an all-against-all BLAST similarity test among them. With this similarity measure in hand we proceed to perform a continuous bottom-up clustering process by applying alternative rules for merging clusters. The outcome of this clustering process is a classification of the input proteins into a hierarchy of clusters of varying degrees of granularity. Here we compare the clusters that result from alternative merging rules, and validate the results against InterPro. Our preliminary results show that clusters that are consistent with several rather than a single merging rule tend to comply with InterPro annotation. This is an affirmation of the view that the protein space consists of families that differ markedly in their evolutionary conservation. Availability: The outcome of these investigations can be viewed in an interactive Web site at http://www.protonet.cs.huji.ac.il Supplementary information: Biological examples for comparing the performance of the different algorithms used for classification are presented in http://www.protonet.cs.huji.ac.il/examples.html Contact: [email protected] Keywords: protein families; protein classification; sequence alignment; clustering.

(MATH) In this paper we partially prove a conjecture that was raised by Linial, London and Rabinovich in \cite{llr}. Let $G$ be a $k$-regular graph, $k \ge 3$, with girth $g$. We show that every embedding $f : G \to \ell_2$ has distortion $\Omega (\sqrt{g})$. The original conjecture which remains open is that the Euclidean distortion is bounded below by $\Omega(g)$. Two proofs are given, one based on semi-definite programming, and the other on Markov Type, a concept that considers random walks on metrics.

Let $D \subseteq \Sigma^n$ be a dictionary. We look for efficient data structures and algorithms to solve the following approximate query problem: Given a query $u \in \Sigma^n$ list all words $v \in D$ that are close to u in Hamming distance. The problem reduces to the following combinatorial problem: Hash the vertices of the n-dimensional hypercube into buckets so that (1) the c-neighborhood of each vertex is mapped into at most k buckets and (2) no bucket is too large. Lower and upper bounds are given for the tradeoff between k and the size of the largest bucket. These results are used to derive bounds for the approximate query problem.

Introduction There has been a growing interest in finite metric spaces and their approximations. Such considerations have proved useful in a number of graph algorithms [13], in clustering [11] and most recently in online computation [2, 3]. To study a given metric space, one seeks first an approximate metric from a better-understood class of metrics. Thus, approximations by l 1 metrics are instrumental in the study of multicommodity flows Institute of Computer Science, Hebrew University, Jerusalem 91904, Israel. E-mail: [email protected]. Supported in part by grants from the Israeli Academy of Sciences and the US-Israel Binational Science Foundation Israel-USA. y Institute of Computer Science, Hebrew University, Jerusalem 91904, Israel. E-mail: [email protected]. z Department of Mathematics, Rutgers University, Hill Center, 110 Frelinghuysen Road, Piscataway, NJ 08854. Supported in part by NSF under gran

We present a deterministic strongly polynomial algorithm that computes the permanent of a nonnegativo n x m matrix to within a multiplicative factor of e".To thii end we develop the first strongly polynomial time algorithm for matrix scaling -an important nonlinear optimization problem with many applications.Our work suggests a (slow) decision algorithm for bipartite perfect matching, conceptually different from known approaches.

We initiate an investigation of general fault-tolerant distributed computation in the full-information model. In the full information model no restrictions are made on the computational power of the faulty parties or the information available to them. (Namely, the faulty players may be infinitely powerful and there are no private channels connecting pairs of honest players). Previous work in this model has concentrated on the particular problem of simulating a single bounded-bias global coin flip (e.g., Ben-Or and Linial [Randomness and Computation, S. Micali, ed., JAI Press, Greenwich, CT, 1989, pp. 91--115] and Alon and Naor [SIAM J. Comput., 22 (1993), pp. 403--417]). We widen the scope of investigation to the general question of how well arbitrary fault-tolerant computations can be performed in this model. The results we obtain should be considered as first steps in this direction. We present efficient two-party protocols for fault-tolerant computation of any bivariate function. We prove that the advantage of a dishonest player in these protocols is the minimum one possible (up to polylogarithmic factors). We also present efficient m-party fault-tolerant protocols for sampling a general distribution (\mbox{$m\geq2$}). Such an algorithm seems an important building block towards the design of efficient multiparty protocols for fault-tolerant computation of multivariate functions.

A linear array network consists of k + 1 processors P 0 ; P 1 ; : : : ; P k with links only between P i and P i+1 (0 i ! k). It is required to compute some boolean function f(x; y) in this network, where initially x is stored at P 0 and y is stored at P k . Let D k (f) be the (total) number of bits that must be exchanged to compute f in worst case. Clearly, D k (f) k \\Delta D(f ), where D(f) is the standard two-party communication complexity of f . Tiwari proved that for almost all functions D k (f) k(D(f) \\Gamma O(1)) and conjectured that this is true for all functions. In this paper we disprove Tiwari's conjecture, by exhibiting an infinite family of functions for which D k (f) is essentially at most 3 4 k \\Delta D(f ). Our construction also leads to progress on another major problem in this area: It is easy to bound the two-party communication complexity of any function, given the least number of monochromatic rectangles in any partition of the input space. How tight are suc...

In a non-e~pansive hashing scheme, similar inputs are stored in memory locations which are close.We develop a non-expansive hashing scheme wherein any set of size O (R1-C) from a large universe may be stored in a memory of size R (any e > 0, and R > Ro(c)), and where ret rieval takes O(1) operations.We explain how to use non-expansive hashing schemes for efficient storage and retrieval of noisy data.A dynamic version of this hashing scheme is presented as well.

The distinct distribution of a binary code C is the sequence (B/sub i/)/sub i=0//sup n/ defined as follows: let B/sub i/(w) be the number of codewords at distance i from the codeword w, and let B/sub i/ be the average of B/sub i/(w) over all w in C. In this correspondence we study the distance distribution for codes of length n and minimal distance /spl delta/n, with /spl delta/>0 fixed and n/spl rarr//spl infin/. Our main aim is to relate the size of the code with the distribution of distances near the minimal distance.>

We explore some implications of viewing graphs as geometric objects. This approach offers a new perspective on a number of graph-theoretic and algorithmic problems. There are several ways to model graphs geometrically and our main concern here is with geometric representations that respect the metric of the (possibly weighted) graph. Given a graph G we map its vertices to a normed space in an attempt to (i) Keep down the dimension of the host space and (ii) Guarantee a small distortion, i.e., make sure that distances between vertices in G closely match the distances between their geometric images. We develop efficient algorithms for embedding graphs low-dimensionally with a small distortion.>

In this paper we develop a leader election protocol P with the following features: *

Given d, m and c, we deterministically produce a sequence of points S that hits every combinatorial rectangle in [m]d of volume at least 6.Both the running time of the algorithm and ISI are polynomial in m log(d) /c.This algorithm has applications to deterministic constructions of small sample spaces for general multivalued random variables.

In this paper, Boolean functions in ,4C0 are studied using harmonic analysis on the cube.The main result is that an ACO Boolean function has almost all of its "power spectrum" on the low-order coefficients.An important ingredient of the proof is Hastad's switching lemma [8].This result implies several new properties of functions in -4C[': Functions in AC() have low "average sensitivity;" they may be approximated well by a real polynomial of low degree and they cannot be pseudorandom function generators.Perhaps the most interesting application is an O(n POIYIOg(n ')-time algorithm for learning functions in ACO.The algorithm observes the behavior of an AC'" function on O(nPO'Y'Og(n)) randomly chosen inputs, and derives a good approximation for the Fourier transform of the function.This approximation allows the algorithm to predict, with high probability, the value of the function on other randomly chosen inputs.

A shared directional multichannel (SDM) consists of a set of inputs and a set of outputs to which transmitters and receivers respectively, are connected. A signal placed at any given input reaches a subset of the outputs, and a channel is specified by the sets of outputs that are reachable from each input. A message is received successfully at an output of the channel if and only if it is addressed to the receiver connected to that output and no other signals reach that output at the same time. Constructive lower bounds as well as some upper bounds on the uniform-traffic capacity of SDM-based single-hop interconnections between a set of multitransmitter source stations and a set of multireceiver destination stations are derived. A bidirectional interconnection among a set of stations can be obtained by representing each station as one source station and one destination station. It is shown that with randomized transmissions, SDMs that can be described as a collection of buses can perform as well as any other channels. With deterministic scheduling, however, the use of certain non-bus-oriented SDMs yields a much higher interconnection capacity.>

How much can an imperfect source of randomness affect an algorithm? We examine several simple questions of this type concerning the long-term behavior of a random walk on a finite graph. In our setup, each step of the random walk a “controller” can, with a certain small probability, fix the next step, thus introducing a bias. We analyze the extent to which the bias can affect the limit behavior of the walk. The controller is assumed to associate a real, nonnegative, “benefit” with each state, and to strive to maximize the long-term expected benefit. We derive tight bounds on the maximum of this objective function over all controller's strategies, and present polynomial time algorithms for computing the optimal controller strategy.

In practice, almost all dynamic systems require decisions to be made on-line, without full knowledge of their future impact on the system. A general model for the processing of sequences of tasks is introduced, and a general on-line decision algorithm is developed. It is shown that, for an important class of special cases, this algorithm is optimal among all on-line algorithms. Specifically, a task system ( S,d ) for processing sequences of tasks consists of a set S of states and a cost matrix d where d ( i, j is the cost of changing from state i to state j (we assume that d satisfies the triangle inequality and all diagonal entries are 0). The cost of processing a given task depends on the state of the system. A schedule for a sequence T 1 , T 2 ,…, T k of tasks is a sequence s 1 , s 2 ,…, s k of states where s i is the state in which T i is processed; the cost of a schedule is the sum of all task processing costs and the state transition costs incurred. An on-line scheduling algorithm is one that chooses s i only knowing T 1 T 2 … T i . Such an algorithm is w -competitive if, on any input task sequence, its cost is within an additive constant of w times the optimal offline schedule cost. The competitive ratio w ( S , d ) is the infimum w for which there is a w -competitive on-line scheduling algorithm for ( S , d ). It is shown that w ( S , d ) = 2|S|–1 for every task system in which d is symmetric, and w ( S, d ) = O (| S | 2 ) for every task system. Finally, randomized on-line scheduling algorithms are introduced. It is shown that for the uniform task system (in which d ( i,j ) = 1 for all i,j ), the expected competitive ratio w¯ ( S,d ) = O (log|S|).

This paper concerns a number of algorithmic problems on graphs and how they may be solved in a distributed fashion. The computational model is such that each node of the graph is occupied by a processor which has its own ID. Processors are restricted to collecting data from others which are at a distance at most t away from them in t time units, but are otherwise computationally unbounded. This model focuses on the issue of locality in distributed processing, namely, to what extent a global solution to a computational problem can be obtained from locally available data. Three results are proved within this model: • A 3-coloring of an n-cycle requires time $\Omega (\log ^ * n)$. This bound is tight, by previous work of Cole and Vishkin. • Any algorithm for coloring the d-regular tree of radius r which runs for time at most $2r/3$ requires at least $\Omega (\sqrt d )$ colors. • In an n-vertex graph of largest degree $\Delta $, an $O(\Delta ^2 )$-coloring may be found in time $O(\log ^ * n)$.

Efficient two-party protocols for fault-tolerant computation of any two-argument function are presented. It is proved that the influence of a dishonest player in these protocols is the minimum one possible (up to polylogarithmic factors). Also presented are efficient m-party fault-tolerant protocols for sampling a general distribution (m>or=2). Efficient m-party protocols for computation of any m-argument function are given, and it is proved for these protocols that for most functions, the influence of any t dishonest players on the outcome of the protocol is the minimum one possible (up to polylogarithmic factors).>

The Inclusion-Exclusion formula expresses the size of a union of a family of sets in terms of the sizes of intersections of all subfamilies.This paper considers approximating the size of the union when intersection sizes are known for only some of the subfamilies, or when these quantities are given to within some error, or both.In particular, we consider the case when all k-wise intersections axe given for every k < K.It turns out that the answer changes in a significant way around g = V/'ff : if K < O(v/-ff) then any approximation may err by a factor of O(n/K2), while if K > ft(v/'ff ) it is shown how to approximate the size of the union_to within a multiplicative factor of 1 :t: e -a(g/'/'a).When the sizes of all intersections are only given approximately, good bounds are derived on how well the size of the union may be approximated.Several applications for boolean function are mentioned in conclusion.

Boolean functions in AC/sup O/ are studied using the harmonic analysis of the cube. The main result is that an AC/sup O/ Boolean function has almost all of its power spectrum on the low-order coefficients. This result implies the following properties of functions in AC/sup O/: functions in AC/sup O/ have low average sensitivity; they can be approximated well be a real polynomial of low degree; they cannot be pseudorandom function generators and their correlation with any polylog-wide independent probability distribution is small. An O(n/sup polylog(/ /sup sup)/ /sup (n)/)-time algorithm for learning functions in AC/sup O/ is obtained. The algorithm observed the behavior of an AC/sup O/ function on O(n/sup polylog/ /sup (n)/) randomly chosen inputs and derives a good approximation for the Fourier transform of the function. This allows it to predict with high probability the value of the function on other randomly chosen inputs.>

The problem of computing the chromatic number of a graph is considered. No known approximation algorithm can guarantee a better than O(n/sup 0.4/) coloring on a three-chromatic graph with n vertices. Evidence is provided that it is inherently impossible to achieve a better than n/sup epsilon / ratio in polynomial time by showing that 'breaking the n/sup epsilon / barrier' will automatically lead to vastly better polynomial-time approximation algorithms that achieve ratios closer to log n.>

A radio network is a synchronous network of processors that communicate by transmitting messages to their neighbors. A processor receives a message in a given step if and only if it is silent then and precisely one of its neighbors transmits. This stringent rule poses serious difficulties in performing even the simplest tasks. This is true even under the overly optimistic assumptions of centralized coordination and complete knowledge of the network topology. This paper is concerned with lower and upper bounds for the complexity of realizing various communication primitives for radio networks.

In designing a routing scheme for a communication network it is desirable to use as short as possible paths for routing messages, while keeping the routing information stored in the processors' local memory as succinct as possible. The efficiency of a routing scheme is measured in terms of its stretch factor - the maximum ratio between the cost of a route computed by the scheme and that of a cheapest path connecting the same pair of vertices.

Universal sequences for graphs, a concept introduced by Aleliunas [M.Sc. thesis, University of Toronto, Toronto, Ontario, Canada, January 1978] and Aleliunas et al. [Proc. 20th Annual Symposium on Foundation of Computer Science, 1979, pp. 218–223] are studied. By letting $U(d,n)$ denote the minimum length of a universal sequence for d-regular undirected graphs with n nodes, the latter paper has proved the upper bound $U(d,n) = O(d^2 n^3 \log n)$ using a probabilistic argument. Here a lower bound of $U(2,n) = \Omega (n\log n)$ is proved from which $U(d,n) = \Omega (n\log n)$ for all d is deduced. Also, for complete graphs $U(n - 1,n) = \Omega ({{n\log ^2 n} / {\log \log n}})$. An explicit construction of universal sequences for cycles $(d = 2)$ of length $n^{O(\log n)} $ is given.

Methods from harmonic analysis are used to prove some general theorems on Boolean functions. These connections with harmonic analysis viewed by the authors are very promising; besides the results on Boolean functions they enable them to prove theorems on the rapid mixing of the random walk on the cube and in the extremal theory of finite sets.>

The problem of learning a concept from examples in a distribution-free model is considered. The notion of dynamic sampling, wherein the number of examples examined can increase with the complexity of the target concept, is introduced. This method is used to establish the learnability of various concept classes with an infinite Vapnik-Chervonenkis (VC) dimension. An important variation on the problem of learning from examples, called approximating from examples, is also discussed. The problem of computing the VC dimension of a finite concept set defined on a finite domain is considered.>

This paper deals with distributed graph algorithms. Processors reside in the vertices of a graph G and communicate only with their neighbors. The system is synchronous and reliable, there is no limit on message lengths and local computation is instantaneous. The results: A maximal independent set in an n-cycle cannot be found faster than Ω(log* n) and this is optimal by [CV]. The d-regular tree of radius r cannot be colored with fewer than √d colors in time 2r / 3. If Δ is the largest degree in G which has order n, then in time O(log*n) it can be colored with O(Δ2) colors.

In practice, almost all dynamic systems require decisions to be made online, without full knowledge of their future impact on the system. We introduce a general model for the processing of sequences of tasks and develop a general online decision algorithm. We show that, for an important class of special cases, this algorithm is optimal among all online algorithms.

We consider a simple model for a class of discrete control processes, motivated in part by recent work about the behavior of imperfect random sources in computer algorithms. The process produces a string of characters from {0, 1} of length n and is a “success” or “failure” depending on whether the string produced belongs to a prespecified set L. In an uninfluenced process each character is chosen by a fair coin toss, and hence the probability of success is |L|/2n. We are interested in the effect on the probability of success in the presence of a player (controller) who can intervene in the process by specifying the value of certain characters in the string. We answer the following questions in both worst and average case: (1) how much can the player increase the probability of success given a fixed number of interventions? (2) in terms of |L| what is the expected number of interventions needed to guarantee success? In particular our results imply that if |L|/2n = 1/w(n) where w(n) tends to infinity with n (so the probability of success with no interventions is o(1)) then with Ο(√nlogw(n)) interventions the probability of success is 1-o(1).

In this paper we propose two new multi-layer grid models for VLSI layout, both of which take into account the number of contact cuts used. For the first model in which nodes "exist" only on one layer, we prove a tight area x (number of contact cuts) = Θ(n2) trade-off for embedding any degree 4 n-node planar graph in two layers. For the second model in which nodes "exist" simultaneously on all layers, we prove a number of bounds on the area needed to embed graphs using no contact cuts. For example we prove that any n-node graph which is the union of two planar subgraphs can be embedded on two layers in O(n2) area without contact cuts. This bound is tight even if more layers and an unbounded number of contact cuts are allowed. We also show that planar graphs of bounded degree can be embedded on two layers in O(n1.6) area without contact cuts. These results use some interesting new results on embedding graphs in a single layer. In particular we give an O(n2) area embedding of planar graphs such that each edge makes a constant number of turns, and each exterior vertex has a path to the perimeter of the grid making a constant number of turns. We also prove a tight Ω(n3) lower bound on the area of grid n-permutation networks.

The power of players in a collective decision process is a central issue in Mathematical Economics and Game Theory. Similar issues arise in Computer Science in the study of distributed, fault tolerant computations when several processes, some perhaps faulty, have to reach agreement. In the present article we study voting schemes which are relatively immune to the presence of unfair players. In particular, we discuss how to perform collective coin flipping which is only slightly biased despite the presence of unfair players. Mathematically this corresponds to problems concerning the minima of Banzhaf values in certain n -person games. These are measures of power studied in Game Theory. It is quite remarkable that while dictatorial voting games are, of course, the most sensitive to the presence of unfair players, some voting schemes that we propose here are significantly more robust than majority voting. Coin flipping was selected as a study case because of its simplicity and because collective coin flipping is widely used in randomized algorithms for distributed computations. It is our feeling that Game Theory has much to contribute to Computer Science and we are sure that further applications will be found.

We consider dual pairs of packing and covering integer linear programs. Best possible bounds are found between their optimal values. Tight inequalities are obtained relating the integral optima and the optimal rational solutions.

Let $A = (a_1 > \cdots > a_m )$ and $B = (b_1 > \cdots > b_n )$ be given ordered lists: also let there be given some order relations between $a_i $’s and $b_j $’s. Suppose that an unknown total order exists on $A \cup B$ which is consistent with all these relations ($ = a$ linear extension of the partial order) and we wish to find out this total order by comparing pairs of elements $a_t :b_s $. If the partial order has N linear extensions, then the Information Theoretic Bound says that $\log _2 N$ steps will be required in the worst case from any such algorithm. In this paper we show that there exists an algorithm which will take no more than $C\log _2 N$ comparisons where $C = (\log _2 ((\sqrt 5 + 1)/ 2))^{ -1} $. The computation required to determine the pair $a_t :b_s $ to be compared has length polynomial in $(m + n)$. The constant C is best possible. Many related results are reviewed.

The following computational problem was initiated by Manber and Tompa (22nd FOCS Conference, 1981) : Given a graph G = (V,E) and a real function f : V→R which is a proposed vertex coloring. Decide whether f is a proper vertex coloring of G. The elementary steps are taken to be linear comparisons. Lower bounds on the complexity of this problem are derived using the chromatic polynomial of G. It is shown how geometric parameters of a space partition associated with G influence the complexity of this problem. In particular we show (theorem 6) a lower bound of (m/2)1/2 log m + O(m1/2), where m is the number of edges of the graph in question. Existing methods for analyzing such space partitions are suggested as a powerful tool for establishing lower bounds for a variety of computational problems. Many interesting open problems are presented.

The complexity of the search problem for a very broad class of data structures is estimated. The lower (Information Theoretic) bound and the upper bound differ by a small multiplicative constant.

We find the optimal algorithm in the sense of average run time for the counterfeit coin problem: Given n coins, one of which is heavier or lighter than the rest. Using a balance scale, find the counterfeit coin and whether it is heavy or light. An interesting feature of the solution is that our algorithm is a straight line algorithm. We also find the optimal algorithm if a standard coin is available for the first weighing.