default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDIlan Newman
Person information
- affiliation: University of Haifa, Israel
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[j51]Ilan Newman, Nithin Varma:
Strongly Sublinear Algorithms for Testing Pattern Freeness. TheoretiCS 3 (2024)- [c53]Mika Göös
, Ilan Newman, Artur Riazanov, Dmitry Sokolov:
Hardness Condensation by Restriction. STOC 2024: 2016-2027 - 2023
- [i25]Ilan Newman, Yuri Rabinovich:
Online embedding of metrics. CoRR abs/2303.15945 (2023) - [i24]Oren Ben-Zwi, Ilan Newman:
No Ascending Auction can find Equilibrium for SubModular valuations. CoRR abs/2312.00522 (2023) - [i23]Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov:
Hardness Condensation by Restriction. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [b2]Mario Szegedy, Ilan Newman, Troy Lee:
Query Complexity. WorldScientific 2022, ISBN 9789813223202, pp. 1-200 - [c52]Ilan Newman, Nithin Varma:
Strongly Sublinear Algorithms for Testing Pattern Freeness. ICALP 2022: 98:1-98:20 - [c51]Abhiruk Lahiri, Ilan Newman, Nithin Varma:
Parameterized Convexity Testing. SOSA 2022: 174-181 - 2021
- [j50]Rogers Mathew, Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad:
Hamiltonian and pseudo-Hamiltonian cycles and fillings in simplicial complexes. J. Comb. Theory B 150: 119-143 (2021) - [c50]Ilan Newman, Nithin Varma:
New Sublinear Algorithms and Lower Bounds for LIS Estimation. ICALP 2021: 100:1-100:20 - [c49]Ibrahim Jubran, Ernesto Evgeniy Sanches Shayda, Ilan Newman, Dan Feldman:
Coresets for Decision Trees of Signals. NeurIPS 2021: 30352-30364 - [i22]Ilan Newman, Nithin Varma:
Strongly Sublinear Algorithms for Testing Pattern Freeness. CoRR abs/2106.04856 (2021) - [i21]Ibrahim Jubran, Ernesto Evgeniy Sanches Shayda, Ilan Newman, Dan Feldman:
Coresets for Decision Trees of Signals. CoRR abs/2110.03195 (2021) - [i20]Abhiruk Lahiri, Ilan Newman, Nithin Varma:
Parameterized Convexity Testing. CoRR abs/2110.13012 (2021) - 2020
- [j49]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): 1 (2020) - [c48]Ilan Newman, Yuri Rabinovich:
Online Embedding of Metrics. SWAT 2020: 32:1-32:13 - [i19]Ilan Newman, Nithin Varma:
New Algorithms and Lower Bounds for LIS Estimation. CoRR abs/2010.05805 (2020)
2010 – 2019
- 2019
- [j48]Irith Ben-Arroyo Hartman, Ilan Newman:
Contractors' minimum spanning tree. Australas. J Comb. 74: 33-45 (2019) - [j47]Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad, Christian Sohler:
Testing for forbidden order patterns in an array. Random Struct. Algorithms 55(2): 402-426 (2019) - [i18]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 abs/1909.09984 (2019) - 2017
- [c47]Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad, Christian Sohler:
Testing for Forbidden Order Patterns in an Array. SODA 2017: 1582-1597 - 2016
- [c46]Jasine Babu, Areej Khoury, Ilan Newman:
Every Property of Outerplanar Graphs is Testable. APPROX-RANDOM 2016: 21:1-21:19 - 2015
- [j46]Oren Ben-Zwi, Ilan Newman, Guy Wolfovitz:
Hats, auctions and derandomization. Random Struct. Algorithms 46(3): 478-493 (2015) - 2013
- [j45]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): 19-46 (2013) - [j44]Ilan Newman, Yuri Rabinovich:
On Multiplicative Lambda-Approximations and Some Geometric Applications. SIAM J. Comput. 42(3): 855-883 (2013) - [j43]Ilan Newman, Christian Sohler:
Every Property of Hyperfinite Graphs Is Testable. SIAM J. Comput. 42(3): 1095-1112 (2013) - [i17]Oren Ben-Zwi, Ron Lavi, Ilan Newman:
Ascending auctions and Walrasian equilibrium. CoRR abs/1301.1153 (2013) - 2012
- [j42]Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg:
Hierarchy Theorems for Property Testing. Comput. Complex. 21(1): 129-192 (2012) - [j41]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): 187-214 (2012) - [j40]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): 250-271 (2012) - [j39]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): 15:1-15:41 (2012) - [c45]Ilan Newman, Yuri Rabinovich:
On multiplicative λ-approximations and some geometric applications. SODA 2012: 51-67 - 2011
- [j38]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): 129-144 (2011) - [j37]Oded Lachish, Ilan Newman:
Testing Periodicity. Algorithmica 60(2): 401-420 (2011) - [j36]Oren Ben-Zwi, Danny Hermelin, Daniel Lokshtanov, Ilan Newman:
Treewidth governs the complexity of target set selection. Discret. Optim. 8(1): 87-96 (2011) - [j35]Gad M. Landau, Avivit Levy, Ilan Newman:
LCS approximation via embedding into locally non-repetitive strings. Inf. Comput. 209(4): 705-716 (2011) - [j34]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): 256-265 (2011) - [c44]Ilan Newman, Christian Sohler:
Every property of hyperfinite graphs is testable. STOC 2011: 675-684 - [i16]Oren Ben-Zwi, Ilan Newman:
Optimal Bi-Valued Auctions. CoRR abs/1106.4677 (2011) - 2010
- [c43]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: 95-109 - [p2]Ilan Newman:
Property Testing of Massively Parametrized Problems - A Survey. Property Testing 2010: 142-157 - [p1]Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg:
Hierarchy Theorems for Property Testing. Property Testing 2010: 289-294 - [i15]Ilan Newman, Yuri Rabinovich:
On Cut Dimension of ℓ1 Metrics and Volumes, and Related Sparsification Techniques. CoRR abs/1002.3541 (2010) - [i14]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 abs/1007.0489 (2010)
2000 – 2009
- 2009
- [j33]Ilan Newman:
Computing in fault tolerant broadcast networks and noisy decision trees. Random Struct. Algorithms 34(4): 478-501 (2009) - [j32]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): 143-167 (2009) - [j31]Ilan Newman, Yuri Rabinovich:
Hard Metrics from Cayley Graphs of Abelian Groups. Theory Comput. 5(1): 125-134 (2009) - [c42]Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg:
Hierarchy Theorems for Property Testing. APPROX-RANDOM 2009: 504-519 - [c41]Gad M. Landau, Avivit Levy, Ilan Newman:
LCS Approximation via Embedding into Local Non-repetitive Strings. CPM 2009: 92-105 - [c40]Oren Ben-Zwi, Ilan Newman, Guy Wolfovitz:
A New Derandomization of Auctions. SAGT 2009: 233-237 - [c39]Oren Ben-Zwi, Danny Hermelin, Daniel Lokshtanov, Ilan Newman:
An exact almost optimal algorithm for target set selection in social networks. EC 2009: 355-362 - [c38]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: 125-136 - [i13]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 abs/0909.3221 (2009) - 2008
- [j30]Oded Lachish, Ilan Newman, Asaf Shapira:
Space Complexity Vs. Query Complexity. Comput. Complex. 17(1): 70-93 (2008) - [j29]Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig:
Quantum Property Testing. SIAM J. Comput. 37(5): 1387-1400 (2008) - [c37]Eldar Fischer, Oded Lachish, Ilan Newman, Arie Matsliah, Orly Yahalom:
On the Query Complexity of Testing Orientations for Being Eulerian. APPROX-RANDOM 2008: 402-415 - [c36]Roy Levin, Ilan Newman, Gadi Haber:
Complementing Missing and Inaccurate Profiling Using a Minimum Cost Circulation Algorithm. HiPEAC 2008: 291-304 - [i12]Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg:
Hierarchy Theorems for Property Testing. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [j28]Eldar Fischer, Ilan Newman:
Testing of matrix-poset properties. Comb. 27(3): 293-327 (2007) - [j27]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): 134-144 (2007) - [j26]Oren Ben-Zwi, Oded Lachish, Ilan Newman:
Lower bounds for testing Euclidean Minimum Spanning Trees. Inf. Process. Lett. 102(6): 219-225 (2007) - [j25]Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf:
Robust Polynomials and Quantum Algorithms. Theory Comput. Syst. 40(4): 379-395 (2007) - [j24]Eldar Fischer, Ilan Newman:
Testing versus Estimation of Graph Properties. SIAM J. Comput. 37(2): 482-501 (2007) - [j23]Noga Alon, Eldar Fischer, Ilan Newman:
Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs. SIAM J. Comput. 37(3): 959-976 (2007) - [c35]Sourav Chakraborty, Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman:
Testing st -Connectivity. APPROX-RANDOM 2007: 380-394 - [c34]Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur:
Testing Properties of Constraint-Graphs. CCC 2007: 264-277 - [c33]Ilan Newman, Yuri Rabinovich:
Hard Metrics from Cayley Graphs of Abelian Groups. STACS 2007: 157-162 - [c32]Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, Oren Weimann:
The Stackelberg Minimum Spanning Tree Game. WADS 2007: 64-76 - [i11]Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, Oren Weimann:
The Stackelberg Minimum Spanning Tree Game. CoRR abs/cs/0703019 (2007) - [i10]Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur:
Testing Properties of Constraint-Graphs. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [j22]Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair:
Embedding k-Outerplanar Graphs into l 1. SIAM J. Discret. Math. 20(1): 119-136 (2006) - [c31]Oded Lachish, Ilan Newman, Asaf Shapira:
Space Complexity vs. Query Complexity. APPROX-RANDOM 2006: 426-437 - [c30]Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh S. Vempala:
Local versus global properties of metric spaces. SODA 2006: 41-50 - [c29]Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira:
A combinatorial characterization of the testable graph properties: it's all about regularity. STOC 2006: 251-260 - [i9]Oded Lachish, Ilan Newman, Asaf Shapira:
Space Complexity vs. Query Complexity. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [j21]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): 91-109 (2005) - [c28]Oded Lachish, Ilan Newman:
Testing Periodicity. APPROX-RANDOM 2005: 366-377 - [c27]Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin:
Increasing Kolmogorov Complexity. STACS 2005: 412-421 - [c26]Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf:
Robust Polynomials and Quantum Algorithms. STACS 2005: 593-604 - [c25]Eldar Fischer, Ilan Newman:
Testing versus estimation of graph properties. STOC 2005: 138-146 - [i8]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. TR05 (2005) - [i7]Oded Lachish, Ilan Newman:
Languages that are Recognized by Simple Counter Automata are not necessarily Testable. Electron. Colloquium Comput. Complex. TR05 (2005) - [i6]Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur:
Testing Orientation Properties. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [j20]Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair:
Cuts, Trees and l1-Embeddings of Graphs. Comb. 24(2): 233-269 (2004) - [j19]Eldar Fischer, Ilan Newman, Jirí Sgall:
Functions that have read-twice constant width branching programs are not necessarily testable. Random Struct. Algorithms 24(2): 175-193 (2004) - [c24]Ilan Newman:
Computing in Fault Tolerance Broadcast Networks. CCC 2004: 113-122 - [i5]Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin:
Increasing Kolmogorov Complexity. Electron. Colloquium Comput. Complex. TR04 (2004) - [i4]Oded Lachish, Ilan Newman:
Testing Periodicity. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [c23]Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig:
Quantum property testing. SODA 2003: 480-488 - [c22]Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair:
Embedding k-outerplanar graphs into l1. SODA 2003: 527-536 - [c21]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: 813-822 - [i3]Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf:
Robust Quantum Algorithms and Polynomials. CoRR quant-ph/0309220 (2003) - 2002
- [j18]Adnan Agbaria, Yosi Ben-Asher, Ilan Newman:
Communication - Processor Tradeoffs in a Limited Resources PRAM. Algorithmica 34(3): 276-297 (2002) - [j17]Ilan Newman:
Testing Membership in Languages that Have Small Width Branching Programs. SIAM J. Comput. 31(5): 1557-1570 (2002) - [c20]Eldar Fischer, Ilan Newman:
Functions that have Read-Twice Constant Width Branching Programs are not Necessarily Testable. CCC 2002: 73-79 - [c19]Ilan Newman, Yuri Rabinovich:
A lower bound on the distortion of embedding planar metrics into Euclidean space. SCG 2002: 94-96 - [c18]Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky:
Monotonicity testing over general poset domains. STOC 2002: 474-483 - 2001
- [c17]Eldar Fischer, Ilan Newman:
Testing of matrix properties. STOC 2001: 286-295 - 2000
- [j16]Pascal Berthomé, Torben Hagerup, Ilan Newman, Assaf Schuster:
Self-Simulation for the Passive Optical Star. J. Algorithms 34(1): 128-147 (2000) - [j15]Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy:
Regular Languages are Testable with a Constant Number of Queries. SIAM J. Comput. 30(6): 1842-1862 (2000) - [c16]Ilan Newman:
Testing of Functions that have small width Branching Programs. FOCS 2000: 251-258
1990 – 1999
- 1999
- [j14]Yosi Ben-Asher, Eitan Farchi, Ilan Newman:
Optimal Search in Trees. SIAM J. Comput. 28(6): 2090-2102 (1999) - [c15]Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair:
Cuts, Trees and l1-Embeddings of Graphs. FOCS 1999: 399-409 - [c14]Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy:
Regular Languages Are Testable with a Constant Number of Queries. FOCS 1999: 645-655 - [c13]Adnan Agbaria, Yosi Ben-Asher, Ilan Newman:
Communication-Processor Tradeoffs in Limited Resources PRAM. SPAA 1999: 74-82 - 1998
- [c12]Gene Itkis, Ilan Newman, Assaf Schuster:
Broadcasting on a budget in the multi-service communication model. HiPC 1998: 163-170 - 1997
- [j13]Ishai Ben-Aroya, Ilan Newman, Assaf Schuster:
Randomized Single-Target Hot-Potato Routing. J. Algorithms 23(1): 101-120 (1997) - [j12]Yosi Ben-Asher, Ilan Newman:
Geometric Approach for Optimal Routing on a Mesh with Buses. J. Comput. Syst. Sci. 54(3): 475-486 (1997) - [c11]Yosi Ben-Asher, Eitan Farchi, Ilan Newman:
Optimal Search in Trees: Extended Abstract + Appendix. SODA 1997: 739-746 - 1996
- [c10]Ilan Newman, Mario Szegedy:
Public vs. Private Coin Flips in One Round Communication Games (Extended Abstract). STOC 1996: 561-570 - [i2]Yosi Ben-Asher, Ilan Newman:
Optimal Search in Trees. Electron. Colloquium Comput. Complex. TR96 (1996) - [i1]Yosi Ben-Asher, Ilan Newman:
Geometric Approach for Optimal Routing on Mesh with Buses. Electron. Colloquium Comput. Complex. TR96 (1996) - 1995
- [j11]Yosi Ben-Asher, Ilan Newman:
Decision Trees with Boolean Threshold Queries. J. Comput. Syst. Sci. 51(3): 495-502 (1995) - [j10]Ilan Newman, Assaf Schuster:
Hot Potato Worm Routing via Store-and-Forward Packet Routing. J. Parallel Distributed Comput. 30(1): 76-84 (1995) - [j9]László Lovász, Moni Naor, Ilan Newman, Avi Wigderson:
Search Problems in the Decision Tree Model. SIAM J. Discret. Math. 8(1): 119-132 (1995) - [j8]Ilan Newman, Avi Wigderson:
Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy. SIAM J. Discret. Math. 8(4): 536-542 (1995) - [j7]Ilan Newman, Assaf Schuster:
Hot-Potato Algorithms for Permutation Routing. IEEE Trans. Parallel Distributed Syst. 6(11): 1168-1176 (1995) - [c9]Yosi Ben-Asher, Ilan Newman:
Decision Trees with AND, OR Queries. SCT 1995: 74-81 - [c8]Pascal Berthomé, Th. Duboux, Torben Hagerup, Ilan Newman, Assaf Schuster:
Self-Simulation for the Passive Optical Star Model. ESA 1995: 369-380 - [c7]Ishai Ben-Aroya, Ilan Newman, Assaf Schuster:
Randomized Single-Target Hot-Potato Routing. ISTCS 1995: 20-29 - [c6]