Ilan Newman

	2012
102		Ilan Newman, Yuri Rabinovich: On multiplicative λ-approximations and some geometric applications. SODA 2012: 51-67
101		Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman, Orly Yahalom: On the query complexity of testing orientations for being Eulerian. ACM Transactions on Algorithms 8(2): 15 (2012)
100		Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg: Hierarchy Theorems for Property Testing. Computational Complexity 21(1): 129-192 (2012)
99		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 47(1): 187-214 (2012)
98		Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala: Local Versus Global Properties of Metric Spaces. SIAM J. Comput. 41(1): 250-271 (2012)
	2011
97		Ilan Newman, Christian Sohler: Every property of hyperfinite graphs is testable. STOC 2011: 675-684
96		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)
95		Oded Lachish, Ilan Newman: Testing Periodicity. Algorithmica 60(2): 401-420 (2011)
94		Oren Ben-Zwi, Ilan Newman: Optimal Bi-Valued Auctions CoRR abs/1106.4677: (2011)
93		Oren Ben-Zwi, Danny Hermelin, Daniel Lokshtanov, Ilan Newman: Treewidth governs the complexity of target set selection. Discrete Optimization 8(1): 87-96 (2011)
92		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)
91		Gad M. Landau, Avivit Levy, Ilan Newman: LCS approximation via embedding into locally non-repetitive strings. Inf. Comput. 209(4): 705-716 (2011)
	2010
90		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
89		Ilan Newman: Property Testing of Massively Parametrized Problems - A Survey. Property Testing 2010: 142-157
88		Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg: Hierarchy Theorems for Property Testing. Property Testing 2010: 289-294
87		Ilan Newman, Yuri Rabinovich: On Cut Dimension of $\ell_1$ Metrics and Volumes, and Related Sparsification Techniques CoRR abs/1002.3541: (2010)
86		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)
	2009
85		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: 355-362
84		Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg: Hierarchy Theorems for Property Testing. APPROX-RANDOM 2009: 504-519
83		Gad M. Landau, Avivit Levy, Ilan Newman: LCS Approximation via Embedding into Local Non-repetitive Strings. CPM 2009: 92-105
82		Oren Ben-Zwi, Ilan Newman, Guy Wolfovitz: A New Derandomization of Auctions. SAGT 2009: 233-237
81		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
80		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)
79		Ilan Newman: Computing in fault tolerant broadcast networks and noisy decision trees. Random Struct. Algorithms 34(4): 478-501 (2009)
78		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)
77		Ilan Newman, Yuri Rabinovich: Hard Metrics from Cayley Graphs of Abelian Groups. Theory of Computing 5(1): 125-134 (2009)
	2008
76		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
75		Roy Levin, Ilan Newman, Gadi Haber: Complementing Missing and Inaccurate Profiling Using a Minimum Cost Circulation Algorithm. HiPEAC 2008: 291-304
74		Oded Lachish, Ilan Newman, Asaf Shapira: Space Complexity Vs. Query Complexity. Computational Complexity 17(1): 70-93 (2008)
73		Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg: Hierarchy Theorems for Property Testing. Electronic Colloquium on Computational Complexity (ECCC) 15(097): (2008)
72		Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig: Quantum Property Testing. SIAM J. Comput. 37(5): 1387-1400 (2008)
	2007
71		Sourav Chakraborty, Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman: Testing st -Connectivity. APPROX-RANDOM 2007: 380-394
70		Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur: Testing Properties of Constraint-Graphs. IEEE Conference on Computational Complexity 2007: 264-277
69		Ilan Newman, Yuri Rabinovich: Hard Metrics from Cayley Graphs of Abelian Groups. STACS 2007: 157-162
68		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
67		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)
66		Eldar Fischer, Ilan Newman: Testing of matrix-poset properties. Combinatorica 27(3): 293-327 (2007)
65		Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur: Testing Properties of Constraint-Graphs. Electronic Colloquium on Computational Complexity (ECCC) 14(054): (2007)
64		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)
63		Oren Ben-Zwi, Oded Lachish, Ilan Newman: Lower bounds for testing Euclidean Minimum Spanning Trees. Inf. Process. Lett. 102(6): 219-225 (2007)
62		Eldar Fischer, Ilan Newman: Testing versus Estimation of Graph Properties. SIAM J. Comput. 37(2): 482-501 (2007)
61		Noga Alon, Eldar Fischer, Ilan Newman: Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs. SIAM J. Comput. 37(3): 959-976 (2007)
60		Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf: Robust Polynomials and Quantum Algorithms. Theory Comput. Syst. 40(4): 379-395 (2007)
	2006
59		Oded Lachish, Ilan Newman, Asaf Shapira: Space Complexity vs. Query Complexity. APPROX-RANDOM 2006: 426-437
58		Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala: Local versus global properties of metric spaces. SODA 2006: 41-50
57		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
56		Oded Lachish, Ilan Newman, Asaf Shapira: Space Complexity vs. Query Complexity. Electronic Colloquium on Computational Complexity (ECCC) 13(103): (2006)
55		Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair: Embedding k-Outerplanar Graphs into l 1. SIAM J. Discrete Math. 20(1): 119-136 (2006)
	2005
54		Oded Lachish, Ilan Newman: Testing Periodicity. APPROX-RANDOM 2005: 366-377
53		Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin: Increasing Kolmogorov Complexity. STACS 2005: 412-421
52		Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf: Robust Polynomials and Quantum Algorithms. STACS 2005: 593-604
51		Eldar Fischer, Ilan Newman: Testing versus estimation of graph properties. STOC 2005: 138-146
50		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)(095): (2005)
49		Oded Lachish, Ilan Newman: Languages that are Recognized by Simple Counter Automata are not necessarily Testable Electronic Colloquium on Computational Complexity (ECCC)(152): (2005)
48		Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur: Testing Orientation Properties Electronic Colloquium on Computational Complexity (ECCC)(153): (2005)
47		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)
	2004
46		Ilan Newman: Computing in Fault Tolerance Broadcast Networks. IEEE Conference on Computational Complexity 2004: 113-122
45		Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair: Cuts, Trees and l1-Embeddings of Graphs. Combinatorica 24(2): 233-269 (2004)
44		Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin: Increasing Kolmogorov Complexity Electronic Colloquium on Computational Complexity (ECCC)(081): (2004)
43		Oded Lachish, Ilan Newman: Testing Periodicity Electronic Colloquium on Computational Complexity (ECCC)(092): (2004)
42		Eldar Fischer, Ilan Newman, Jiri Sgall: Functions that have read-twice constant width branching programs are not necessarily testable. Random Struct. Algorithms 24(2): 175-193 (2004)
	2003
41		Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig: Quantum property testing. SODA 2003: 480-488
40		Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair: Embedding k-outerplanar graphs into l1. SODA 2003: 527-536
39		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
38		Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf: Robust Quantum Algorithms and Polynomials CoRR quant-ph/0309220: (2003)
	2002
37		Eldar Fischer, Ilan Newman: Functions that have Read-Twice Constant Width Branching Programs are not Necessarily Testable. IEEE Conference on Computational Complexity 2002: 73-79
36		Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky: Monotonicity testing over general poset domains. STOC 2002: 474-483
35		Ilan Newman, Yuri Rabinovich: A lower bound on the distortion of embedding planar metrics into Euclidean space. Symposium on Computational Geometry 2002: 94-96
34		Adnan Agbaria, Yosi Ben-Asher, Ilan Newman: Communication - Processor Tradeoffs in a Limited Resources PRAM. Algorithmica 34(3): 276-297 (2002)
33		Ilan Newman: Testing Membership in Languages that Have Small Width Branching Programs. SIAM J. Comput. 31(5): 1557-1570 (2002)
	2001
32		Eldar Fischer, Ilan Newman: Testing of matrix properties. STOC 2001: 286-295
	2000
31		Ilan Newman: Testing of Functions that have small width Branching Programs. FOCS 2000: 251-258
30		Pascal Berthomé, Torben Hagerup, Ilan Newman, Assaf Schuster: Self-Simulation for the Passive Optical Star. J. Algorithms 34(1): 128-147 (2000)
29		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)
	1999
28		Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair: Cuts, Trees and l1-Embeddings of Graphs. FOCS 1999: 399-409
27		Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy: Regular Languages Are Testable with a Constant Number of Queries. FOCS 1999: 645-655
26		Adnan Agbaria, Yosi Ben-Asher, Ilan Newman: Communication-Processor Tradeoffs in Limited Resources PRAM. SPAA 1999: 74-82
25		Yosi Ben-Asher, Eitan Farchi, Ilan Newman: Optimal Search in Trees. SIAM J. Comput. 28(6): 2090-2102 (1999)
	1997
24		Yosi Ben-Asher, Eitan Farchi, Ilan Newman: Optimal Search in Trees: Extended Abstract + Appendix. SODA 1997: 739-746
23		Ishai Ben-Aroya, Ilan Newman, Assaf Schuster: Randomized Single-Target Hot-Potato Routing. J. Algorithms 23(1): 101-120 (1997)
22		Yosi Ben-Asher, Ilan Newman: Geometric Approach for Optimal Routing on a Mesh with Buses. J. Comput. Syst. Sci. 54(3): 475-486 (1997)
	1996
21		Ilan Newman, Mario Szegedy: Public vs. Private Coin Flips in One Round Communication Games (Extended Abstract). STOC 1996: 561-570
20		Yosi Ben-Asher, Ilan Newman: Optimal Search in Trees Electronic Colloquium on Computational Complexity (ECCC) 3(44): (1996)
19		Yosi Ben-Asher, Ilan Newman: Geometric Approach for Optimal Routing on Mesh with Buses Electronic Colloquium on Computational Complexity (ECCC) 3(53): (1996)
	1995
18		Pascal Berthomé, Th. Duboux, Torben Hagerup, Ilan Newman, Assaf Schuster: Self-Simulation for the Passive Optical Star Model. ESA 1995: 369-380
17		Ishai Ben-Aroya, Ilan Newman, Assaf Schuster: Randomized Single-Target Hot-Potato Routing. ISTCS 1995: 20-29
16		Yosi Ben-Asher, Ilan Newman: Decision Trees with AND, OR Queries. Structure in Complexity Theory Conference 1995: 74-81
15		Ilan Newman, Assaf Schuster: Hot-Potato Algorithms for Permutation Routing. IEEE Trans. Parallel Distrib. Syst. 6(11): 1168-1176 (1995)
14		Yosi Ben-Asher, Ilan Newman: Decision Trees with Boolean Threshold Queries. J. Comput. Syst. Sci. 51(3): 495-502 (1995)
13		Ilan Newman, Assaf Schuster: Hot Potato Worm Routing via Store-and-Forward Packet Routing. J. Parallel Distrib. Comput. 30(1): 76-84 (1995)
12		László Lovász, Moni Naor, Ilan Newman, Avi Wigderson: Search Problems in the Decision Tree Model. SIAM J. Discrete Math. 8(1): 119-132 (1995)
11		Ilan Newman, Avi Wigderson: Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy. SIAM J. Discrete Math. 8(4): 536-542 (1995)
	1994
10		Mauricio Karchmer, Ilan Newman, Michael E. Saks, Avi Wigderson: Non-Deterministic Communication Complexity with Few Witnesses. J. Comput. Syst. Sci. 49(2): 247-257 (1994)
	1993
9		Ilan Newman, Assaf Schuster: Hot-Potato Worm Routing is Almost as Easy as Store-and-Forward Packet Routing. ISTCS 1993: 202-211
8		Mauricio Karchmer, Nathan Linial, Ilan Newman, Michael E. Saks, Avi Wigderson: Combinatorial characterization of read-once formulae. Discrete Mathematics 114(1-3): 275-282 (1993)
7		Rafi Heiman, Ilan Newman, Avi Wigderson: On Read-Once Threshold Formulae and Their Randomized Decision in Tree Complexity. Theor. Comput. Sci. 107(1): 63-76 (1993)
	1992
6		Mauricio Karchmer, Ilan Newman, Michael E. Saks, Avi Wigderson: Non-deterministic Communication Complexity with Few Witness. Structure in Complexity Theory Conference 1992: 275-281
	1991
5		László Lovász, Moni Naor, Ilan Newman, Avi Wigderson: Search Problems in the Decision Tree Model (Preliminary Version) FOCS 1991: 576-585
4		Irith Ben-Arroyo Hartman, Ilan Newman, Ran Ziv: On grid intersection graphs. Discrete Mathematics 87(1): 41-52 (1991)
3		Ilan Newman: Private vs. Common Random Bits in Communication Complexity. Inf. Process. Lett. 39(2): 67-71 (1991)
	1990
2		Rafi Heiman, Ilan Newman, Avi Wigderson: On Read-Once Threshold Formulae and Their Randomized Decision Tree Complexity. Structure in Complexity Theory Conference 1990: 78-87
1		Ilan Newman, Prabhakar Ragde, Avi Wigderson: Perfect Hashing, Graph Entropy, and Circuit Complexity. Structure in Complexity Theory Conference 1990: 91-99

Coauthor Index

1	Adnan Agbaria	[26] [34]
2	Noga Alon	[27] [29] [50] [57] [61] [64] [78]
3	Sanjeev Arora	[58] [98]
4	Ishai Ben-Aroya	[17] [23]
5	Yosi Ben-Asher	[14] [16] [19] [20] [22] [24] [25] [26] [34]
6	Oren Ben-Zwi	[63] [82] [85] [92] [93] [94]
7	Pascal Berthomé	[18] [30]
8	Harry Buhrman	[38] [41] [44] [52] [53] [60] [72]
9	Jean Cardinal	[67] [68] [80] [81] [96]
10	Sourav Chakraborty	[71]
11	Chandra Chekuri	[40] [55]
12	Victor Chepoi	[86] [90] [99]
13	Artur Czumaj	[39] [47]
14	Erik D. Demaine	[67] [68] [80] [81] [96]
15	Feodor F. Dragan	[86] [90] [99]
16	Th. Duboux	[18]
17	Funda Ergün	[39] [47]
18	Eitan Farchi	[24] [25]
19	Samuel Fiorini	[67] [68] [80] [81] [96]
20	Eldar Fischer	[32] [36] [37] [42] [51] [57] [61] [62] [66] [71] [76] [78] [101]
21	Lance Fortnow	[39] [41] [44] [47] [53] [72]
22	Oded Goldreich	[73] [84] [88] [100]
23	Anupam Gupta	[28] [40] [45] [55]
24	Gadi Haber	[75]
25	Torben Hagerup	[18] [30]
26	Shirley Halevy	[48] [65] [70]
27	Irith Ben-Arroyo Hartman	[4]
28	Rafi Heiman	[2] [7]
29	Danny Hermelin	[85] [93]
30	Gwenaël Joret	[67] [68] [80] [81] [96]
31	Mauricio Karchmer	[6] [8] [10]
32	Daniel Keren	[92]
33	Igor Kleiner	[92]
34	Michael Krivelevich	[27] [29] [73] [84] [88] [100]
35	Oded Lachish	[43] [48] [49] [54] [56] [59] [63] [65] [70] [71] [74] [76] [95] [101]
36	Gad M. Landau	[83] [91]
37	Stefan Langerman	[67] [68] [96]
38	Eric Lehman	[36]
39	Roy Levin	[75]
40	Avivit Levy (Avivit Kapah-Levy)	[83] [91]
41	Nathan Linial (Nati Linial)	[8]
42	Daniel Lokshtanov	[85] [93]
43	László Lovász	[5] [12] [58] [98]
44	Avner Magen	[39] [47]
45	Arie Matsliah	[71] [76] [101]
46	Moni Naor	[5] [12]
47	Yuval Rabani	[58] [98]
48	Yuri Rabinovich	[28] [35] [40] [45] [55] [58] [69] [77] [86] [87] [90] [98] [99] [102]
49	Prabhakar Ragde	[1]
50	Sofya Raskhodnikova	[36]
51	Hein Röhrig	[38] [41] [52] [60] [72]
52	Eyal Rozenberg	[73] [84] [88] [100]
53	Ronitt Rubinfeld	[36] [39] [47]
54	Michael E. Saks (Michael Saks)	[6] [8] [10]
55	Alex Samorodnitsky	[36]
56	Assaf Schuster	[9] [13] [15] [17] [18] [23] [30]
57	Jiri Sgall	[42]
58	Asaf Shapira	[56] [57] [59] [74] [78]
59	Alexander Shen	[50] [64]
60	Alistair Sinclair	[28] [40] [45] [55]
61	Christian Sohler	[39] [47] [97]
62	Mario Szegedy	[21] [27] [29]
63	Gábor Tardos	[50] [64]
64	Dekel Tsur	[48] [65] [70]
65	Yann Vaxès	[86] [90] [99]
66	Santosh Vempala	[58] [98]
67	Nikolai K. Vereshchagin (Nikolay K. Vereshchagin)	[44] [50] [53] [64]
68	Oren Weimann	[67] [68] [80] [81] [96]
69	Avi Wigderson	[1] [2] [5] [6] [7] [8] [10] [11] [12]
70	Ronald de Wolf	[38] [52] [60]
71	Guy Wolfovitz	[82]
72	Orly Yahalom	[76] [101]
73	Ran Ziv	[4]

Colors in the list of coauthors

Last update Sun Jun 3 16:06:10 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page