The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs (2009)
Cardinal, Jean, Demaine, Erik D., Fiorini, Samuel, Joret, Gwenaël, Newman, Ilan, Weimann, Oren
The Stackelberg Minimum Spanning Tree Game is a two-level combinatorial pricing problem introduced at WADS'07. The game is played on a graph (representing a network), whose edges are colored either...
Testing Properties of Constraint-Graphs Extended Abstract + Appendix (2009)
Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur
We study a model of graph related formulae that we call the Constraint-Graph model. A constraintgraph is a labeled multi-graph (a graph where loops and parallel edges are allowed), where each edge e...
An Exact Almost Optimal Algorithm for Target Set Selection in Social Networks (2009)
Oren Ben-zwi, Danny Hermelin, Daniel Lokshtanov, Ilan Newman
Abstract. The Target Set Selection problem proposed by Kempe, Kleinberg, and Tardos, gives a nice clean combinatorial formulation for many problems arising in economy, sociology, and medicine. Its...
Approximating the Weight of the Euclidean Minimum Spanning Treein Sublinear Time (2009)
Funda Erg, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohlerk
Abstract We consider the problem of computing the weight of a Euclidean minimum spanning tree fora set of n points in Rd. We focus on the setting where the input point set is supported by...
On the Query Complexity of Testing for Eulerian Orientations (2008)
Eldar Fischer, Arie Matsliah, Ilan Newman, Orly Yahalom
We consider testing directed graphs for being Eulerian in the orientation model introduced in [15]. Despite the local nature of the property of being Eulerian, it turns out to be significantly harder...
Space Complexity vs. Query Complexity ∗ (2008)
Oded Lachish, Ilan Newman, Asaf Shapira
Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x satisfies the property or is “far”...
Lower Bounds for Testing Euclidean Minimum Spanning Trees (2008)
Oren Ben-zwi, Oded Lachish, Ilan Newman
Abstract The Euclidean Minimum Spanning Tree problem is to decide whether a given graph G = ( P, E) on a set of points in the two dimensional plane is a minimum spanning tree with respectto the...
Lower Bounds for Testing Euclidean Minimum Spanning Trees (2008)
Oren Ben-zwi, Oded Lachish, Ilan Newman
The Euclidean Minimum Spanning Tree problem is to decide whether a given graph G = (P, E) on a set of points in the two dimensional plane is a minimum spanning tree with respect to the Euclidean...
Testing Properties of Constraint-Graphs (2008)
Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur
We study a model of graph related formulae that we call the Constraint-Graph model. A constraintgraph is a labeled multi-graph (a graph where loops and parallel edges are allowed), where each edge e...
Space Complexity vs. Query Complexity (2008)
Oded Lachish, Ilan Newman, Asaf Shapira
Abstract. Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x satisfies the property or is...
Abstract. A string α ∈ Σ n is called p-periodic, if for every i, j ∈ {1,..., n}, such that i ≡ j mod p, αi = αj, where αi is the i-th place of α. A string α ∈ Σ n is said to be...
Testing membership in languages that have small width branching programs (2008)
Abstract. Combinatorial property testing, initiated formally by Goldreich, Goldwasser, and
Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time (2008)
Artur Czumaj, Ilan Newman, Funda Ergün, Ronitt Rubinfeld, Lance Fortnow, Avner Magen, ...
We consider the problem of computing the weight of a Euclidean minimum spanning tree for a ¦ set of §© ¨ points in. We focus on the setting where the input point set is supported by certain basic...
Oded Lachish, Ilan Newman, Asaf Shapira
Abstract. Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x satisfies the property or is...
Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time ∗ (2008)
Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, ...
We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in R d. We focus on the setting where the input point set is supported by certain basic (and...
Space Complexity vs. Query Complexity ∗ (2008)
Oded Lachish, Ilan Newman, Asaf Shapira
Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x satisfies the property or is “far”...
Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time (2008)
Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, ...
We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in R^d. We focus on the setting where the input point set is supported by certain basic (and...
Mauricio Karchmer, Mike Saks, Avi Wigderson, Ilan Newman, Ilan Newman
Proposed running title: Nondet communication comp. Mailing address:
Cuts, Trees and l 1 -Embeddings of Graphs (2007)
Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair
Motivated by many recent algorithmic applications, this paper aims to promote a systematic study of the relationship between the topology of a graph and the metric distortion incurred when the graph...
Communication-Processor Tradeoffs in Limited Resources PRAM (2007)
Adnan Agbaria, Yosi Ben-Asher, Ilan Newman
We consider a simple restriction of the PRAM model (called PPRAM), where the input is arbitrarily partitioned between a fixed set of p processors and the shared memory is restricted to m cells. This...
Self-Simulation for the Passive Optical Star (2007)
Pascal Berthome, Ilan Newman, Assaf Schuster
Optical technology offers simple interconnection schemes with straightforward layouts that support complex logical interconnection patterns. The Passive Optical Star (pos) is often suggested as a...
Artur Czumaj, Funda Ergun, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, ...
We consider the problem of estimating the weight of a Euclidean minimum spanning tree for a set of n points in R
Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time (2007)
Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, ...
We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in R . We focus on the setting where the input point set is supported by certain basic (and...
Partitioning Multi-Dimensional Sets in a Small (2007)
Number Of Uniform, Ilan Newman, Alexander Shen, Gabor Tardos, Nikolai Vereshchagin
Our main result implies the following easily formulated statement.
Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair
We show that the shortest-path metric of any k-outerplanar graph, for any fixed k, can be approximated by a probability distribution over tree metrics with constant distortion, and hence also...
The Stackelberg Minimum Spanning Tree Game (2007)
Cardinal, Jean, Demaine, Erik D., Fiorini, Samuel, Joret, Gwenaël, Langerman, Stefan, Newman, Ilan, ...
We consider a one-round two-player network pricing game, the {\em Stackelberg Minimum Spanning Tree} game or StackMST. The game is played on a graph (representing a network), whose edges are colored...
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, ...
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
Testing st-connectivity (2007)
Sourav Chakraborty, Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman
We continue the study, started in [9], of property testing of graphs in the orientation model. A major question which was left open in [9] is whether the property of st-connectivity can be tested...
Testing st-connectivity (2007)
Sourav Chakraborty, Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman
Abstract. We continue the study, started in [9], of property testing of graphs in the orientation model. A major question which was left open in [9] is whether the property of st-connectivity can be...
Efficient testing of bipartite graphs for forbidden induced subgraphs ∗ (2007)
Noga Alon, Eldar Fischer, Ilan Newman
Alon et. al. [3], showed that every property that is characterized by a finite collection of forbidden induced subgraphs is ɛ-testable. However, the complexity of the test is double-tower with...
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, ...
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Stefan Langerman, Ilan Newman, Oren Weimann
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
Testing of matrix-poset properties* (2007)
Abstract Combinatorial property testing, initiated by Rubinfeld and Sudan [23] and formally definedby Goldreich, Goldwasser and Ron in [18], deals with the following relaxation of decision problems:...
Testing st-connectivity (2007)
Sourav Chakraborty, Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman
We continue the study, started in [9], of property testing of graphs in the orientation model. A major question which was left open in [9] is whether the property of st-connectivity can be tested...
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, ...
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, ...
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, ...
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
A combinatorial characterization of the testable graph properties: it’s all about regularity (2006)
Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira
A common thread in all the recent results concerning testing dense graphs is the use of Szemerédi’s regularity lemma. In this paper we show that in some sense this is not a coincidence. Our first...
A combinatorial characterization of the testable graph properties: it’s all about regularity (2006)
Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira
A common thread in all the recent results concerning the testing of dense graphs is the use of Szemerédi’s regularity lemma. In this paper we show that in some sense this is not a coincidence. Our...
Testing of matrix-poset properties* (2006)
Abstract Combinatorial property testing, initiated by Rubinfeld and Sudan [23] and formally definedby Goldreich, Goldwasser and Ron in [18], deals with the following relaxation of decision problems:...
A combinatorial characterization of the testable graph properties: it’s all about regularity (2006)
A common thread in recent results concerning the testing of dense graphs is the use of Szemerédi’s regularity lemma. In this paper we show that in some sense this is not a coincidence. Our first...
Local versus global properties of metric spaces (2006)
Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala
Motivated by applications in combinatorial optimization, we initiate a study of the extent to which the global properties of a metric space (especially, embeddability in ℓ1 with low distortion) are...
A combinatorial characterization of the testable graph properties: it’s all about regularity (2006)
Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira
A common thread in all the recent results concerning the testing of dense graphs is the use of Szemerédi’s regularity lemma. In this paper we show that in some sense this is not a coincidence. Our...
Local versus global properties of metric spaces (2006)
Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala
Motivated by applications in combinatorial optimization, we initiate a study of the extent to which the global properties of a metric space (especially, embeddability in ℓ1 with low distortion) are...
Testing of bipartite graph properties ∗ (2005)
Noga Alon, Eldar Fischer, Ilan Newman
Alon et. al. [3], showed that every property that is characterized by a finite collection of forbidden induced subgraphs is ɛ-testable. However, the complexity of the test is double-tower with...
Testing versus estimation of graph properties (2005)
In the course of the proof we develop a framework for extending Szemer'edi's Regularity Lemma, both as a prerequisite for formulating what kind of information about the input graph will...
Robust polynomials and quantum algorithms (2005)
Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald De Wolf
We define and study the complexity of robust polynomials for Boolean functions and the related fault-tolerant quantum decision trees, where input bits are perturbed by noise. We show that, in...
Robust polynomials and quantum algorithms (2005)
Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald De Wolf
Abstract. We define and study the complexity of robust polynomials for Boolean functions and the related fault-tolerant quantum decision trees, where input bits are perturbed by noise. We show that,...
Robust polynomials and quantum algorithms (2005)
Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald De Wolf
We define and study the complexity of robust polynomials for Boolean functions and the related fault-tolerant quantum decision trees, where input bits are perturbed by noise. We compare several...
Robust Polynomials and Quantum Algorithms (2003)
Buhrman, Harry, Newman, Ilan, Roehrig, Hein, De Wolf, Ronald
We define and study the complexity of robust polynomials for Boolean functions and the related fault-tolerant quantum decision trees, where input bits are perturbed by noise. We compare several...
Quantum property testing (2003)
Harry Buhrman, Lance Fortnow, Ilan Newman
Hein R"ohrig \Lambda \Lambda
Quantum property testing (2003)
Harry Buhrman, Lance Fortnow, Ilan Newman
A language L has a property tester if there exists a probabilistic algorithm that given an input x only asks a small number of bits of x and distinguishes the cases as to whether x is in L and x has...
Quantum property testing (2003)
Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig
A language L has a property tester if there exists a probabilistic algorithm that given an input x only asks a small number of bits of x and distinguishes the cases as to whether x is in L and x has...
Sublinear-Time Approximation of Euclidean Minimum Spanning Tree (2003)
Artur Czumaj, Funda Ergun, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, ...
We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in R^d. We focus on the situation when the input point set is supported by certain basic...
Quantum property testing (2003)
Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig
A language L has a property tester if there exists a probabilistic algorithm that given an input x only asks a small number of bits of x and distinguishes the cases as to whether x is in L and x has...
Functions That Have Read-Twice Constant Width Branching Programs Are Not Necessarily Testable (2003)
Testing of matrix properties (2001)
Combinatorial property testing, initiated by Rubinfeld and Sudan [15] and formally dened by Goldreich, Goldwasser and Ron in [12], deals with the following relaxation of decision problems: Given a...
Testing of matrix properties (2001)
Combinatorial property testing deals with the following relaxation of decision problems: Given a xed property P and an input f, distinguish between the case that f satises P, and the case that no...
Testing of matrix properties (2001)
Combinatorial property testing, initiated by Rubinfeld and Sudan [15] and formally dened by Goldreich, Goldwasser and Ron in [12], deals with the following relaxation of decision problems: Given a...
Testing of matrix properties (2001)
Both collections above are variants of properties that are defined by certain first order formulae with no quantifier alternation over the syntax containing the grid order relations (and some...
Testing of functions that have small width branching programs (2000)
Ilan Newman, The Algorithm Queries
Combinatorial property testing, initiated formally by Goldreich, Goldwasser and Ron in [11], and inspired by Rubinfeld and Sudan [13], deals with the following relaxation of decision problems: Given...
Regular Languages are Testable with a Constant Number of Queries (1999)
Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy
We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron in [7]. The subject of this paper is testing regular languages. Our main result is as follows. For...
Regular Languages are Testable with a Constant Number of Queries (1999)
Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy
We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron in [7]. The subject of this paper is testing regular languages. Our main result is as follows. For...
Regular Languages are Testable with a Constant Number of Queries (1999)
Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy
We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron in [7]. The subject of this paper is testing regular languages. Our main result is as follows. For...
Regular Languages are Testable with a Constant Number of Queries (1999)
Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy
We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron in [7]. The subject of this paper is testing regular languages. Our main result is as follows. For...
Regular Languages are Testable with a Constant Number of Queries (1999)
Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy
We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron in [7]. The subject of this paper is testing regular languages. Our main result is as follows. For...
Broadcasting on a Budget in the Multi-Service Communication Model (1998)
Gene Itkis, Ilan Newman, Assaf Schuster
In this paper we introduce the multi_service model of network communication. This model attempts to capture recent communication technology trends, such as aspects of quality-of-service and their...
Broadcasting on a Budget in the Multi-Service Communication Model (1998)
Gene Itkis, Ilan Newman, Assaf Schuster
In this paper we introduce the multi service model of network communication. This model attempts to capture recent communication technology trends, such as aspects of qualityof -service and their...
Optimal Search in Trees (1997)
Yosi Ben-Asher, Eitan Farchi, Ilan Newman
It is well known that the optimal solution for searching in a finite total order set is binary search. In binary search we divide the set into two "halves" by querying the middle element...
Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai Vereshchagin
classification: Kolmogorov complexity, computational complexity
Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai Vereshchagin
classification: Kolmogorov complexity, computational complexity
Public vs. Private coin flips in one round communication games (Extended Abstract) (1996)
) Ilan Newman and Mario Szegedy y Abstract We study 1-round two parties communication complexity games, where private random bits are used. We observe that the existence of good protocols for such...
Optimal Search in Trees (Extended Abstract + Appendix) (1996)
Yosi Ben-Asher, Eitan Farchi, Ilan Newman
+ Appendix Yosi Ben-Asher, Eitan Farchi, y Ilan Newman z , Abstract It is well known that the optimal solution for searching in a finite total order set is the binary search. In the binary search we...
Geometric Approach for Optimal Routing on Mesh with Buses (1996)
The architecture of 'mesh of buses' is an important model in parallel computing. Its main advantage is that the additional broadcast capability can be used to overcome the main disadvantage...
Lower Bounds on Formula Size of Boolean Functions using Hypergraph-Entropy (1996)
Korner [7] defined the notion of graph-entropy. He used it in [8] to simplify the proof of the Fredman-Komlos lower bound for the family size of perfect hash functions. We use this information...
Self-Simulation for the Passive Optical Star (1995)
Pascal Berthome, Torben Hagerup, Ilan Newman, Assaf Schuster
Optical technology offers simple interconnection schemes with straightforward layouts that support complex logical interconnection patterns. The Passive Optical Star (pos), in which communication...
Private vs. Common Random bits in Communication Complexity (1995)
We investigate the relative power of the common random string model vs. the private random string model in communication complexity. We show that the two model are essentially equal. Keywords:...
Lower Bounds on Formula Size of Boolean Functions using Hypergraph-Entropy (1995)
Korner [7] defined the notion of graph-entropy. He used it in [8] to simplify the proof of the Fredman-Komlos lower bound for the family size of perfect hash functions. We use this information...
Decision trees with Boolean threshold queries (1995)
Yosi Ben-Asher, Ilan Newman, Ilan Newman
We investigate decision trees in which one is allowed to query threshold functions of subsets of variables. We are mainly interested in the case were only queries of AND and OR are allowed. This...
Geometric Approach for Optimal Routing on Mesh with Buses (1995)
The architecture of 'mesh of buses' is an important model in parallel computing. Its main advantage is that the additional broadcast capability can be used to overcome the main disadvantage...
Randomized Single-Target Hot-Potato Routing (1995)
Ishai Ben Aroya, Ilan Newman, Assaf Schuster
We present randomized hot-potato routing algorithms on d-dimensional meshes and on the n-dimensional hypercube. The algorithms are designed for routing many packets to a single destination, or a...
Geometric Approach for Optimal Routing on Mesh with Buses (1995)
The architecture of 'mesh of buses' is an important model in parallel computing. Its main advantage is that the additional broadcast capability can be used to overcome the main disadvantage...
Decision trees with Boolean threshold queries (1995)
Yosi Ben-Asher, Ilan Newman, Ilan Newman
We investigate decision trees in which one is allowed to query threshold functions of subsets of variables. We are mainly interested in the case were only queries of AND and OR are allowed. This...
Lower bounds on formula size of Boolean functions using hypergraph entropy (1995)
Körner [7] defined the notion of graph-entropy. He used it in [8] to simplify the proof of the Fredman-Komlos lower bound for the family size of perfect hash functions. We use this information...
On Read-Once Threshold Formulae and their Randomized Decision Tree Complexity (1994)
Rafi Heiman, Ilan Newman, Avi Wigderson
TC 0 is the class of functions computable by polynomial-size, constant- depth formulae with threshold gates. Read-Once TC 0 (RO-TC 0 ) is the subclass of TC 0 which restricts every variable to occur...
Search Problems in the Decision Tree Model (1994)
Laszlo Lovasz, Moni Naor, Ilan Newman, Avi Wigderson
We study the relative power of determinism, randomness and nondeterminism for search problems in the Boolean decision tree model. We show that the gaps between the nondeterministic, the randomized...
Non-deterministic communication complexity with few witnesses (1994)
Mauricio Karchmer, Ilan Newman, Mike Saks, Avi Wigderson
We study non-deterministic communication protocols in which no input has too many witnesses. Define nk(f) to be the minimum complexity of a non-deterministic protocol for the function f in which each...