Arrow Research search

Author name cluster

Nati Linial

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

36 papers
2 author rows

Possible papers

36

FOCS Conference 2019 Conference Paper

Expander Graphs - Both Local and Global

  • Michael Chapman
  • Nati Linial
  • Yuval Peled

Let G=(V, E) be a finite graph. For vϵ V we denote by G_v the subgraph of G that is induced by v's neighbor set. We say that G is (a, b) -regular for a>b>0 integers, if G is a-regular and G v is b-regular for every vϵ V. Recent advances in PCP theory call for the construction of infinitely many (a, b) -regular expander graphs G that are expanders also locally. Namely, all the graphs {G v |vϵ V} should be expanders as well. While random regular graphs are expanders with high probability, they almost surely fail to expand locally. Here we construct two families of (a, b) -regular graphs that expand both locally and globally. We also analyze the possible local and global spectral gaps of (a, b) -regular graphs. In addition, we examine our constructions vis-a-vis properties which are considered characteristic of high-dimensional expanders.

Details

STOC Conference 2014 Conference Paper

From average case complexity to improper learning complexity

  • Amit Daniely
  • Nati Linial
  • Shai Shalev-Shwartz

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.

Details

NeurIPS Conference 2013 Conference Paper

More data speeds up training time in learning halfspaces over sparse vectors

  • Amit Daniely
  • Nati Linial
  • Shai Shalev-Shwartz

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.

PDF Details

TARK Conference 2011 Conference Paper

The dynamics of reputation systems

  • Amir Ban
  • Nati Linial

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. The specific model depends on (i) The way that experts’ reputation affects customers’ preferences, (ii) How experts’ reputation is modified as a result of their success/failure in satisfying the customers’ requests. We investigate several such models and elucidate some of the key characteristics of reputation in such a market of experts and customers.

Details

STOC Conference 2007 Conference Paper

Lower bounds in communication complexity based on factorization norms

  • Nati Linial
  • Adi Shraibman

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.

Details

FOCS Conference 2004 Conference Paper

Constructing Expander Graphs by 2-Lifts and Discrepancy vs. Spectral Gap

  • Yonatan Bilu
  • Nati Linial

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.

Details

FOCS Conference 1994 Conference Paper

The geometry of graphs and some of its algorithmic applications

  • Nati Linial
  • Eran London
  • Yuri Rabinovich

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. >

Details

FOCS Conference 1991 Conference Paper

Fault-tolerant Computation in the Full Information Model (Extended Abstract)

  • Oded Goldreich 0001
  • Shafi Goldwasser
  • Nati Linial

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). >

Details

FOCS Conference 1989 Conference Paper

Constant Depth Circuits, Fourier Transform, and Learnability

  • Nati Linial
  • Yishay Mansour
  • Noam Nisan

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. >

Details

FOCS Conference 1989 Conference Paper

Graph Products and Chromatic Numbers

  • Nati Linial
  • Umesh V. Vazirani

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. >

Details

FOCS Conference 1988 Conference Paper

Results on learnability and the Vapnik-Chervonenkis dimension (Extended Abstract)

  • Nati Linial
  • Yishay Mansour
  • Ronald L. Rivest

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. >

Details

FOCS Conference 1988 Conference Paper

The Influence of Variables on Boolean Functions (Extended Abstract)

  • Jeff Kahn 0001
  • Gil Kalai
  • Nati Linial

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. >

Details

FOCS Conference 1987 Conference Paper

Distributive Graph Algorithms-Global Solutions from Local Data

  • Nati Linial

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.

Details

FOCS Conference 1985 Conference Paper

Collective Coin Flipping, Robust Voting Schemes and Minima of Banzhaf Values

  • Michael Ben-Or
  • Nati Linial

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.

Details

FOCS Conference 1985 Conference Paper

Multi-Layer Grid Embeddings

  • Alok Aggarwal
  • Maria M. Klawe
  • David Lichtenstein
  • Nati Linial
  • Avi Wigderson

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.

Details

FOCS Conference 1983 Conference Paper

Legal Coloring of Graphs

  • Nati Linial

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.

Details