Ilan Newman

ORCID

Publication Activity (10 Years)

Years Active: 1990-2024
Publications (10 Years): 21

Top Venues

CoRR

ICALP

Random Struct. Algorithms

APPROX-RANDOM

Publications

Ilan Newman, Nithin Varma
Strongly Sublinear Algorithms for Testing Pattern Freeness. TheoretiCS 3 (2024)
Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov
Hardness Condensation by Restriction. STOC (2024)
Ilan Newman, Yuri Rabinovich
Online embedding of metrics. CoRR (2023)
Oren Ben-Zwi, Ilan Newman
No Ascending Auction can find Equilibrium for SubModular valuations. CoRR (2023)
Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov
Hardness Condensation by Restriction. Electron. Colloquium Comput. Complex. (2023)
Ilan Newman, Nithin Varma
Strongly Sublinear Algorithms for Testing Pattern Freeness. ICALP (2022)
Abhiruk Lahiri, Ilan Newman, Nithin Varma
Parameterized Convexity Testing. SOSA (2022)
Ilan Newman, Nithin Varma
Strongly Sublinear Algorithms for Testing Pattern Freeness. CoRR (2021)
Rogers Mathew, Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad
Hamiltonian and pseudo-Hamiltonian cycles and fillings in simplicial complexes. J. Comb. Theory, Ser. B 150 (2021)
Ibrahim Jubran, Ernesto Evgeniy Sanches Shayda, Ilan Newman, Dan Feldman
Coresets for Decision Trees of Signals. NeurIPS (2021)
Ilan Newman, Nithin Varma
New Sublinear Algorithms and Lower Bounds for LIS Estimation. ICALP (2021)
Abhiruk Lahiri, Ilan Newman, Nithin Varma
Parameterized Convexity Testing. CoRR (2021)
Ibrahim Jubran, Ernesto Evgeniy Sanches Shayda, Ilan Newman, Dan Feldman
Coresets for Decision Trees of Signals. CoRR (2021)
Ilan Newman, Nithin Varma
New Algorithms and Lower Bounds for LIS Estimation. CoRR (2020)
Hiro Ito, Areej Khoury, Ilan Newman
On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs. Comput. Complex. 29 (1) (2020)
Ilan Newman, Yuri Rabinovich
Online Embedding of Metrics. SWAT (2020)
Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad, Christian Sohler
Testing for forbidden order patterns in an array. Random Struct. Algorithms 55 (2) (2019)
Irith Ben-Arroyo Hartman, Ilan Newman
Contractors' minimum spanning tree. Australas. J Comb. 74 (2019)
Hiro Ito, Areej Khoury, Ilan Newman
On the Characterization of 1-sided error Strongly-Testable Graph Properties for bounded-degree graphs, including an appendix. CoRR (2019)
Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad, Christian Sohler
Testing for Forbidden Order Patterns in an Array. SODA (2017)
Jasine Babu, Areej Khoury, Ilan Newman
Every Property of Outerplanar Graphs is Testable. APPROX-RANDOM (2016)
Oren Ben-Zwi, Ilan Newman, Guy Wolfovitz
Hats, auctions and derandomization. Random Struct. Algorithms 46 (3) (2015)
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. J. Comb. Optim. 25 (1) (2013)
Oren Ben-Zwi, Ron Lavi, Ilan Newman
Ascending auctions and Walrasian equilibrium CoRR (2013)
Ilan Newman, Christian Sohler
Every Property of Hyperfinite Graphs Is Testable. SIAM J. Comput. 42 (3) (2013)
Ilan Newman, Yuri Rabinovich
On Multiplicative Lambda-Approximations and Some Geometric Applications. SIAM J. Comput. 42 (3) (2013)
Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman, Orly Yahalom
On the query complexity of testing orientations for being Eulerian. ACM Trans. Algorithms 8 (2) (2012)
Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh S. Vempala
Local Versus Global Properties of Metric Spaces. SIAM J. Comput. 41 (1) (2012)
Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg
Hierarchy Theorems for Property Testing. Comput. Complex. 21 (1) (2012)
Ilan Newman, Yuri Rabinovich
On multiplicative λ-approximations and some geometric applications. SODA (2012)
Victor Chepoi, Feodor F. Dragan, Ilan Newman, Yuri Rabinovich, Yann Vaxès
Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs. Discret. Comput. Geom. 47 (1) (2012)
Ilan Newman, Christian Sohler
Every property of hyperfinite graphs is testable. STOC (2011)
Oren Ben-Zwi, Ilan Newman
Optimal Bi-Valued Auctions CoRR (2011)
Oded Lachish, Ilan Newman
Testing Periodicity. Algorithmica 60 (2) (2011)
Oren Ben-Zwi, Danny Hermelin, Daniel Lokshtanov, Ilan Newman
Treewidth governs the complexity of target set selection. Discret. Optim. 8 (1) (2011)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, Oren Weimann
The Stackelberg Minimum Spanning Tree Game. Algorithmica 59 (2) (2011)
Gad M. Landau, Avivit Levy, Ilan Newman
LCS approximation via embedding into locally non-repetitive strings. Inf. Comput. 209 (4) (2011)
Igor Kleiner, Daniel Keren, Ilan Newman, Oren Ben-Zwi
Applying Property Testing to an Image Partitioning Problem. IEEE Trans. Pattern Anal. Mach. Intell. 33 (2) (2011)
Ilan Newman, Yuri Rabinovich
Metrics and Volumes, and Related Sparsification Techniques CoRR (2010)
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)
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)
Oren Ben-Zwi, Ilan Newman, Guy Wolfovitz
A New Derandomization of Auctions. SAGT (2009)
Gad M. Landau, Avivit Levy, Ilan Newman
LCS Approximation via Embedding into Local Non-repetitive Strings. CPM (2009)
Ilan Newman
Computing in fault tolerant broadcast networks and noisy decision trees. Random Struct. Algorithms 34 (4) (2009)
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)
Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira
A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity. SIAM J. Comput. 39 (1) (2009)
Oren Ben-Zwi, Danny Hermelin, Daniel Lokshtanov, Ilan Newman
An exact almost optimal algorithm for target set selection in social networks. EC (2009)
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)
Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg
Hierarchy Theorems for Property Testing. APPROX-RANDOM (2009)
Ilan Newman, Yuri Rabinovich
Hard Metrics from Cayley Graphs of Abelian Groups. Theory Comput. 5 (1) (2009)
Oded Lachish, Ilan Newman, Asaf Shapira
Space Complexity Vs. Query Complexity. Comput. Complex. 17 (1) (2008)
Roy Levin, Ilan Newman, Gadi Haber
Complementing Missing and Inaccurate Profiling Using a Minimum Cost Circulation Algorithm. HiPEAC (2008)
Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig
Quantum Property Testing. SIAM J. Comput. 37 (5) (2008)
Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg
Hierarchy Theorems for Property Testing. Electron. Colloquium Comput. Complex. 15 (097) (2008)
Eldar Fischer, Oded Lachish, Ilan Newman, Arie Matsliah, Orly Yahalom
On the Query Complexity of Testing Orientations for Being Eulerian. APPROX-RANDOM (2008)
Noga Alon, Eldar Fischer, Ilan Newman
Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs. SIAM J. Comput. 37 (3) (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, Oren Weimann
The Stackelberg Minimum Spanning Tree Game CoRR (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, Oren Weimann
The Stackelberg Minimum Spanning Tree Game. WADS (2007)
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. 28 (1) (2007)
Oren Ben-Zwi, Oded Lachish, Ilan Newman
Lower bounds for testing Euclidean Minimum Spanning Trees. Inf. Process. Lett. 102 (6) (2007)
Sourav Chakraborty, Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman
-Connectivity. APPROX-RANDOM (2007)
Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur
Testing Properties of Constraint-Graphs. Electron. Colloquium Comput. Complex. 14 (054) (2007)
Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur
Testing Properties of Constraint-Graphs. Computational Complexity Conference (2007)
Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf
Robust Polynomials and Quantum Algorithms. Theory Comput. Syst. 40 (4) (2007)
Eldar Fischer, Ilan Newman
Testing versus Estimation of Graph Properties. SIAM J. Comput. 37 (2) (2007)
Ilan Newman, Yuri Rabinovich
Hard Metrics from Cayley Graphs of Abelian Groups. STACS (2007)
Eldar Fischer, Ilan Newman
Testing of matrix-poset properties. Comb. 27 (3) (2007)
Oded Lachish, Ilan Newman, Asaf Shapira
Space Complexity vs. Query Complexity. Electron. Colloquium Comput. Complex. 13 (103) (2006)
Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair
. SIAM J. Discret. Math. 20 (1) (2006)
Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira
A combinatorial characterization of the testable graph properties: it's all about regularity. STOC (2006)
Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh S. Vempala
Local versus global properties of metric spaces. SODA (2006)
Oded Lachish, Ilan Newman, Asaf Shapira
Space Complexity vs. Query Complexity. APPROX-RANDOM (2006)
Oded Lachish, Ilan Newman
Testing Periodicity. APPROX-RANDOM (2005)
Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf
Robust Polynomials and Quantum Algorithms. STACS (2005)
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. 35 (1) (2005)
Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur
Testing Orientation Properties Electron. Colloquium Comput. Complex. (153) (2005)
Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin
Partitioning multi-dimensional sets in a small number of "uniform" parts Electron. Colloquium Comput. Complex. (095) (2005)
Eldar Fischer, Ilan Newman
Testing versus estimation of graph properties. STOC (2005)
Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin
Increasing Kolmogorov Complexity. STACS (2005)
Oded Lachish, Ilan Newman
Languages that are Recognized by Simple Counter Automata are not necessarily Testable Electron. Colloquium Comput. Complex. (152) (2005)
Ilan Newman
Computing in Fault Tolerance Broadcast Networks. Computational Complexity Conference (2004)
Eldar Fischer, Ilan Newman, Jirí Sgall
Functions that have read-twice constant width branching programs are not necessarily testable. Random Struct. Algorithms 24 (2) (2004)
Oded Lachish, Ilan Newman
Testing Periodicity Electron. Colloquium Comput. Complex. (092) (2004)
Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin
Increasing Kolmogorov Complexity Electron. Colloquium Comput. Complex. (081) (2004)
Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair
-Embeddings of Graphs. Comb. 24 (2) (2004)
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)
Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair
Embedding k-outerplanar graphs into l1. SODA (2003)
Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf
Robust Quantum Algorithms and Polynomials CoRR (2003)
Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig
Quantum property testing. SODA (2003)
Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky
Monotonicity testing over general poset domains. STOC (2002)
Eldar Fischer, Ilan Newman
Functions that have Read-Twice Constant Width Branching Programs are not Necessarily Testable. Computational Complexity Conference (2002)
Ilan Newman, Yuri Rabinovich
A lower bound on the distortion of embedding planar metrics into Euclidean space. SCG (2002)
Ilan Newman
Testing Membership in Languages that Have Small Width Branching Programs. SIAM J. Comput. 31 (5) (2002)
Adnan Agbaria, Yosi Ben-Asher, Ilan Newman
Communication - Processor Tradeoffs in a Limited Resources PRAM. Algorithmica 34 (3) (2002)
Eldar Fischer, Ilan Newman
Testing of matrix properties. STOC (2001)
Ilan Newman
Testing of Functions that have small width Branching Programs. FOCS (2000)
Pascal Berthomé, Torben Hagerup, Ilan Newman, Assaf Schuster
Self-Simulation for the Passive Optical Star. J. Algorithms 34 (1) (2000)
Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy
Regular Languages are Testable with a Constant Number of Queries. SIAM J. Comput. 30 (6) (2000)
Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy
Regular Languages Are Testable with a Constant Number of Queries. FOCS (1999)
Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair
-Embeddings of Graphs. FOCS (1999)

Ilan Newman.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Ilan Newman