dblp.uni-trier.dewww.uni-trier.de

Ilan Newman Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo
Home Page

*2009
80EEOren 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
79EEOded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg: Hierarchy Theorems for Property Testing. APPROX-RANDOM 2009: 504-519
78EEGad M. Landau, Avivit Levy, Ilan Newman: LCS Approximation via Embedding into Local Non-repetitive Strings. CPM 2009: 92-105
77EEOren Ben-Zwi, Ilan Newman, Guy Wolfovitz: A New Derandomization of Auctions. SAGT 2009: 233-237
76EEJean 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
75EEEldar Fischer, Oded Lachish, Ilan Newman, Arie Matsliah, Orly Yahalom: On the Query Complexity of Testing Orientations for Being Eulerian. APPROX-RANDOM 2008: 402-415
74EERoy Levin, Ilan Newman, Gadi Haber: Complementing Missing and Inaccurate Profiling Using a Minimum Cost Circulation Algorithm. HiPEAC 2008: 291-304
73EEOded Lachish, Ilan Newman, Asaf Shapira: Space Complexity Vs. Query Complexity. Computational Complexity 17(1): 70-93 (2008)
72EEOded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg: Hierarchy Theorems for Property Testing. Electronic Colloquium on Computational Complexity (ECCC) 15(097): (2008)
71EEHarry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig: Quantum Property Testing. SIAM J. Comput. 37(5): 1387-1400 (2008)
2007
70EESourav Chakraborty, Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman: Testing st -Connectivity. APPROX-RANDOM 2007: 380-394
69EEShirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur: Testing Properties of Constraint-Graphs. IEEE Conference on Computational Complexity 2007: 264-277
68EEIlan Newman, Yuri Rabinovich: Hard Metrics from Cayley Graphs of Abelian Groups. STACS 2007: 157-162
67EEJean 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
66EEJean 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)
65EEShirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur: Testing Properties of Constraint-Graphs. Electronic Colloquium on Computational Complexity (ECCC) 14(054): (2007)
64EENoga 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)
63EEOren Ben-Zwi, Oded Lachish, Ilan Newman: Lower bounds for testing Euclidean Minimum Spanning Trees. Inf. Process. Lett. 102(6): 219-225 (2007)
62EEEldar Fischer, Ilan Newman: Testing versus Estimation of Graph Properties. SIAM J. Comput. 37(2): 482-501 (2007)
61EENoga Alon, Eldar Fischer, Ilan Newman: Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs. SIAM J. Comput. 37(3): 959-976 (2007)
60EEHarry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf: Robust Polynomials and Quantum Algorithms. Theory Comput. Syst. 40(4): 379-395 (2007)
2006
59EEOded Lachish, Ilan Newman, Asaf Shapira: Space Complexity vs. Query Complexity. APPROX-RANDOM 2006: 426-437
58EESanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala: Local versus global properties of metric spaces. SODA 2006: 41-50
57EENoga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira: A combinatorial characterization of the testable graph properties: it's all about regularity. STOC 2006: 251-260
56EEOded Lachish, Ilan Newman, Asaf Shapira: Space Complexity vs. Query Complexity. Electronic Colloquium on Computational Complexity (ECCC) 13(103): (2006)
55EEChandra 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
54EEOded Lachish, Ilan Newman: Testing Periodicity. APPROX-RANDOM 2005: 366-377
53EEHarry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin: Increasing Kolmogorov Complexity. STACS 2005: 412-421
52EEHarry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf: Robust Polynomials and Quantum Algorithms. STACS 2005: 593-604
51EEEldar Fischer, Ilan Newman: Testing versus estimation of graph properties. STOC 2005: 138-146
50EENoga 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)
49EEOded Lachish, Ilan Newman: Languages that are Recognized by Simple Counter Automata are not necessarily Testable Electronic Colloquium on Computational Complexity (ECCC)(152): (2005)
48EEShirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur: Testing Orientation Properties Electronic Colloquium on Computational Complexity (ECCC)(153): (2005)
47EEArtur 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
46EEIlan Newman: Computing in Fault Tolerance Broadcast Networks. IEEE Conference on Computational Complexity 2004: 113-122
45EEAnupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair: Cuts, Trees and l1-Embeddings of Graphs. Combinatorica 24(2): 233-269 (2004)
44EEHarry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin: Increasing Kolmogorov Complexity Electronic Colloquium on Computational Complexity (ECCC)(081): (2004)
43EEOded Lachish, Ilan Newman: Testing Periodicity Electronic Colloquium on Computational Complexity (ECCC)(092): (2004)
42EEEldar 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
41EEHarry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig: Quantum property testing. SODA 2003: 480-488
40EEChandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair: Embedding k-outerplanar graphs into l1. SODA 2003: 527-536
39EEArtur 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
38EEHarry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf: Robust Quantum Algorithms and Polynomials CoRR quant-ph/0309220: (2003)
2002
37EEEldar Fischer, Ilan Newman: Functions that have Read-Twice Constant Width Branching Programs are not Necessarily Testable. IEEE Conference on Computational Complexity 2002: 73-79
36EEEldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky: Monotonicity testing over general poset domains. STOC 2002: 474-483
35EEIlan Newman, Yuri Rabinovich: A lower bound on the distortion of embedding planar metrics into Euclidean space. Symposium on Computational Geometry 2002: 94-96
34EEAdnan Agbaria, Yosi Ben-Asher, Ilan Newman: Communication - Processor Tradeoffs in a Limited Resources PRAM. Algorithmica 34(3): 276-297 (2002)
33EEIlan Newman: Testing Membership in Languages that Have Small Width Branching Programs. SIAM J. Comput. 31(5): 1557-1570 (2002)
2001
32EEEldar 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)
29EENoga 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
28EEAnupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair: Cuts, Trees and l1-Embeddings of Graphs. FOCS 1999: 399-409
27EENoga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy: Regular Languages Are Testable with a Constant Number of Queries. FOCS 1999: 645-655
26EEAdnan 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
21EEIlan Newman, Mario Szegedy: Public vs. Private Coin Flips in One Round Communication Games (Extended Abstract). STOC 1996: 561-570
20EEYosi Ben-Asher, Ilan Newman: Optimal Search in Trees Electronic Colloquium on Computational Complexity (ECCC) 3(44): (1996)
19EEYosi Ben-Asher, Ilan Newman: Geometric Approach for Optimal Routing on Mesh with Buses Electronic Colloquium on Computational Complexity (ECCC) 3(53): (1996)
1995
18EEPascal 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
15EEIlan 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)
13EEIlan Newman, Assaf Schuster: Hot Potato Worm Routing via Store-and-Forward Packet Routing. J. Parallel Distrib. Comput. 30(1): 76-84 (1995)
12EELá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)
11EEIlan 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
8EEMauricio 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
4EEIrith 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

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

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)