The SCEAS System
Navigation Menu

Search the dblp DataBase

Title:
Author:

Ilan Newman: [Publications] [Author Rank by year] [Co-authors] [Prefers] [Cites] [Cited by]

Publications of Author

  1. Oded Lachish, Ilan Newman
    Testing Periodicity. [Citation Graph (0, 0)][DBLP]
    APPROX-RANDOM, 2005, pp:366-377 [Conf]
  2. Oded Lachish, Ilan Newman, Asaf Shapira
    Space Complexity vs. Query Complexity. [Citation Graph (0, 0)][DBLP]
    APPROX-RANDOM, 2006, pp:426-437 [Conf]
  3. Yosi Ben-Asher, Ilan Newman
    Decision Trees with AND, OR Queries. [Citation Graph (0, 0)][DBLP]
    Structure in Complexity Theory Conference, 1995, pp:74-81 [Conf]
  4. Eldar Fischer, Ilan Newman
    Functions that have Read-Twice Constant Width Branching Programs are not Necessarily Testable. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 2002, pp:73-79 [Conf]
  5. Rafi Heiman, Ilan Newman, Avi Wigderson
    On Read-Once Threshold Formulae and Their Randomized Decision Tree Complexity. [Citation Graph (0, 0)][DBLP]
    Structure in Complexity Theory Conference, 1990, pp:78-87 [Conf]
  6. Mauricio Karchmer, Ilan Newman, Michael E. Saks, Avi Wigderson
    Non-deterministic Communication Complexity with Few Witness. [Citation Graph (0, 0)][DBLP]
    Structure in Complexity Theory Conference, 1992, pp:275-281 [Conf]
  7. Ilan Newman
    Computing in Fault Tolerance Broadcast Networks. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 2004, pp:113-122 [Conf]
  8. Ilan Newman, Prabhakar Ragde, Avi Wigderson
    Perfect Hashing, Graph Entropy, and Circuit Complexity. [Citation Graph (0, 0)][DBLP]
    Structure in Complexity Theory Conference, 1990, pp:91-99 [Conf]
  9. Ilan Newman, Yuri Rabinovich
    A lower bound on the distortion of embedding planar metrics into Euclidean space. [Citation Graph (0, 0)][DBLP]
    Symposium on Computational Geometry, 2002, pp:94-96 [Conf]
  10. Pascal Berthomé, Th. Duboux, Torben Hagerup, Ilan Newman, Assaf Schuster
    Self-Simulation for the Passive Optical Star Model. [Citation Graph (0, 0)][DBLP]
    ESA, 1995, pp:369-380 [Conf]
  11. Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy
    Regular Languages Are Testable with a Constant Number of Queries. [Citation Graph (0, 0)][DBLP]
    FOCS, 1999, pp:645-655 [Conf]
  12. Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair
    Cuts, Trees and l1-Embeddings of Graphs. [Citation Graph (0, 0)][DBLP]
    FOCS, 1999, pp:399-409 [Conf]
  13. László Lovász, Moni Naor, Ilan Newman, Avi Wigderson
    Search Problems in the Decision Tree Model (Preliminary Version) [Citation Graph (0, 0)][DBLP]
    FOCS, 1991, pp:576-585 [Conf]
  14. Ilan Newman
    Testing of Functions that have small width Branching Programs. [Citation Graph (0, 0)][DBLP]
    FOCS, 2000, pp:251-258 [Conf]
  15. Ishai Ben-Aroya, Ilan Newman, Assaf Schuster
    Randomized Single-Target Hot-Potato Routing. [Citation Graph (0, 0)][DBLP]
    ISTCS, 1995, pp:20-29 [Conf]
  16. Ilan Newman, Assaf Schuster
    Hot-Potato Worm Routing is Almost as Easy as Store-and-Forward Packet Routing. [Citation Graph (0, 0)][DBLP]
    ISTCS, 1993, pp:202-211 [Conf]
  17. Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala
    Local versus global properties of metric spaces. [Citation Graph (0, 0)][DBLP]
    SODA, 2006, pp:41-50 [Conf]
  18. Yosi Ben-Asher, Eitan Farchi, Ilan Newman
    Optimal Search in Trees: Extended Abstract + Appendix. [Citation Graph (0, 0)][DBLP]
    SODA, 1997, pp:739-746 [Conf]
  19. Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig
    Quantum property testing. [Citation Graph (0, 0)][DBLP]
    SODA, 2003, pp:480-488 [Conf]
  20. Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair
    Embedding k-outerplanar graphs into l1. [Citation Graph (0, 0)][DBLP]
    SODA, 2003, pp:527-536 [Conf]
  21. Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler
    Sublinear-time approximation of Euclidean minimum spanning tree. [Citation Graph (0, 0)][DBLP]
    SODA, 2003, pp:813-822 [Conf]
  22. Adnan Agbaria, Yosi Ben-Asher, Ilan Newman
    Communication-Processor Tradeoffs in Limited Resources PRAM. [Citation Graph (0, 0)][DBLP]
    SPAA, 1999, pp:74-82 [Conf]
  23. Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin
    Increasing Kolmogorov Complexity. [Citation Graph (0, 0)][DBLP]
    STACS, 2005, pp:412-421 [Conf]
  24. Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf
    Robust Polynomials and Quantum Algorithms. [Citation Graph (0, 0)][DBLP]
    STACS, 2005, pp:593-604 [Conf]
  25. Ilan Newman, Yuri Rabinovich
    Hard Metrics from Cayley Graphs of Abelian Groups. [Citation Graph (0, 0)][DBLP]
    STACS, 2007, pp:157-162 [Conf]
  26. Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky
    Monotonicity testing over general poset domains. [Citation Graph (0, 0)][DBLP]
    STOC, 2002, pp:474-483 [Conf]
  27. Eldar Fischer, Ilan Newman
    Testing of matrix properties. [Citation Graph (0, 0)][DBLP]
    STOC, 2001, pp:286-295 [Conf]
  28. Eldar Fischer, Ilan Newman
    Testing versus estimation of graph properties. [Citation Graph (0, 0)][DBLP]
    STOC, 2005, pp:138-146 [Conf]
  29. Ilan Newman, Mario Szegedy
    Public vs. Private Coin Flips in One Round Communication Games (Extended Abstract). [Citation Graph (0, 0)][DBLP]
    STOC, 1996, pp:561-570 [Conf]
  30. Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira
    A combinatorial characterization of the testable graph properties: it's all about regularity. [Citation Graph (0, 0)][DBLP]
    STOC, 2006, pp:251-260 [Conf]
  31. Adnan Agbaria, Yosi Ben-Asher, Ilan Newman
    Communication - Processor Tradeoffs in a Limited Resources PRAM. [Citation Graph (0, 0)][DBLP]
    Algorithmica, 2002, v:34, n:3, pp:276-297 [Journal]
  32. Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair
    Cuts, Trees and l1-Embeddings of Graphs. [Citation Graph (0, 0)][DBLP]
    Combinatorica, 2004, v:24, n:2, pp:233-269 [Journal]
  33. Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf
    Robust Quantum Algorithms and Polynomials [Citation Graph (0, 0)][DBLP]
    CoRR, 2003, v:0, n:, pp:- [Journal]
  34. Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin
    Increasing Kolmogorov Complexity [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2004, v:, n:081, pp:- [Journal]
  35. Oded Lachish, Ilan Newman
    Testing Periodicity [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2004, v:, n:092, pp:- [Journal]
  36. Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin
    Partitioning multi-dimensional sets in a small number of ``uniform'' parts [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2005, v:, n:095, pp:- [Journal]
  37. Oded Lachish, Ilan Newman
    Languages that are Recognized by Simple Counter Automata are not necessarily Testable [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2005, v:, n:152, pp:- [Journal]
  38. Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur
    Testing Orientation Properties [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2005, v:, n:153, pp:- [Journal]
  39. Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin
    Partitioning multi-dimensional sets in a small number of "uniform" parts. [Citation Graph (0, 0)][DBLP]
    Eur. J. Comb., 2007, v:28, n:1, pp:134-144 [Journal]
  40. Ilan Newman
    Private vs. Common Random Bits in Communication Complexity. [Citation Graph (0, 0)][DBLP]
    Inf. Process. Lett., 1991, v:39, n:2, pp:67-71 [Journal]
  41. Oren Ben-Zwi, Oded Lachish, Ilan Newman
    Lower bounds for testing Euclidean Minimum Spanning Trees. [Citation Graph (0, 0)][DBLP]
    Inf. Process. Lett., 2007, v:102, n:6, pp:219-225 [Journal]
  42. Ishai Ben-Aroya, Ilan Newman, Assaf Schuster
    Randomized Single-Target Hot-Potato Routing. [Citation Graph (0, 0)][DBLP]
    J. Algorithms, 1997, v:23, n:1, pp:101-120 [Journal]
  43. Pascal Berthomé, Torben Hagerup, Ilan Newman, Assaf Schuster
    Self-Simulation for the Passive Optical Star. [Citation Graph (0, 0)][DBLP]
    J. Algorithms, 2000, v:34, n:1, pp:128-147 [Journal]
  44. Yosi Ben-Asher, Ilan Newman
    Decision Trees with Boolean Threshold Queries. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 1995, v:51, n:3, pp:495-502 [Journal]
  45. Yosi Ben-Asher, Ilan Newman
    Geometric Approach for Optimal Routing on a Mesh with Buses. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 1997, v:54, n:3, pp:475-486 [Journal]
  46. Mauricio Karchmer, Ilan Newman, Michael E. Saks, Avi Wigderson
    Non-Deterministic Communication Complexity with Few Witnesses. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 1994, v:49, n:2, pp:247-257 [Journal]
  47. Ilan Newman, Assaf Schuster
    Hot Potato Worm Routing via Store-and-Forward Packet Routing. [Citation Graph (0, 0)][DBLP]
    J. Parallel Distrib. Comput., 1995, v:30, n:1, pp:76-84 [Journal]
  48. Eldar Fischer, Ilan Newman, Jiri Sgall
    Functions that have read-twice constant width branching programs are not necessarily testable. [Citation Graph (0, 0)][DBLP]
    Random Struct. Algorithms, 2004, v:24, n:2, pp:175-193 [Journal]
  49. Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy
    Regular Languages are Testable with a Constant Number of Queries. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 2000, v:30, n:6, pp:1842-1862 [Journal]
  50. Yosi Ben-Asher, Eitan Farchi, Ilan Newman
    Optimal Search in Trees. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 1999, v:28, n:6, pp:2090-2102 [Journal]
  51. 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. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 2005, v:35, n:1, pp:91-109 [Journal]
  52. Ilan Newman
    Testing Membership in Languages that Have Small Width Branching Programs. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 2002, v:31, n:5, pp:1557-1570 [Journal]
  53. Eldar Fischer, Ilan Newman
    Testing versus Estimation of Graph Properties. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 2007, v:37, n:2, pp:482-501 [Journal]
  54. Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair
    Embedding k-Outerplanar Graphs into l 1. [Citation Graph (0, 0)][DBLP]
    SIAM J. Discrete Math., 2006, v:20, n:1, pp:119-136 [Journal]
  55. Ilan Newman, Avi Wigderson
    Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy. [Citation Graph (0, 0)][DBLP]
    SIAM J. Discrete Math., 1995, v:8, n:4, pp:536-542 [Journal]
  56. László Lovász, Moni Naor, Ilan Newman, Avi Wigderson
    Search Problems in the Decision Tree Model. [Citation Graph (0, 0)][DBLP]
    SIAM J. Discrete Math., 1995, v:8, n:1, pp:119-132 [Journal]
  57. Rafi Heiman, Ilan Newman, Avi Wigderson
    On Read-Once Threshold Formulae and Their Randomized Decision in Tree Complexity. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 1993, v:107, n:1, pp:63-76 [Journal]
  58. Ilan Newman, Assaf Schuster
    Hot-Potato Algorithms for Permutation Routing. [Citation Graph (0, 0)][DBLP]
    IEEE Trans. Parallel Distrib. Syst., 1995, v:6, n:11, pp:1168-1176 [Journal]
  59. Sourav Chakraborty, Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman
    Testing st -Connectivity. [Citation Graph (0, 0)][DBLP]
    APPROX-RANDOM, 2007, pp:380-394 [Conf]
  60. Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur
    Testing Properties of Constraint-Graphs. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 2007, pp:264-277 [Conf]
  61. Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, Oren Weimann
    The Stackelberg Minimum Spanning Tree Game. [Citation Graph (0, 0)][DBLP]
    WADS, 2007, pp:64-76 [Conf]
  62. Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, Oren Weimann
    The Stackelberg Minimum Spanning Tree Game [Citation Graph (0, 0)][DBLP]
    CoRR, 2007, v:0, n:, pp:- [Journal]
  63. Irith Ben-Arroyo Hartman, Ilan Newman, Ran Ziv
    On grid intersection graphs. [Citation Graph (0, 0)][DBLP]
    Discrete Mathematics, 1991, v:87, n:1, pp:41-52 [Journal]
  64. Mauricio Karchmer, Nathan Linial, Ilan Newman, Michael E. Saks, Avi Wigderson
    Combinatorial characterization of read-once formulae. [Citation Graph (0, 0)][DBLP]
    Discrete Mathematics, 1993, v:114, n:1-3, pp:275-282 [Journal]
  65. Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf
    Robust Polynomials and Quantum Algorithms. [Citation Graph (0, 0)][DBLP]
    Theory Comput. Syst., 2007, v:40, n:4, pp:379-395 [Journal]
  66. Noga Alon, Eldar Fischer, Ilan Newman
    Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 2007, v:37, n:3, pp:959-976 [Journal]

  67. On the Query Complexity of Testing Orientations for Being Eulerian. [Citation Graph (, )][DBLP]


  68. Hierarchy Theorems for Property Testing. [Citation Graph (, )][DBLP]


  69. Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs. [Citation Graph (, )][DBLP]


  70. LCS Approximation via Embedding into Local Non-repetitive Strings. [Citation Graph (, )][DBLP]


  71. Complementing Missing and Inaccurate Profiling Using a Minimum Cost Circulation Algorithm. [Citation Graph (, )][DBLP]


  72. An exact almost optimal algorithm for target set selection in social networks. [Citation Graph (, )][DBLP]


  73. The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs. [Citation Graph (, )][DBLP]


  74. A New Derandomization of Auctions. [Citation Graph (, )][DBLP]


  75. Space Complexity Vs. Query Complexity. [Citation Graph (, )][DBLP]


  76. Testing of matrix-poset properties. [Citation Graph (, )][DBLP]


  77. The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs [Citation Graph (, )][DBLP]


  78. On Cut Dimension of $\ell_1$ Metrics and Volumes, and Related Sparsification Techniques [Citation Graph (, )][DBLP]


  79. Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs [Citation Graph (, )][DBLP]


  80. Hierarchy Theorems for Property Testing. [Citation Graph (, )][DBLP]


  81. Testing Properties of Constraint-Graphs. [Citation Graph (, )][DBLP]


  82. Space Complexity vs. Query Complexity. [Citation Graph (, )][DBLP]


Search in 0.026secs, Finished in 0.032secs
NOTICE1
System may not be available sometimes or not working properly, since it is still in development with continuous upgrades
NOTICE2
The rankings that are presented on this page should NOT be considered as formal since the citation info is incomplete in DBLP
 
System created by asidirop@csd.auth.gr [http://users.auth.gr/~asidirop/] © 2002
for Data Engineering Laboratory, Department of Informatics, Aristotle University © 2002