| 2008 |
|---|
| 75 | EE | 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 |
| 74 | EE | Roy Levin,
Ilan Newman,
Gadi Haber:
Complementing Missing and Inaccurate Profiling Using a Minimum Cost Circulation Algorithm.
HiPEAC 2008: 291-304 |
| 73 | EE | Oded Lachish,
Ilan Newman,
Asaf Shapira:
Space Complexity Vs. Query Complexity.
Computational Complexity 17(1): 70-93 (2008) |
| 72 | EE | Oded Goldreich,
Michael Krivelevich,
Ilan Newman,
Eyal Rozenberg:
Hierarchy Theorems for Property Testing.
Electronic Colloquium on Computational Complexity (ECCC) 15(097): (2008) |
| 71 | EE | Harry Buhrman,
Lance Fortnow,
Ilan Newman,
Hein Röhrig:
Quantum Property Testing.
SIAM J. Comput. 37(5): 1387-1400 (2008) |
| 2007 |
|---|
| 70 | EE | Sourav Chakraborty,
Eldar Fischer,
Oded Lachish,
Arie Matsliah,
Ilan Newman:
Testing st -Connectivity.
APPROX-RANDOM 2007: 380-394 |
| 69 | EE | Shirley Halevy,
Oded Lachish,
Ilan Newman,
Dekel Tsur:
Testing Properties of Constraint-Graphs.
IEEE Conference on Computational Complexity 2007: 264-277 |
| 68 | EE | Ilan Newman,
Yuri Rabinovich:
Hard Metrics from Cayley Graphs of Abelian Groups.
STACS 2007: 157-162 |
| 67 | EE | 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 |
| 66 | EE | 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) |
| 65 | EE | Shirley Halevy,
Oded Lachish,
Ilan Newman,
Dekel Tsur:
Testing Properties of Constraint-Graphs.
Electronic Colloquium on Computational Complexity (ECCC) 14(054): (2007) |
| 64 | EE | 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 | EE | Oren Ben-Zwi,
Oded Lachish,
Ilan Newman:
Lower bounds for testing Euclidean Minimum Spanning Trees.
Inf. Process. Lett. 102(6): 219-225 (2007) |
| 62 | EE | Eldar Fischer,
Ilan Newman:
Testing versus Estimation of Graph Properties.
SIAM J. Comput. 37(2): 482-501 (2007) |
| 61 | EE | Noga Alon,
Eldar Fischer,
Ilan Newman:
Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs.
SIAM J. Comput. 37(3): 959-976 (2007) |
| 60 | EE | 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 | EE | Oded Lachish,
Ilan Newman,
Asaf Shapira:
Space Complexity vs. Query Complexity.
APPROX-RANDOM 2006: 426-437 |
| 58 | EE | 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 | EE | 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 | EE | Oded Lachish,
Ilan Newman,
Asaf Shapira:
Space Complexity vs. Query Complexity.
Electronic Colloquium on Computational Complexity (ECCC) 13(103): (2006) |
| 55 | EE | 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 | EE | Oded Lachish,
Ilan Newman:
Testing Periodicity.
APPROX-RANDOM 2005: 366-377 |
| 53 | EE | Harry Buhrman,
Lance Fortnow,
Ilan Newman,
Nikolai K. Vereshchagin:
Increasing Kolmogorov Complexity.
STACS 2005: 412-421 |
| 52 | EE | Harry Buhrman,
Ilan Newman,
Hein Röhrig,
Ronald de Wolf:
Robust Polynomials and Quantum Algorithms.
STACS 2005: 593-604 |
| 51 | EE | Eldar Fischer,
Ilan Newman:
Testing versus estimation of graph properties.
STOC 2005: 138-146 |
| 50 | EE | 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 | EE | 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 | EE | Shirley Halevy,
Oded Lachish,
Ilan Newman,
Dekel Tsur:
Testing Orientation Properties
Electronic Colloquium on Computational Complexity (ECCC)(153): (2005) |
| 47 | EE | 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 | EE | Ilan Newman:
Computing in Fault Tolerance Broadcast Networks.
IEEE Conference on Computational Complexity 2004: 113-122 |
| 45 | EE | Anupam Gupta,
Ilan Newman,
Yuri Rabinovich,
Alistair Sinclair:
Cuts, Trees and l1-Embeddings of Graphs.
Combinatorica 24(2): 233-269 (2004) |
| 44 | EE | Harry Buhrman,
Lance Fortnow,
Ilan Newman,
Nikolai K. Vereshchagin:
Increasing Kolmogorov Complexity
Electronic Colloquium on Computational Complexity (ECCC)(081): (2004) |
| 43 | EE | Oded Lachish,
Ilan Newman:
Testing Periodicity
Electronic Colloquium on Computational Complexity (ECCC)(092): (2004) |
| 42 | EE | 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 | EE | Harry Buhrman,
Lance Fortnow,
Ilan Newman,
Hein Röhrig:
Quantum property testing.
SODA 2003: 480-488 |
| 40 | EE | Chandra Chekuri,
Anupam Gupta,
Ilan Newman,
Yuri Rabinovich,
Alistair Sinclair:
Embedding k-outerplanar graphs into l1.
SODA 2003: 527-536 |
| 39 | EE | 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 | EE | Harry Buhrman,
Ilan Newman,
Hein Röhrig,
Ronald de Wolf:
Robust Quantum Algorithms and Polynomials
CoRR quant-ph/0309220: (2003) |
| 2002 |
|---|
| 37 | EE | 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 | EE | Eldar Fischer,
Eric Lehman,
Ilan Newman,
Sofya Raskhodnikova,
Ronitt Rubinfeld,
Alex Samorodnitsky:
Monotonicity testing over general poset domains.
STOC 2002: 474-483 |
| 35 | EE | 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 | EE | Adnan Agbaria,
Yosi Ben-Asher,
Ilan Newman:
Communication - Processor Tradeoffs in a Limited Resources PRAM.
Algorithmica 34(3): 276-297 (2002) |
| 33 | EE | Ilan Newman:
Testing Membership in Languages that Have Small Width Branching Programs.
SIAM J. Comput. 31(5): 1557-1570 (2002) |
| 2001 |
|---|
| 32 | EE | 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 | EE | 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 | EE | Anupam Gupta,
Ilan Newman,
Yuri Rabinovich,
Alistair Sinclair:
Cuts, Trees and l1-Embeddings of Graphs.
FOCS 1999: 399-409 |
| 27 | EE | Noga Alon,
Michael Krivelevich,
Ilan Newman,
Mario Szegedy:
Regular Languages Are Testable with a Constant Number of Queries.
FOCS 1999: 645-655 |
| 26 | EE | 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 | EE | Ilan Newman,
Mario Szegedy:
Public vs. Private Coin Flips in One Round Communication Games (Extended Abstract).
STOC 1996: 561-570 |
| 20 | EE | Yosi Ben-Asher,
Ilan Newman:
Optimal Search in Trees
Electronic Colloquium on Computational Complexity (ECCC) 3(44): (1996) |
| 19 | EE | 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 | EE | 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 | EE | Ilan Newman,
Assaf Schuster:
Hot Potato Worm Routing via Store-and-Forward Packet Routing.
J. Parallel Distrib. Comput. 30(1): 76-84 (1995) |
| 12 | EE | 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 | EE | 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 | EE | 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 | EE | 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 |
