Are stable instances easy? (2009)
We introduce the notion of a stable instance for a discrete optimization problem, and argue that in many practical situations only sufficiently stable instances are of interest. The question then...
The expected genus of a random chord diagram (2009)
To any generic curve in an oriented surface there corresponds an oriented chord diagram, and any oriented chord diagram may be realized by a curve in some oriented surface. The genus of an oriented...
Sum complexes - a new family of hypertrees (2009)
Linial, Nathan, Meshulam, Roy, Rosenthal, Mishael
A k-dimensional hypertree X is a k-dimensional complex on n vertices with a full (k-1)-dimensional skeleton and \binom{n-1}{k} facets such that H_k(X;Q)=0. Here we introduce the following family of...
Elon Portugaly, Nathan Linial, Michal Linial
collection of evolutionary conserved protein domains
Abstract On the Complexity of Radio Communication (Extended Abstract) (2008)
Noga Alon, Amotz Bar-noy, Nathan Linial, David Peleg
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...
Assessment of Protein Domain Classifications: SCOP, CATH, Dali and EVEREST (2008)
Elon Portugaly, Nathan Linial, Michal Linial
In recent years, we witness an enormous increase in the number proteins that are structurally solved at high resolution. To get a coherent perspective on
ProtoNet: Navigating the Hierarchical Clustering of the Protein Space (2008)
Ori Sasson, Hillel Fleischer, Elon Portugaly, Yonatan Bilu, Nathan Linial, Michal Linial
The ProtoNet site provides an automatic hierarchical clustering of the protein space. The clustering is based on an all-against-all BLAST similarity test. With this similarity measure we proceed to...
Menachem Fromer, Moriah Friedlich, Noam Kaplan, Nathan Linial, Michal Linial
32,840 characters (including spaces) 20 pages
Eigenvectors of random graphs: Nodal domains (2008)
Dekel, Yael, Lee, James R., Linial, Nathan
We initiate a systematic study of eigenvectors of random graphs. Whereas much is known about eigenvalues of graphs and how they reflect properties of the underlying graph, relatively little is known...
112. Structure from sequence: A view based on a global organization of the protein space (2008)
Ori Shachar, Elon Portugaly, Nathan Linial, Michal Linial
modeling
Nathan Linial, Michael Saks, David Statter
Two sets are non-crossing if they are disjoint or one contains the other. The noncrossing graph NCn is the graph whose vertex set is the set of nonempty subsets of [n] ={1,...,n} with an edge between...
Elon Portugaly, Nathan Linial, Michal Linial
Background: SCOP is a manual classification of protein domain structures. CATH is a classification of protein domain structures created through a combination of manual and automatic methods. The Dali...
Elon Portugaly, Nathan Linial, Michal Linial
collection of evolutionary conserved protein domains
For a graph G, a random n-lift of G has the vertex set V (G) \Theta [n] and for each edge [u; v] 2 E(G), there is a random matching between fug \Theta [n] and fvg \Theta [n]. We present bounds on the...
In the one-round Voronoi game, the F R ST player places n sites inside a unit-square Q. Next, the SCN D player places n points inside Q. The payoff for a player is the total area of the Voronoi...
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
In this note, we consider the metric Ramsey problem for the normed spaces # p. Namely, given some 1
Yair Bartal, Nathan Linial, Assaf Naor
The main question studied in this article may be viewed as a non-linear analog of Dvoretzky's Theorem in Banach space theory or as part of Ramsey Theory in combinatorics. Given a nite metric...
Homological Connectivity of Random 2-Complexes (2007)
Let # n-1 denote the (n- 1)-dimensional simplex. Let Y be a random 2-dimensional subcomplex of # n-1 obtained by starting with the full 1-dimensional skeleton of # n-1 and then adding each 2-simplex...
For a graph G, a random n-lift of G has the vertex set V (G) [n] and for each edge [u; v] 2 E(G), there is a random matching between fug [n] and fvg [n]. We present bounds on the chromatic number and...
Supported in part by BSF and by the Israeli academy of sciences. y
Otfried Cheong, Nathan Linial, Jip F Matougek
In the one-round Voronoi game, the first player chooses an n-point set]42 in a square Q, and then tile second player places another n-point set /3 into Q. Tile payoff for thc sccond playcr is thc...
Colorings of the d-regular innite tree (2007)
The existence of small d-regular graphs of a prescribed girth g is equivalent to the existence of certain codes in the d-regular innite tree. We show that in the tree \perfect " codes exist,...
Colorings of the d-regular innite tree (2007)
The existence of small d-regular graphs of a prescribed girth g is equivalent to the existence of certain codes in the d-regular innite tree. We show that in the tree \perfect " codes exist,...
Central points for sets in R n (or: The Chocolate Ice-Cream Problem) (2007)
Let A be a subset of the unit ball in R n, and 0 r 1 real. Find a point x for which the intersection of the r-neighborhood of x with A has a large measure. Tight bounds on this measure are found. 1
Nathan Linial, Avner Magen, Michael E. Saks
In order to study a finite metric space (X; d), one often seeks first an approximation in the form of a metric that is induced from a norm. The quality of such an approximation is quantified by the...
Random Lifts of Graphs I: General Theory and Graph Connectivity (2007)
In this paper we describe a simple model for random graphs that have an n-fold covering map onto a xed nite base graph. Roughly, given a base graph G and an integer n, we form a random graph by...
For a graph G, a random n-lift of G has the vertex set V (G) [n] and for each edge [u; v] 2 E(G), there is a random matching between fug [n] and fvg [n]. We present bounds on the chromatic number and...
Bourgain [1] showed that every embedding of the complete binary tree of depth n into l 2 has metric distortion
Supported in part by BSF and by the Israeli academy of sciences.
The Influence of Variables on Boolean Functions (Extended Abstract) (2007)
Jeff Kahn, Gil Kalai, Nathan Linial
This paper applies methods from harmonic analysis to prove some general theorems on boolean functions. The result that is easiest to describe says that "Boolean functions always have small...
A counterexample to a conjecture of Lovasz on the -coloring (2007)
Complex Shlomo Hoory, Shlomo Hoory, Nathan Linial
Associated with every graph G of chromatic number is another graph G . The vertex set of G consists of all -colorings of G, and two -colorings are adjacent when they dier on exactly one vertex....
Essential Covers of the Cube By Hyperplanes (2007)
Nathan Linial, Jaikumar Radhakrishnan
A set L of linear polynomials in variables X 1 ; X 2 ; : : : ; X n with real coecients is said to be an essential cover of the cube f0; 1g (E1) For each v 2 f0; 1g , there is a p 2 L such that p(v) =...
Yair Bartal, Nathan Linial, Assaf Naor
The main question studied in this article may be viewed as a non-linear analog of Dvoretzky's Theorem in Banach space theory or as part of Ramsey Theory in combinatorics. Given a nite metric...
Otfried Cheong, Sariel Har-peled, Nathan Linial
In the one-round Voronoi game, the rst player chooses an n-point set W in a square Q, and then the second player places another n-point set B into Q. The payo for the second player is the fraction of...
Vol Suppl Pages, Ori Sasson, Nathan Linial, Michal Linial
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...
Annals of Mathematics, 162 (2005), 643–710 On metric Ramsey-type phenomena (2007)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
The main question studied in this article may be viewed as a nonlinear analogue of Dvoretzky’s theorem in Banach space theory or as part of Ramsey theory in combinatorics. Given a finite metric...
Nathan Linial, Or Sheffet, Gábor Tardos
For a graph G and an integer t we let mcct(G) be the smallest m such that there exists a coloring of the vertices of G by t colors with no monochromatic connected subgraph having more than m...
EVEREST: a collection of evolutionary conserved protein domains (2007)
Portugaly, Elon, Linial, Nathan, Linial, Michal
Protein domains are subunits of proteins that recur throughout the protein world. There are many definitions attempting to capture the essence of a protein domain, and several systems that identify...
Portugaly, Elon, Harel, Amir, Linial, Nathan, Linial, Michal
Abstract 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...
EVEREST: a collection of evolutionary conserved protein (2006)
Elon Portugaly, Nathan Linial, Michal Linial
domains
DRAFT-- DRAFT-- DRAFT-- DRAFT-- DRAFT-- DRAFT-- DRAFT-- DRAFT-- DRAFT-- DRAFT-- (2006)
Shlomo Hoory, Nathan Linial, Avi Wigderson, An Overview
A major consideration we had in writing this survey was to make it accessible to mathematicians as well as computer scientists, since expander graphs, the protagonists of our story come up in...
Expander graphs and their applications (2006)
Shlomo Hoory, Nathan Linial, Avi Wigderson, An Overview
A major consideration we had in writing this survey was to make it accessible to mathematicians as well as to computer scientists, since expander graphs, the protagonists of our story, come up in...
How neighborly can a centrally symmetric polytope be (2006)
Abstract. We show that there exist k-neighborly centrally symmetric ddimensional polytopes with 2(n + d) vertices, where
DRAFT-- DRAFT-- DRAFT-- DRAFT-- DRAFT-- (2006)
Shlomo Hoory, Nathan Linial, Avi Wigderson, An Overview
A major consideration we had in writing this survey was to make it accessible to mathematicians as well as computer scientists, since expander graphs, the protagonists of our story come up in...
EVEREST: a collection of evolutionary conserved protein domains (2006)
Portugaly, Elon, Linial, Nathan, Linial, Michal
Protein domains are subunits of proteins that recur throughout the protein world. There are many definitions attempting to capture the essence of a protein domain, and several systems that identify...
EVEREST: a collection of evolutionary conserved protein domains (2006)
Portugaly, Elon, Linial, Nathan, Linial, Michal
Protein domains are subunits of proteins that recur throughout the protein world. There are many definitions attempting to capture the essence of a protein domain, and several systems that identify...
On metric Ramsey-type phenomena (2005)
Bartal, Yair, Linial, Nathan, Mendel, Manor, Naor, Assaf
The main question studied in this article may be viewed as a nonlinear analogue of Dvoretzky's theorem in Banach space theory or as part of Ramsey theory in combinatorics. Given a finite metric space...
How neighborly can a centrally symmetric polytope be? (2005)
Linial, Nathan, Novik, Isabella
We show that there exist k-neighborly centrally symmetric d-dimensional polytopes with 2(n+d) vertices, where k(d,n)=Theta(d/(1+log ((d+n)/d))). We also show that this bound is tight.
On metric Ramsey-type phenomena (2005)
Mendel, Manor, Naor, Assaf, Linial, Nathan, Bartal, Yair
The main question studied in this article may be viewed as a nonlinear analogue of Dvoretzky¿s theorem in Banach space theory or as part of Ramsey theory in combinatorics. Given a finite metric...
Efficient calculation of interval scores for dna copy number data analysis (2005)
Doron Lipson, Yonatan Aumann, Amir Ben-dor, Nathan Linial, Zohar Yakhini
Background. DNA amplifications and deletions characterize cancer genome and are often related to disease evolution. Microarray based techniques for measuring these DNA copy-number changes use...
ProtoNet 4.0: A hierarchical classification of one (2005)
Million Protein Sequences, Noam Kaplan, Ori Sasson, Uri Inbar, Moriah Friedlich, Menachem Fromer, ...
ProtoNet is an automatic hierarchical classification of the protein sequence space. In 2004, the ProtoNet (version 4.0) presents the analysis of over one million proteins merged from SwissProt and...
Fabian Kuhn, Dipl Inf. -ing, Eth Zürich, Waltenschwil Ag, Prof Dr, Roger Wattenhofer, ...
born 30.07.1976 citizen of
Efficient calculation of interval scores for dna copy number data analysis (2005)
Doron Lipson, Yonatan Aumann, Amir Ben-dor, Nathan Linial, Zohar Yakhini
Background. DNA amplifications and deletions characterize cancer genome and are often related to disease evolution. Microarray based techniques for measuring these DNA copy-number changes use...
Protonet 4.0: A hierarchical classification of one million protein sequences (2005)
Ori Sasson, Uri Inbar, Moriah Friedlich, Hillel Fleischer, Elon Portugaly, Nathan Linial, ...
ProtoNet is an automatic hierarchical classification of the protein sequence space. In 2004 the ProtoNet (version 4.0) presents the analysis of over one million proteins merged from SwissProt and...
On the expansion rate of Margulis expanders (2005)
In this note we determine exactly the expansion rate of an infinite 4-regular expander graph which is a variant of an expander due to Margulis. The vertex set of this graph consists of all points in...
ProtoNet 4.0: A hierarchical classification of one million protein sequences (2005)
Kaplan, Noam, Sasson, Ori, Inbar, Uri, Friedlich, Moriah, Fromer, Menachem, Fleischer, Hillel, ...
ProtoNet is an automatic hierarchical classification of the protein sequence space. In 2004, the ProtoNet (version 4.0) presents the analysis of over one million proteins merged from SwissProt and...
Limitations to Frechet's Metric Embedding Method (2004)
Batal, Yair, Linial, Nathan, Mendel, Manor, Naor, Assaf
Frechet's classical isometric embedding argument has evolved to become a major tool in the study of metric spaces. An important example of a Frechet embedding is Bourgain's embedding. The authors...
On Metric Ramsey-type Dichotomies (2004)
Bartal, Yair, Linial, Nathan, Mendel, Manor, Naor, Assaf
The classical Ramsey theorem, states that every graph contains either a large clique or a large independent set. Here we investigate similar dichotomic phenomena in the context of finite metric...
On metric Ramsey-type phenomena (2004)
Bartal, Yair, Linial, Nathan, Mendel, Manor, Naor, Assaf
The main question studied in this article may be viewed as a nonlinear analogue of Dvoretzky's theorem in Banach space theory or as part of Ramsey theory in combinatorics. Given a finite metric space...
A counterexample to a conjecture of Bj\"{o}rner and Lov\'asz on the $\chi$-coloring complex (2004)
Associated with every graph $G$ of chromatic number $\chi$ is another graph $G'$. The vertex set of $G'$ consists of all $\chi$-colorings of $G$, and two $\chi$-colorings are adjacent when they...
The One-Round Voronoi Game (2004)
Cheong, Otfried, Har-Peled, Sariel, Linial, Nathan, Matousek, Jirí
In the one-round Voronoi game, the first player chooses an n-point set W in a square Q, and then the second player places another n-point set B into Q. The payoff for the second player is the...
Metric Embedding – Beyond onedimensional distortion, Discrete and Computational Geometry 31 (2004)
Robert Krauthgamer, Nathan Linial, Avner Magen
The extensive study of metric spaces and their embeddings has so far focused on embeddings that preserve pairwise distances. A very intriguing concept introduced by Feige [Fei00] allows us to...
ProtoNet 4.0: A hierarchical classification of one (2004)
Noam Kaplan, Ori Sasson, Uri Inbar, Moriah Friedlich, Menachem Fromer, Hillel Fleischer, ...
million protein sequences
Metric Embedding – Beyond onedimensional distortion, Discrete and Computational Geometry 31 (2004)
Robert Krauthgamer, Nathan Linial, Avner Magen
Metric spaces and their embeddings have recently played a prominent role in the development of new algorithms. So far, most of the emphasis was on embeddings that preserve pairwise distances. A very...
Metric Embedding – Beyond onedimensional distortion, Discrete and Computational Geometry 31 (2004)
Robert Krauthgamer, Nathan Linial, Avner Magen
The extensive study of metric spaces and their embeddings has so far focused on embeddings that preserve pairwise distances. A very intriguing concept introduced by Feige [Fei00] allows us to...
Lifts, discrepancy and nearly optimal spectral gaps (2004)
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...
Metric Embedding – Beyond onedimensional distortion, Discrete and Computational Geometry 31 (2004)
Robert Krauthgamer, Robert Krauthgamer, Nathan Linial, Nathan Linial, Avner Magen, Avner Magen
Metric spaces and their embeddings have recently played a prominent role in the development of new algorithms. So far, most of the emphasis was on embeddings that preserve pairwise distances. A very...
Constructing expander graphs by 2-lifts and discrepancy vs. spectral gap (2003)
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...
Finite metric spaces--combinatorics, geometry and algorithms (2003)
Finite metric spaces arise in many different contexts. Enormous bodies of data, scientific, commercial and others can often be viewed as large metric spaces. It turns out that the metric of graphs...
ProtoNet: hierarchical classification of the protein space (2003)
Ori Sasson, Avishay Vaaknin, Hillel Fleischer, Elon Portugaly, Yonatan Bilu, Nathan Linial, ...
The ProtoNet site provides an automatic hierarchical clustering of the SWISS-PROT protein database. The clustering is based on an all-against-all BLAST similarity search. The similarities ’ E-score...
Limitations to Fréchet metric embedding method (2003)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
Abstract Fr'echet's classical isometric embedding argument has evolved to become a major toolin the study of metric spaces. An important example of a Fr'echet embedding is...
ProtoNet: hierarchical classification of the protein space (2003)
Ori Sasson, Avishay Vaaknin, Hillel Fleischer, Elon Portugaly, Yonatan Bilu, Nathan Linial, ...
The ProtoNet site provides an automatic hierarchical clustering of the SWISS-PROT protein database. The clustering is based on an all-against-all BLAST similarity search. The similarities ’ E-score...
On metric Ramsey-type phenomena (2003)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
The main question studied in this article may be viewed as a non-linear analogue of Dvoretzky’s Theorem in Banach space theory or as part of Ramsey Theory in combinatorics. Given a finite metric...
Random lifts of graphs II: Edge expansion (2003)
We continue the study of random lifts of graphs initiated in [4]. Here we study the possibility of generating graphs with high edge expansion as random lifts. Along the way, we introduce the method...
Random lifts of graphs II: Edge expansion (2003)
We continue the study of random lifts of graphs initiated in [4]. Here we study the possibility of generating graphs with high edge expansion as random lifts. Along the way, we introduce the method...
On metric Ramsey-type phenomena (2003)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
The main question studied in this article may be viewed as a nonlinear analogue of Dvoretzky’s theorem in Banach space theory or as part of Ramsey theory in combinatorics. Given a finite metric...
Limitations to Fréchet's Metric Embedding Method (2003)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
Frechet's classical isometric embedding argument has evolved to become a major tool in the study of metric spaces. An important example of a Frechet embedding is Bourgain's embedding [4]....
ProtoNet: hierarchical classification of the protein space (2003)
Sasson, Ori, Vaaknin, Avishay, Fleischer, Hillel, Portugaly, Elon, Bilu, Yonatan, Linial, Nathan, ...
The ProtoNet site provides an automatic hierarchical clustering of the SWISS-PROT protein database. The clustering is based on an all-against-all BLAST similarity search. The similarities' E-score is...
Noga Alon, Nathan Linial, Amotz Bar-noy, David Peleg
A radio network is a synchronous network of processors that communicate by trans-mitting messages to their neighbors. A processor receives a message in a given step if and only if it is silent then...
The Moore bound for irregular graphs (2002)
Noga Alon, Shlomo Hoory, Nathan Linial
What is the largest number of edges in a graph of order n and girth g? For dregular graphs, essentially the best known answer is provided by the Moore bound. This result is extended here to cover...
On Metric Ramsey-type Dichotomies (2002)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
The classical Ramsey theorem, states that every graph contains either a large clique or a large independent set. Here we investigate similar dichotomic phenomena in the context of finite metric...
On Metric Ramsey-type Dichotomies (2002)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
The classical Ramsey theorem, states that every graph contains either a large clique or a large independent set. Here we investigate similar dichotomic phenomena in the context of finite metric...
Finite metric spaces - combinatorics, geometry and algorithms (2002)
The constantly intensifying ties between combinatorics and geometry are among the most signi-cant developments in Discrete Mathematics in recent years. These connections are manifold, and it is,...
Random graph coverings. I. General theory and graph connectivity (2002)
In this paper we describe a simple model for random graphs that have an n-fold covering map onto a xed nite base graph. Roughly, given a base graph G and an integer n, we form a random graph by...
The Moore bound for irregular graphs (2002)
Noga Alon, Shlomo Hoory, Nathan Linial
What is the largest number of edges in a graph of order n and girth g? For d-regular graphs, essentially the best known answer is provided by the Moore bound. This result is extended here to cover...
Girth and Euclidean distortion (2002)
Nathan Linial, Avner Magen, Assaf Naor
Let G be a k-regular graph, k 3, with girth g. We prove that every embedding f: G! `2 has distortion
The Moore bound for irregular graphs (2002)
Noga Alon, Shlomo Hoory, Nathan Linial
What is the largest number of edges in a graph of order n and girth g? For d-regular graphs, essentially the best known answer is provided by the Moore bound. This result is extended here to cover...
Girth and Euclidean distortion (2002)
Nathan Linial, Avner Magen, Assaf Naor
Let G be a k-regular graph, k 3, with girth g. We prove that every embedding f: G! `2 has distortion
The Metric Space of Proteins - Comparative Study of Clustering Algorithms (2002)
Ori Sasson, Nathan Linial, Michal Linia
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...
The one-round Voronoi game (2002)
Otfried Cheong, Nathan Linial, Sariel Har-peled
In the one-round Voronoi game, the first player chooses an n-point set W in a square Q, and then the second player places another n-point set B into Q. The payoff for the second player is the...
The one-round Voronoi game (2002)
Otfried Cheong, Nathan Linial, Sariel Har-peled
In the one-round Voronoi game, the F R ST player places n sites inside a unit-square Q. Next, the SCN D player places n points inside Q. The payoff for a player is the total area of the Voronoi...
The metric space of proteins--comparative study of clustering algorithms (2002)
Sasson, Ori, Linial, Nathan, Linial, Michal
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...
We study here lifts and random lifts of graphs, as defined in [1]. We consider the Hadwiger number η and the Hajós number σ of ℓlifts of Kn, and analyze their extremal as well as their typical...
Random Vectors of Bounded Weight and Their Linear Dependencies (2000)
Let µ be a probability distribution on a vector space V. When m vectors u1,...,um are drawn from µ, how likely are they to be linearly dependent? How is the dimension of their linear span...
Least-distortion Euclidean embeddings of graphs: products of cycles and expanders (2000)
Embeddings of nite metric spaces into Euclidean space have been studied in several contexts: The local theory of Banach spaces, the design of approximation algorithms, and graph theory. The emphasis...
ProtoMap: automatic classification of protein sequences and hierarchy of protein families (2000)
Yona, Golan, Linial, Nathan, Linial, Michal
The ProtoMap site offers an exhaustive classification of all proteins in the SWISS-PROT database, into groups of related proteins. The classification is based on analysis of all pairwise similarities...
ProtoMap: automatic classification of protein sequences and hierarchy of protein families (1999)
Golan Yona, Nathan Linial, Michal Linial
ABSTRACT We investigate the space of all protein sequences in search of clusters of related proteins. Our aim is to automatically detect these sets, and thus obtain a classification of all protein...
Linear codes and character sums (1999)
Nathan Linial, Alex Samorodnitsky
2. Suppose the smallest Hamming weight of non-zero vectors in V is d. (In coding-theoretic terminology, V is a linear code of length n, rate r and distance d.) We settle two extremal problems on such...
ProtoMap: automatic classification of protein sequences and hierarchy of protein families (1999)
Golan Yona, Nathan Linial, Michal Linial
ABSTRACT We investigate the space of all protein sequences in search of clusters of related proteins. Our aim is to automatically detect these sets, and thus obtain a classification of all protein...
Golan Yona, Nathan Linial, Michal Linial
We investigate the space of all protein sequences in search of clusters of related proteins. Our aim is to automatically detect these sets, and thus obtain a classi cation of all protein sequences....
Linear codes and character sums (1999)
Nathan Linial, Alex Samorodnitsky
Let V be an rn-dimensional linear subspace of Zn 2. Suppose the smallest Hamming weight of non-zero vectors in V is d. (In coding-theoretic terminology, V is a linear code of length n, rate r and...
Low distortion euclidean embeddings of trees (1998)
Nathan Linial, Avner Magen, Michael E. Saks
Embeddings of nite metric spaces into normed spaces are of interest in the local theory of Banach spaces ([?,?,?]), in combinatorics (e.g. [?] and the references therein) and in the theory of...
Michal Linial, Nathan Linial, Naftali Tishby, Golan Yona
A global classification of all currently known protein sequences is performed. Every protein sequence is partitioned into segments of 50 amino acids and a dynamicprogramming distance is calculated...
Golan Yona, Nathan Linial, Naftali Tishby, Michal Linial
We investigate the space of all protein sequences. We combine the standard measures of similarity (SW, FASTA, BLAST), to associate with each sequence an exhaustive list of neighboring sequences....
Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension (1997)
Nathan Linial, Michael Luby, Michael Saks, David Zuckerman, Michael Saks
We describe a deterministic algorithm which, on input integers d, m and real number ffl 2 (0; 1), produces a subset S of [m] d = f1; 2; 3; : : : ; mg d that hits every combinatorial rectangle in [m]...
Inclusion-exclusion: exact and approximate (1996)
Je Kahn, Nathan Linial, Alex Samorodnitsky
It is often required to nd the probability of the union of given n events A 1; : : : ; A n. The answer is provided, of course, by the inclusion-exclusion formula: Pr([A i) =
In a non-expansive 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(R
The Linear-Array Conjecture in Communication Complexity is False (1996)
Eyal Kushilevitz Nathan, Nathan Linial, Rafail Ostrovsky
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,...
The geometry of graphs and some of its algorithmic applications (1995)
Nathan Linial, Eran London, Yuri Rabinovich
In this paper we explore some implications of view-ing graphs as geometric objects. This approach of-fers a new perspective on a number of graph-theoretic and algorithmic problems. There are several...
The geometry of graphs and some of its algorithmic applications (1995)
Nathan Linial, Eran London, Yuri Rabinovich
In this paper 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...
On the Distance Distribution of Codes (1995)
The distance distribution of a binary code C is the sequence (G i ) n i=0 defined as follows: Let G i (w) be the number of code words at distance i from the code word w, and let G i be the average of...
Fault-tolerant Computation in the Full Information Model (1995)
Oded Goldreich, Shafi Goldwasser, Nathan Linial
We initiate an investigation of general fault-tolerant distributed computation in the fullinformation model. In the full information model no restrictions are made on the computational power of the...
Compact Distributed Data Structures for Adaptive Routing (1994)
Baruch Awerbuch, Amotz Bar-noy, Nathan Linial, David Peleg
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'...
The Geometry of Graphs and Some of Its Algorithmic Applications (1994)
Nathan Linial, Eran London, Yuri Rabinovich
In this paper 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...
On the Hardness of Approximating the Chromatic Number (1993)
We study the hardness of approximating the chromatic number when the input graph is k-colorable for some xed k 3. Our main result is that it is NP-hard to nd a 4-coloring of a 3-chromatic graph. As...
Games Computers Play: Game-Theoretic Aspects of Computing (1992)
Computers may interact in great many ways. A parallel computer consists of a group of processors which cooperate in order to solve large-scale computational problems. Computers
Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Nathan Linial, Steven Phillips
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...
An optimal online algorithm for metrical task systems (1992)
Allan Borodin, Nathan Linial, Michael E. Saks
Abstract. 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...
Approximate inclusion-exclusion (1990)
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...
Compact Distributed Data Structures for Adaptive Routing (1989)
Baruch Awerbuch, Amotz Bar-noy, Nathan Linial, David Peleg
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'...
A radio network is a synchronous network of processors that communicate by transmitting messages to their neighbors, where a processor receives a message in a given step if and only if it is silent...
The influence of variables on Boolean functions (1988)
Jeff Kahn, Gil Kalai, Nathan Linial
This paper applies methods from harmonic analysis to prove some general theorems on boolean functions. The result that is easiest to describe says that "Boolean functions always have small...
ProtoMap: automatic classification of protein sequences and hierarchy of protein families
Yona, Golan, Linial, Nathan, Linial, Michal
The ProtoMap site offers an exhaustive classification of all proteins in the SWISS-PROT database, into groups of related proteins. The classification is based on analysis of all pairwise similarities...
ProtoNet: hierarchical classification of the protein space
Sasson, Ori, Vaaknin, Avishay, Fleischer, Hillel, Portugaly, Elon, Bilu, Yonatan, Linial, Nathan, ...
The ProtoNet site provides an automatic hierarchical clustering of the SWISS-PROT protein database. The clustering is based on an all-against-all BLAST similarity search. The similarities' E-score is...
Approximate protein structural alignment in polynomial time
Kolodny, Rachel, Linial, Nathan
Alignment of protein structures is a fundamental task in computational molecular biology. Good structural alignments can help detect distant evolutionary relationships that are hard or impossible to...
ProtoNet 4.0: A hierarchical classification of one million protein sequences
Kaplan, Noam, Sasson, Ori, Inbar, Uri, Friedlich, Moriah, Fromer, Menachem, Fleischer, Hillel, ...
ProtoNet is an automatic hierarchical classification of the protein sequence space. In 2004, the ProtoNet (version 4.0) presents the analysis of over one million proteins merged from SwissProt and...
EVEREST: automatic identification and classification of protein domains in all protein sequences
Portugaly, Elon, Harel, Amir, Linial, Nathan, Linial, Michal
ProtoMap: automatic classification of protein sequences and hierarchy of protein families
Yona, Golan, Linial, Nathan, Linial, Michal
The ProtoMap site offers an exhaustive classification of all proteins in the SWISS-PROT database, into groups of related proteins. The classification is based on analysis of all pairwise similarities...
ProtoNet: hierarchical classification of the protein space
Sasson, Ori, Vaaknin, Avishay, Fleischer, Hillel, Portugaly, Elon, Bilu, Yonatan, Linial, Nathan, ...
The ProtoNet site provides an automatic hierarchical clustering of the SWISS-PROT protein database. The clustering is based on an all-against-all BLAST similarity search. The similarities' E-score is...
Approximate protein structural alignment in polynomial time
Kolodny, Rachel, Linial, Nathan
Alignment of protein structures is a fundamental task in computational molecular biology. Good structural alignments can help detect distant evolutionary relationships that are hard or impossible to...
ProtoNet 4.0: A hierarchical classification of one million protein sequences
Kaplan, Noam, Sasson, Ori, Inbar, Uri, Friedlich, Moriah, Fromer, Menachem, Fleischer, Hillel, ...
ProtoNet is an automatic hierarchical classification of the protein sequence space. In 2004, the ProtoNet (version 4.0) presents the analysis of over one million proteins merged from SwissProt and...
EVEREST: automatic identification and classification of protein domains in all protein sequences
Portugaly, Elon, Harel, Amir, Linial, Nathan, Linial, Michal
EVEREST: a collection of evolutionary conserved protein domains
Portugaly, Elon, Linial, Nathan, Linial, Michal
Protein domains are subunits of proteins that recur throughout the protein world. There are many definitions attempting to capture the essence of a protein domain, and several systems that identify...
A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents
Nathan Linial, Alex Samorodnitsky, Avi Wigderson
We present a deterministic strongly polynomial algorithm that computes the permanent of a nonnegative n n matrix to within a multiplicative factor of e .