Ilan Newman

According to our database, Ilan Newman authored at least 96 papers between 1990 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Strongly Sublinear Algorithms for Testing Pattern Freeness.

Ilan Newman, Nithin Varma

TheoretiCS, 2024

2023

Hardness Condensation by Restriction.

Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2023

No Ascending Auction can find Equilibrium for SubModular valuations.

Oren Ben-Zwi, Ilan Newman

CoRR, 2023

2022

Parameterized Convexity Testing.

Abhiruk Lahiri, Ilan Newman, Nithin Varma

Proceedings of the 5th Symposium on Simplicity in Algorithms, 2022

Query Complexity

Mario Szegedy, Ilan Newman, Troy Lee

WorldScientific, ISBN: 9789813223226, 2022

2021

Hamiltonian and pseudo-Hamiltonian cycles and fillings in simplicial complexes.

Rogers Mathew, Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad

J. Comb. Theory, Ser. B, 2021

Coresets for Decision Trees of Signals.

Ibrahim Jubran, Ernesto Evgeniy Sanches Shayda, Ilan Newman, Dan Feldman

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

New Sublinear Algorithms and Lower Bounds for LIS Estimation.

Ilan Newman, Nithin Varma

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

New Algorithms and Lower Bounds for LIS Estimation.

Ilan Newman, Nithin Varma

CoRR, 2020

On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs.

Hiro Ito, Areej Khoury, Ilan Newman

Comput. Complex., 2020

Online Embedding of Metrics.

Ilan Newman, Yuri Rabinovich

Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory, 2020

2019

Testing for forbidden order patterns in an array.

Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad, Christian Sohler

Random Struct. Algorithms, 2019

On the Characterization of 1-sided error Strongly-Testable Graph Properties for bounded-degree graphs, including an appendix.

Hiro Ito, Areej Khoury, Ilan Newman

CoRR, 2019

Contractors' minimum spanning tree.

Irith Ben-Arroyo Hartman, Ilan Newman

Australas. J Comb., 2019

2016

Every Property of Outerplanar Graphs is Testable.

Jasine Babu, Areej Khoury, Ilan Newman

Proceedings of the Approximation, 2016

2015

Hats, auctions and derandomization.

Oren Ben-Zwi, Ilan Newman, Guy Wolfovitz

Random Struct. Algorithms, 2015

2013

Every Property of Hyperfinite Graphs Is Testable.

Ilan Newman, Christian Sohler

SIAM J. Comput., 2013

On Multiplicative Lambda-Approximations and Some Geometric Applications.

Ilan Newman, Yuri Rabinovich

SIAM J. Comput., 2013

The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs.

Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Ilan Newman, Oren Weimann

J. Comb. Optim., 2013

Ascending auctions and Walrasian equilibrium

Oren Ben-Zwi, Ron Lavi, Ilan Newman

CoRR, 2013

2012

On the query complexity of testing orientations for being Eulerian.

Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman, Orly Yahalom

ACM Trans. Algorithms, 2012

Local Versus Global Properties of Metric Spaces.

Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh S. Vempala

SIAM J. Comput., 2012

Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs.

Victor Chepoi, Feodor F. Dragan, Ilan Newman, Yuri Rabinovich, Yann Vaxès

Discret. Comput. Geom., 2012

Hierarchy Theorems for Property Testing.

Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg

Comput. Complex., 2012

On multiplicative λ-approximations and some geometric applications.

Ilan Newman, Yuri Rabinovich

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011

Applying Property Testing to an Image Partitioning Problem.

Igor Kleiner, Daniel Keren, Ilan Newman, Oren Ben-Zwi

IEEE Trans. Pattern Anal. Mach. Intell., 2011

LCS approximation via embedding into locally non-repetitive strings.

Gad M. Landau, Avivit Levy, Ilan Newman

Inf. Comput., 2011

Treewidth governs the complexity of target set selection.

Oren Ben-Zwi, Danny Hermelin, Daniel Lokshtanov, Ilan Newman

Discret. Optim., 2011

Optimal Bi-Valued Auctions

Oren Ben-Zwi, Ilan Newman

CoRR, 2011

Testing Periodicity.

Oded Lachish, Ilan Newman

Algorithmica, 2011

The Stackelberg Minimum Spanning Tree Game.

Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, Oren Weimann

Algorithmica, 2011

2010

On Cut Dimension of ℓ₁ Metrics and Volumes, and Related Sparsification Techniques

Ilan Newman, Yuri Rabinovich

CoRR, 2010

Property Testing of Massively Parametrized Problems - A Survey.

Ilan Newman

Proceedings of the Property Testing - Current Research and Surveys, 2010

Hierarchy Theorems for Property Testing.

Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg

Proceedings of the Property Testing - Current Research and Surveys, 2010

2009

Hard Metrics from Cayley Graphs of Abelian Groups.

Ilan Newman, Yuri Rabinovich

Theory Comput., 2009

A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity.

Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira

SIAM J. Comput., 2009

Computing in fault tolerant broadcast networks and noisy decision trees.

Ilan Newman

Random Struct. Algorithms, 2009

An exact almost optimal algorithm for target set selection in social networks.

Oren Ben-Zwi, Danny Hermelin, Daniel Lokshtanov, Ilan Newman

Proceedings of the Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), 2009

A New Derandomization of Auctions.

Oren Ben-Zwi, Ilan Newman, Guy Wolfovitz

Proceedings of the Algorithmic Game Theory, Second International Symposium, 2009

LCS Approximation via Embedding into Local Non-repetitive Strings.

Gad M. Landau, Avivit Levy, Ilan Newman

Proceedings of the Combinatorial Pattern Matching, 20th Annual Symposium, 2009

2008

Quantum Property Testing.

Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig

SIAM J. Comput., 2008

Space Complexity Vs. Query Complexity.

Oded Lachish, Ilan Newman, Asaf Shapira

Comput. Complex., 2008

Complementing Missing and Inaccurate Profiling Using a Minimum Cost Circulation Algorithm.

Roy Levin, Ilan Newman, Gadi Haber

Proceedings of the High Performance Embedded Architectures and Compilers, 2008

2007

Testing versus Estimation of Graph Properties.

Eldar Fischer, Ilan Newman

SIAM J. Comput., 2007

Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs.

Noga Alon, Eldar Fischer, Ilan Newman

SIAM J. Comput., 2007

Robust Polynomials and Quantum Algorithms.

Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf

Theory Comput. Syst., 2007

Lower bounds for testing Euclidean Minimum Spanning Trees.

Oren Ben-Zwi, Oded Lachish, Ilan Newman

Inf. Process. Lett., 2007

Partitioning multi-dimensional sets in a small number of "uniform" parts.

Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin

Eur. J. Comb., 2007

Testing Properties of Constraint-Graphs.

Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur

Electron. Colloquium Comput. Complex., 2007

Testing of matrix-poset properties.

Eldar Fischer, Ilan Newman

Comb., 2007

Testing <i>st</i> -Connectivity.

Sourav Chakraborty, Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman

Proceedings of the Approximation, 2007

2006

Embedding <i>k</i>-Outerplanar Graphs into <i>l</i> ₁.

Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair

SIAM J. Discret. Math., 2006

2005

Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time.

Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler

SIAM J. Comput., 2005

Testing Orientation Properties

Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur

Electron. Colloquium Comput. Complex., 2005

Languages that are Recognized by Simple Counter Automata are not necessarily Testable

Oded Lachish, Ilan Newman

Electron. Colloquium Comput. Complex., 2005

2004

Functions that have read-twice constant width branching programs are not necessarily testable.

Eldar Fischer, Ilan Newman, Jirí Sgall

Random Struct. Algorithms, 2004

Increasing Kolmogorov Complexity

Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin

Electron. Colloquium Comput. Complex., 2004

Cuts, Trees and l₁-Embeddings of Graphs.

Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair

Comb., 2004

Computing in Fault Tolerance Broadcast Networks.

Ilan Newman

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

2003

Robust Quantum Algorithms and Polynomials

Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf

CoRR, 2003

Sublinear-time approximation of Euclidean minimum spanning tree.

Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Embedding k-outerplanar graphs into l1.

Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

2002

Testing Membership in Languages that Have Small Width Branching Programs.

Ilan Newman

SIAM J. Comput., 2002

Communication - Processor Tradeoffs in a Limited Resources PRAM.

Adnan Agbaria, Yosi Ben-Asher, Ilan Newman

Algorithmica, 2002

Monotonicity testing over general poset domains.

Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

A lower bound on the distortion of embedding planar metrics into Euclidean space.

Ilan Newman, Yuri Rabinovich

Proceedings of the 18th Annual Symposium on Computational Geometry, 2002

Functions that have Read-Twice Constant Width Branching Programs are not Necessarily Testable.

Eldar Fischer, Ilan Newman

Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001

Testing of matrix properties.

Eldar Fischer, Ilan Newman

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

2000

Regular Languages are Testable with a Constant Number of Queries.

Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy

SIAM J. Comput., 2000

Self-Simulation for the Passive Optical Star.

Pascal Berthomé, Torben Hagerup, Ilan Newman, Assaf Schuster

J. Algorithms, 2000

Testing of Functions that have small width Branching Programs.

Ilan Newman

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999

Optimal Search in Trees.

Yosi Ben-Asher, Eitan Farchi, Ilan Newman

SIAM J. Comput., 1999

1998

Broadcasting on a budget in the multi-service communication model.

Gene Itkis, Ilan Newman, Assaf Schuster

Proceedings of the 5th International Conference On High Performance Computing, 1998

1997

Geometric Approach for Optimal Routing on a Mesh with Buses.

Yosi Ben-Asher, Ilan Newman

J. Comput. Syst. Sci., 1997

Randomized Single-Target Hot-Potato Routing.

Ishai Ben-Aroya, Ilan Newman, Assaf Schuster

J. Algorithms, 1997

Optimal Search in Trees: Extended Abstract + Appendix.

Yosi Ben-Asher, Eitan Farchi, Ilan Newman

Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

1996

Optimal Search in Trees

Yosi Ben-Asher, Ilan Newman

Electron. Colloquium Comput. Complex., 1996

Public vs. Private Coin Flips in One Round Communication Games (Extended Abstract).

Ilan Newman, Mario Szegedy

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

1995

Hot-Potato Algorithms for Permutation Routing.

Ilan Newman, Assaf Schuster

IEEE Trans. Parallel Distributed Syst., 1995

Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy.

Ilan Newman, Avi Wigderson

SIAM J. Discret. Math., 1995

Search Problems in the Decision Tree Model.

László Lovász, Moni Naor, Ilan Newman, Avi Wigderson

SIAM J. Discret. Math., 1995

Hot Potato Worm Routing via Store-and-Forward Packet Routing.

Ilan Newman, Assaf Schuster

J. Parallel Distributed Comput., 1995

Decision Trees with Boolean Threshold Queries.

Yosi Ben-Asher, Ilan Newman

J. Comput. Syst. Sci., 1995

Self-Simulation for the Passive Optical Star Model.

Pascal Berthomé, Th. Duboux, Torben Hagerup, Ilan Newman, Assaf Schuster

Proceedings of the Algorithms, 1995

Decision Trees with AND, OR Queries.

Yosi Ben-Asher, Ilan Newman

Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

1994

Non-Deterministic Communication Complexity with Few Witnesses.

Mauricio Karchmer, Ilan Newman, Michael E. Saks, Avi Wigderson

J. Comput. Syst. Sci., 1994

1993

On Read-Once Threshold Formulae and Their Randomized Decision in Tree Complexity.

Rafi Heiman, Ilan Newman, Avi Wigderson

Theor. Comput. Sci., 1993

Combinatorial characterization of read-once formulae.

Mauricio Karchmer, Nathan Linial, Ilan Newman, Michael E. Saks, Avi Wigderson

Discret. Math., 1993

Hot-Potato Worm Routing is Almost as Easy as Store-and-Forward Packet Routing.

Ilan Newman, Assaf Schuster

Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993

1992

Non-deterministic Communication Complexity with Few Witness.

Mauricio Karchmer, Ilan Newman, Michael E. Saks, Avi Wigderson

Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

1991

On the formula complexity of simple Boolean functions (על סבוכיות הנסחא של פונקציות בוליאניות פשוטות.).

Ilan Newman

PhD thesis, 1991

Private vs. Common Random Bits in Communication Complexity.

Ilan Newman

Inf. Process. Lett., 1991

On grid intersection graphs.

Irith Ben-Arroyo Hartman, Ilan Newman, Ran Ziv

Discret. Math., 1991

Search Problems in the Decision Tree Model (Preliminary Version)

László Lovász, Moni Naor, Ilan Newman, Avi Wigderson

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990

Approximation algorithms for covering a graph by vertex-disjoint paths of maximum total weight.

Shlomo Moran, Ilan Newman, Yaron Wolfstahl

Networks, 1990

Perfect Hashing, Graph Entropy, and Circuit Complexity.

Ilan Newman, Prabhakar Ragde, Avi Wigderson

Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990