| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman, Orly Yahalom |
On the query complexity of testing orientations for being Eulerian.  |
ACM Transactions on Algorithms  |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Victor Chepoi, Feodor F. Dragan, Ilan Newman, Yuri Rabinovich, Yann Vaxès |
Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs. |
Discrete & Computational Geometry |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg |
Hierarchy Theorems for Property Testing. |
Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala |
Local Versus Global Properties of Metric Spaces. |
SIAM J. Comput. |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Ilan Newman, Yuri Rabinovich |
On multiplicative λ-approximations and some geometric applications. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Oren Ben-Zwi, Danny Hermelin, Daniel Lokshtanov, Ilan Newman |
Treewidth governs the complexity of target set selection. |
Discrete Optimization |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Igor Kleiner, Daniel Keren, Ilan Newman, Oren Ben-Zwi |
Applying Property Testing to an Image Partitioning Problem. |
IEEE Trans. Pattern Anal. Mach. Intell. |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, Oren Weimann |
The Stackelberg Minimum Spanning Tree Game. |
Algorithmica |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Lachish, Ilan Newman |
Testing Periodicity. |
Algorithmica |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Gad M. Landau, Avivit Levy, Ilan Newman |
LCS approximation via embedding into locally non-repetitive strings. |
Inf. Comput. |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Oren Ben-Zwi, Ilan Newman |
Optimal Bi-Valued Auctions |
CoRR |
2011 |
DBLP BibTeX RDF |
|
| 1 | Ilan Newman, Christian Sohler |
Every property of hyperfinite graphs is testable. |
STOC |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Ilan Newman, Yuri Rabinovich |
On Cut Dimension of $\ell_1$ Metrics and Volumes, and Related Sparsification Techniques |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Victor Chepoi, Feodor F. Dragan, Ilan Newman, Yuri Rabinovich, Yann Vaxès |
Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Ilan Newman |
Property Testing of Massively Parametrized Problems - A Survey. |
Property Testing |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg |
Hierarchy Theorems for Property Testing. |
Property Testing |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Victor Chepoi, Feodor F. Dragan, Ilan Newman, Yuri Rabinovich, Yann Vaxès |
Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Ilan Newman, Yuri Rabinovich |
Hard Metrics from Cayley Graphs of Abelian Groups. |
Theory of Computing |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Ilan Newman |
Computing in fault tolerant broadcast networks and noisy decision trees. |
Random Struct. Algorithms |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Ilan Newman, Oren Weimann |
The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs |
CoRR |
2009 |
DBLP BibTeX RDF |
|
| 1 | Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira |
A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Ilan Newman, Oren Weimann |
The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs. |
WINE |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Oren Ben-Zwi, Ilan Newman, Guy Wolfovitz |
A New Derandomization of Auctions. |
SAGT |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Gad M. Landau, Avivit Levy, Ilan Newman |
LCS Approximation via Embedding into Local Non-repetitive Strings. |
CPM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Oren Ben-Zwi, Danny Hermelin, Daniel Lokshtanov, Ilan Newman |
An exact almost optimal algorithm for target set selection in social networks. |
ACM Conference on Electronic Commerce |
2009 |
DBLP DOI BibTeX RDF |
bounded tree-width algorithm, bounded tree-width lower-bound, target set selection, social networks, viral marketing |
| 1 | Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg |
Hierarchy Theorems for Property Testing. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
Monotone Graph Properties, Graph Blow-up, One-Sided vs Two-Sided Error, Adaptivity vs Non-adaptivity, Property Testing, Graph Properties |
| 1 | Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg |
Hierarchy Theorems for Property Testing. |
Electronic Colloquium on Computational Complexity (ECCC) |
2008 |
DBLP BibTeX RDF |
|
| 1 | Oded Lachish, Ilan Newman, Asaf Shapira |
Space Complexity Vs. Query Complexity. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
Subject classification. 68Q15, 68Q10 |
| 1 | Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig |
Quantum Property Testing. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Eldar Fischer, Oded Lachish, Ilan Newman, Arie Matsliah, Orly Yahalom |
On the Query Complexity of Testing Orientations for Being Eulerian. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Roy Levin, Ilan Newman, Gadi Haber |
Complementing Missing and Inaccurate Profiling Using a Minimum Cost Circulation Algorithm. |
HiPEAC |
2008 |
DBLP DOI BibTeX RDF |
Circulations, Real-time, Sampling, Profiling, Control Flow, Flow network |
| 1 | Oren Ben-Zwi, Oded Lachish, Ilan Newman |
Lower bounds for testing Euclidean Minimum Spanning Trees. |
Inf. Process. Lett. |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur |
Testing Properties of Constraint-Graphs. |
Electronic Colloquium on Computational Complexity (ECCC) |
2007 |
DBLP BibTeX RDF |
|
| 1 | Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin |
Partitioning multi-dimensional sets in a small number of "uniform" parts. |
Eur. J. Comb. |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Eldar Fischer, Ilan Newman |
Testing of matrix-poset properties. |
Combinatorica |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, Oren Weimann |
The Stackelberg Minimum Spanning Tree Game |
CoRR |
2007 |
DBLP BibTeX RDF |
|
| 1 | Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf |
Robust Polynomials and Quantum Algorithms. |
Theory Comput. Syst. |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Eldar Fischer, Ilan Newman |
Testing versus Estimation of Graph Properties. |
SIAM J. Comput. |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Eldar Fischer, Ilan Newman |
Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs. |
SIAM J. Comput. |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Ilan Newman, Yuri Rabinovich |
Hard Metrics from Cayley Graphs of Abelian Groups. |
STACS |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, Oren Weimann |
The Stackelberg Minimum Spanning Tree Game. |
WADS |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Sourav Chakraborty, Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman |
Testing st -Connectivity. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur |
Testing Properties of Constraint-Graphs. |
IEEE Conference on Computational Complexity |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Lachish, Ilan Newman, Asaf Shapira |
Space Complexity vs. Query Complexity. |
Electronic Colloquium on Computational Complexity (ECCC) |
2006 |
DBLP BibTeX RDF |
|
| 1 | Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair |
Embedding k-Outerplanar Graphs into l 1. |
SIAM J. Discrete Math. |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala |
Local versus global properties of metric spaces. |
SODA |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Lachish, Ilan Newman, Asaf Shapira |
Space Complexity vs. Query Complexity. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira |
A combinatorial characterization of the testable graph properties: it's all about regularity. |
STOC |
2006 |
DBLP DOI BibTeX RDF |
characterization, property testing, regularity lemma |
| 1 | Oded Lachish, Ilan Newman |
Languages that are Recognized by Simple Counter Automata are not necessarily Testable |
Electronic Colloquium on Computational Complexity (ECCC) |
2005 |
DBLP BibTeX RDF |
|
| 1 | Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin |
Partitioning multi-dimensional sets in a small number of ``uniform'' parts |
Electronic Colloquium on Computational Complexity (ECCC) |
2005 |
DBLP BibTeX RDF |
|
| 1 | Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur |
Testing Orientation Properties |
Electronic Colloquium on Computational Complexity (ECCC) |
2005 |
DBLP BibTeX RDF |
|
| 1 | Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler |
Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time. |
SIAM J. Comput. |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin |
Increasing Kolmogorov Complexity. |
STACS |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf |
Robust Polynomials and Quantum Algorithms. |
STACS |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Lachish, Ilan Newman |
Testing Periodicity. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Eldar Fischer, Ilan Newman |
Testing versus estimation of graph properties. |
STOC |
2005 |
DBLP DOI BibTeX RDF |
property testing, regularity lemma, graph properties, distance approximation |
| 1 | Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin |
Increasing Kolmogorov Complexity |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | Oded Lachish, Ilan Newman |
Testing Periodicity |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | Eldar Fischer, Ilan Newman, Jiri Sgall |
Functions that have read-twice constant width branching programs are not necessarily testable. |
Random Struct. Algorithms |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair |
Cuts, Trees and l1-Embeddings of Graphs. |
Combinatorica |
2004 |
DBLP DOI BibTeX RDF |
Mathematics Subject Classification (2000): 05C12, 90C27, 68R10, 05C85 |
| 1 | Ilan Newman |
Computing in Fault Tolerance Broadcast Networks. |
IEEE Conference on Computational Complexity |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf |
Robust Quantum Algorithms and Polynomials |
CoRR |
2003 |
DBLP BibTeX RDF |
|
| 1 | Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig |
Quantum property testing. |
SODA |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair |
Embedding k-outerplanar graphs into l1. |
SODA |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler |
Sublinear-time approximation of Euclidean minimum spanning tree. |
SODA |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Adnan Agbaria, Yosi Ben-Asher, Ilan Newman |
Communication - Processor Tradeoffs in a Limited Resources PRAM. |
Algorithmica |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Ilan Newman |
Testing Membership in Languages that Have Small Width Branching Programs. |
SIAM J. Comput. |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Ilan Newman, Yuri Rabinovich |
A lower bound on the distortion of embedding planar metrics into Euclidean space. |
Symposium on Computational Geometry |
2002 |
DBLP DOI BibTeX RDF |
embedding into Eucledian spaces, metric spaces |
| 1 | Eldar Fischer, Ilan Newman |
Functions that have Read-Twice Constant Width Branching Programs are not Necessarily Testable. (PDF / PS) |
IEEE Conference on Computational Complexity |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky |
Monotonicity testing over general poset domains. |
STOC |
2002 |
DBLP DOI BibTeX RDF |
algorithms, property testing, monotone functions |
| 1 | Eldar Fischer, Ilan Newman |
Testing of matrix properties. |
STOC |
2001 |
DBLP DOI BibTeX RDF |
matrix properties, property testing |
| 1 | Pascal Berthomé, Torben Hagerup, Ilan Newman, Assaf Schuster |
Self-Simulation for the Passive Optical Star. |
J. Algorithms |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy |
Regular Languages are Testable with a Constant Number of Queries. |
SIAM J. Comput. |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Ilan Newman |
Testing of Functions that have small width Branching Programs. |
FOCS |
2000 |
DBLP DOI BibTeX RDF |
small width branching programs, combinatorial property testing, read-once branching programs, computational complexity, probability, probability, Boolean functions, Boolean functions, randomized algorithm, directed graphs, regular languages, randomised algorithms, decision problems, query complexity |
| 1 | Yosi Ben-Asher, Eitan Farchi, Ilan Newman |
Optimal Search in Trees. |
SIAM J. Comput. |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | Adnan Agbaria, Yosi Ben-Asher, Ilan Newman |
Communication-Processor Tradeoffs in Limited Resources PRAM. |
SPAA |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy |
Regular Languages Are Testable with a Constant Number of Queries. |
FOCS |
1999 |
DBLP DOI BibTeX RDF |
testing, randomized algorithms, regular languages |
| 1 | Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair |
Cuts, Trees and l1-Embeddings of Graphs. |
FOCS |
1999 |
DBLP DOI BibTeX RDF |
![src=EQN76.GIF]() embeddings, Multicommodity flow, Sparsest cut, Finite metric spaces |
| 1 | Ishai Ben-Aroya, Ilan Newman, Assaf Schuster |
Randomized Single-Target Hot-Potato Routing. |
J. Algorithms |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Yosi Ben-Asher, Ilan Newman |
Geometric Approach for Optimal Routing on a Mesh with Buses. |
J. Comput. Syst. Sci. |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Yosi Ben-Asher, Eitan Farchi, Ilan Newman |
Optimal Search in Trees: Extended Abstract + Appendix. |
SODA |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Yosi Ben-Asher, Ilan Newman |
Geometric Approach for Optimal Routing on Mesh with Buses |
Electronic Colloquium on Computational Complexity (ECCC) |
1996 |
DBLP BibTeX RDF |
|
| 1 | Yosi Ben-Asher, Ilan Newman |
Optimal Search in Trees |
Electronic Colloquium on Computational Complexity (ECCC) |
1996 |
DBLP BibTeX RDF |
|
| 1 | Ilan Newman, Mario Szegedy |
Public vs. Private Coin Flips in One Round Communication Games (Extended Abstract). |
STOC |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Ilan Newman, Assaf Schuster |
Hot-Potato Algorithms for Permutation Routing. |
IEEE Trans. Parallel Distrib. Syst. |
1995 |
DBLP DOI BibTeX RDF |
parallel algorithms, packet routing, Deflection routing |
| 1 | Ilan Newman, Assaf Schuster |
Hot Potato Worm Routing via Store-and-Forward Packet Routing. |
J. Parallel Distrib. Comput. |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Ilan Newman, Avi Wigderson |
Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy. |
SIAM J. Discrete Math. |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | László Lovász, Moni Naor, Ilan Newman, Avi Wigderson |
Search Problems in the Decision Tree Model. |
SIAM J. Discrete Math. |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Yosi Ben-Asher, Ilan Newman |
Decision Trees with Boolean Threshold Queries. |
J. Comput. Syst. Sci. |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Pascal Berthomé, Th. Duboux, Torben Hagerup, Ilan Newman, Assaf Schuster |
Self-Simulation for the Passive Optical Star Model. |
ESA |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Ishai Ben-Aroya, Ilan Newman, Assaf Schuster |
Randomized Single-Target Hot-Potato Routing. |
ISTCS |
1995 |
DBLP BibTeX RDF |
|
| 1 | Yosi Ben-Asher, Ilan Newman |
Decision Trees with AND, OR Queries. |
Structure in Complexity Theory Conference |
1995 |
DBLP BibTeX RDF |
|
| 1 | Mauricio Karchmer, Ilan Newman, Michael E. Saks, Avi Wigderson |
Non-Deterministic Communication Complexity with Few Witnesses. |
J. Comput. Syst. Sci. |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Rafi Heiman, Ilan Newman, Avi Wigderson |
On Read-Once Threshold Formulae and Their Randomized Decision in Tree Complexity. |
Theor. Comput. Sci. |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Mauricio Karchmer, Nathan Linial, Ilan Newman, Michael E. Saks, Avi Wigderson |
Combinatorial characterization of read-once formulae. |
Discrete Mathematics |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Ilan Newman, Assaf Schuster |
Hot-Potato Worm Routing is Almost as Easy as Store-and-Forward Packet Routing. |
ISTCS |
1993 |
DBLP BibTeX RDF |
|
| 1 | Mauricio Karchmer, Ilan Newman, Michael E. Saks, Avi Wigderson |
Non-deterministic Communication Complexity with Few Witness. |
Structure in Complexity Theory Conference |
1992 |
DBLP BibTeX RDF |
|
| 1 | Ilan Newman |
Private vs. Common Random Bits in Communication Complexity. |
Inf. Process. Lett. |
1991 |
DBLP DOI BibTeX RDF |
|
| 1 | Irith Ben-Arroyo Hartman, Ilan Newman, Ran Ziv |
On grid intersection graphs. |
Discrete Mathematics |
1991 |
DBLP DOI BibTeX RDF |
|
| 1 | László Lovász, Moni Naor, Ilan Newman, Avi Wigderson |
Search Problems in the Decision Tree Model (Preliminary Version) |
FOCS |
1991 |
DBLP DOI BibTeX RDF |
Boolean decision tree model, CNF search, complexities, randomness, search problems, determinism, nondeterminism |
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")