Private vs. common random bits in communication complexity I Newman Information processing letters 39 (2), 67-71, 1991 | 405 | 1991 |
A combinatorial characterization of the testable graph properties: it's all about regularity N Alon, E Fischer, I Newman, A Shapira Proceedings of the thirty-eighth annual ACM Symposium on Theory of Computing …, 2006 | 289 | 2006 |
Monotonicity testing over general poset domains E Fischer, E Lehman, I Newman, S Raskhodnikova, R Rubinfeld, ... Proceedings of the thiry-fourth annual ACM symposium on Theory of computing …, 2002 | 273 | 2002 |
Cuts, Trees and ℓ1-Embeddings of Graphs A Gupta, I Newman, Y Rabinovich, A Sinclair Combinatorica 24 (2), 233-269, 2004 | 212 | 2004 |
Regular languages are testable with a constant number of queries N Alon, M Krivelevich, I Newman, M Szegedy SIAM Journal on Computing 30 (6), 1842-1862, 2001 | 196 | 2001 |
On grid intersection graphs IBA Hartman, I Newman, R Ziv Discrete Mathematics 87 (1), 41-52, 1991 | 153 | 1991 |
Treewidth governs the complexity of target set selection O Ben-Zwi, D Hermelin, D Lokshtanov, I Newman Discrete Optimization 8 (1), 87-96, 2011 | 135 | 2011 |
Every property of hyperfinite graphs is testable I Newman, C Sohler Proceedings of the forty-third annual ACM symposium on Theory of computing …, 2011 | 125 | 2011 |
Testing versus estimation of graph properties E Fischer, I Newman Proceedings of the thirty-seventh annual ACM symposium on Theory of …, 2005 | 116 | 2005 |
Public vs. private coin flips in one round communication games I Newman, M Szegedy Proceedings of the twenty-eighth annual ACM symposium on Theory of computing …, 1996 | 116 | 1996 |
Embedding k-outerplanar graphs into l1 C Chekuri, A Gupta, I Newman, Y Rabinovich, A Sinclair SIAM Journal on Discrete Mathematics 20 (1), 119-136, 2006 | 89 | 2006 |
Search problems in the decision tree model L Lovász, M Naor, I Newman, A Wigderson SIAM Journal on Discrete Mathematics 8 (1), 119-132, 1995 | 86 | 1995 |
Quantum property testing H Buhrman, L Fortnow, I Newman, H Röhrig SIAM Journal on Computing 37 (5), 1387-1400, 2008 | 79 | 2008 |
Optimal search in trees Y Ben-Asher, E Farchi, I Newman SIAM Journal on Computing 28 (6), 2090-2102, 1999 | 79 | 1999 |
Combinatorial characterization of read-once formulae M Karchmer, N Linial, I Newman, M Saks, A Wigderson Discrete Mathematics 114 (1-3), 275-282, 1993 | 72 | 1993 |
A lower bound on the distortion of embedding planar metrics into Euclidean space I Newman, Y Rabinovich Proceedings of the eighteenth annual symposium on Computational geometry, 94-96, 2002 | 69 | 2002 |
Efficient testing of bipartite graphs for forbidden induced subgraphs N Alon, E Fischer, I Newman SIAM Journal on Computing 37 (3), 959-976, 2007 | 66* | 2007 |
Hot-potato algorithms for permutation routing I Newman, A Schuster IEEE Transactions on Parallel and Distributed Systems 6 (11), 1168-1176, 1995 | 62 | 1995 |
Robust polynomials and quantum algorithms H Buhrman, I Newman, H Rohrig, R de Wolf Theory of Computing Systems 40, 379-395, 2007 | 61 | 2007 |
The Stackelberg minimum spanning tree game J Cardinal, ED Demaine, S Fiorini, G Joret, S Langerman, I Newman, ... Algorithmica 59, 129-144, 2011 | 60 | 2011 |