Search the dblp DataBase
Ilan Newman :
[Publications ]
[Author Rank by year ]
[Co-authors ]
[Prefers ]
[Cites ]
[Cited by ]
Publications of Author
Oded Lachish , Ilan Newman Testing Periodicity. [Citation Graph (0, 0)][DBLP ] APPROX-RANDOM, 2005, pp:366-377 [Conf ] Oded Lachish , Ilan Newman , Asaf Shapira Space Complexity vs. Query Complexity. [Citation Graph (0, 0)][DBLP ] APPROX-RANDOM, 2006, pp:426-437 [Conf ] 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 ] 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 ] 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 ] 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 ] Ilan Newman Computing in Fault Tolerance Broadcast Networks. [Citation Graph (0, 0)][DBLP ] IEEE Conference on Computational Complexity, 2004, pp:113-122 [Conf ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] Ilan Newman Testing of Functions that have small width Branching Programs. [Citation Graph (0, 0)][DBLP ] FOCS, 2000, pp:251-258 [Conf ] Ishai Ben-Aroya , Ilan Newman , Assaf Schuster Randomized Single-Target Hot-Potato Routing. [Citation Graph (0, 0)][DBLP ] ISTCS, 1995, pp:20-29 [Conf ] 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 ] 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 ] 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 ] Harry Buhrman , Lance Fortnow , Ilan Newman , Hein Röhrig Quantum property testing. [Citation Graph (0, 0)][DBLP ] SODA, 2003, pp:480-488 [Conf ] 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 ] 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 ] 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 ] Harry Buhrman , Lance Fortnow , Ilan Newman , Nikolai K. Vereshchagin Increasing Kolmogorov Complexity. [Citation Graph (0, 0)][DBLP ] STACS, 2005, pp:412-421 [Conf ] 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 ] Ilan Newman , Yuri Rabinovich Hard Metrics from Cayley Graphs of Abelian Groups. [Citation Graph (0, 0)][DBLP ] STACS, 2007, pp:157-162 [Conf ] 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 ] Eldar Fischer , Ilan Newman Testing of matrix properties. [Citation Graph (0, 0)][DBLP ] STOC, 2001, pp:286-295 [Conf ] Eldar Fischer , Ilan Newman Testing versus estimation of graph properties. [Citation Graph (0, 0)][DBLP ] STOC, 2005, pp:138-146 [Conf ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] Oded Lachish , Ilan Newman Testing Periodicity [Citation Graph (0, 0)][DBLP ] Electronic Colloquium on Computational Complexity (ECCC), 2004, v:, n:092, pp:- [Journal ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] On the Query Complexity of Testing Orientations for Being Eulerian. [Citation Graph (, )][DBLP ] Hierarchy Theorems for Property Testing. [Citation Graph (, )][DBLP ] Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs. [Citation Graph (, )][DBLP ] LCS Approximation via Embedding into Local Non-repetitive Strings. [Citation Graph (, )][DBLP ] Complementing Missing and Inaccurate Profiling Using a Minimum Cost Circulation Algorithm. [Citation Graph (, )][DBLP ] An exact almost optimal algorithm for target set selection in social networks. [Citation Graph (, )][DBLP ] The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs. [Citation Graph (, )][DBLP ] A New Derandomization of Auctions. [Citation Graph (, )][DBLP ] Space Complexity Vs. Query Complexity. [Citation Graph (, )][DBLP ] Testing of matrix-poset properties. [Citation Graph (, )][DBLP ] The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs [Citation Graph (, )][DBLP ] On Cut Dimension of $\ell_1$ Metrics and Volumes, and Related Sparsification Techniques [Citation Graph (, )][DBLP ] Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs [Citation Graph (, )][DBLP ] Hierarchy Theorems for Property Testing. [Citation Graph (, )][DBLP ] Testing Properties of Constraint-Graphs. [Citation Graph (, )][DBLP ] Space Complexity vs. Query Complexity. [Citation Graph (, )][DBLP ] Search in 0.026secs, Finished in 0.481secs