Here are some of my papers

  • Parameterized Convexity Testing, Abhiruk Lahiri, Ilan Newman and Nithin Varma, To appear in SOSA22. Also, arXiv

  • Coresets for Decision Trees of Signals, Ibrahim Jubran, Ernesto Sanches, Ilan Newman, Dan Feldman, spotlight presentation at NeurIPS 2021, arXiv

  • New Sublinear Algorithms and Lower Bounds for LIS Estimation, Ilan Newman and Nithin Varma, LIPIcs, Volume 198, ICALP 2021.

  • Strongly Sublinear Algorithms for Testing Pattern Freeness, Ilan Newman and Nithin Varma, arXiv, appeared in ICALP22, and published in TheoretiCS

  • Online embedding of metrics, Ilan Newman and Yuri Rabinovich, SWAT2020.

  • Large Simple d-Cycles in Simplicial Complexes, Roy Meshulam, Ilan Newman and Yuri Rabinovich, in Israel J. of Math. arxive version.

  • On the Characterization of 1-sided error Strongly-Testable Graph Properties for bounded-degree graphs, Hiro Ito, Areej Khoury and Ilan Newman, to appear in J. CC, arXiv version (including appendix.)

  • Hamiltonian and Pseudo-Hamiltonian Cycles, and Fillings in Simplicial Complexes , Rogers Mathews, Ilan Newman, Yuri Rabinovich and Deepak R, in JCTB, arXiv version and a C++ progamm to verify the small cases program

  • Contractors minimum spanning tree, Irith Ben-Arroyo Hartman, Ilan Newman, Australian J. of Combinatorics, Volume 74(1) (2019)

  • Testing Permutation for forbidden order patterns, Ilan Newman, Yuri Rabinovich, Deepak R, Christian Sohler, Random Structures and Alg. (RSA)

  • Every Property of Outerplanar Graphs is Testable, Jasine Babu, Areej Khoury, Ilan Newman APPROX-RANDOM 2016: 21:1-21:19

  • On Connectivity of the Facet Graphs of Simplicial Complexes, Ilan Newman and Yuri Rabinovich, in I srael J. of Math

  • Extremal problems on shadows and hypercuts in simplicial complexes, Nati Linial, Ilan Newman, Yuval Peled, Yuri Rabinovich. in Israel J. of Math

  • Optimal Bi-Valued Auctions, Oren Ben-Zwi and Ilan Newman, arXiv

  • Ascending auctions and Walrasian equilibrium, Oren Ben-Zwi, Ron Lavi and Ilan Newman, arXiv

  • Every Property of Hyperfinite Graphs is Testable, Ilan Newman and Christian Sohler, STOC2011. . Final version (with simpleer proof) to appear in SICOMP.

  • On Multiplicative $\lambda$-Approximations and Some Geometric Applications , Ilan Newman, Yuri Rabinovich, SODA 2012,   Final version (SICOMP)

  • Approximation algorithms for embedding graph metrics, V. Chepoi, F. F. Dragan, I. Newman, Y. Rabinovich and Y. Vax\`es, Random-Approx 2010, Barcelona , full version DCG .

  • A new derandomization of Auctions, Oren Ben-Zwi, Ilan Newman and Guy Wolfowitz, SAGT 2009, Cyprus. , final version to appear in RS\& A .

  • The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs, Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwena$\ddot{e}$l Joret, Ilan Newman and Oren Weimann, WINE 2009, Rome, Italy.

  • An Exact Almost Optimal Algorithm for Target Set Selection in Social Networks, Oren Ben-Zwi, Danny Hermelin, Daniel Lokshtanov and Ilan Newman, EC09

  • LCS Approximation via Embedding into Local Non-Repetitive Strings, Avivit Levy, Gad Landau, Ilan Newman, Combinatorial Pattern Matching (CPM) 2009

  • Hierarchy Theorems for Property Testingm, Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg, Random09

  • On the Query Complexity of Testing Orientations for being Eulerian, Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman, Orly Yahalom, Random 2008.

  • Testing $st$-Connectivity, Sourav Chakraborty, Eldar Fischer, Oded Lachish, Arie Matsliah, and Ilan Newman, CCC 2007.

  • Testing Properties of Constraint-Graphs, Shirley Halevy, Oded Lachish, Ilan Newman, and Dekel Tsur, CCC 2007.

  • The Stackelberg Minimum Spanning Tree Game, Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwena\"el Joret, Stefan Langerman, Ilan Newman and Oren Weimann, to appear in WADS2007.

  • Efficient testing of bipartite graphs for forbidden induced subgraphs, Noga Alon, Eldar Fischer and Ilan Newman, SICOMP, 37(3)(2007-8), 959-976 . These results first appeared as part of STOC'01. A ppt(pdf) talk on conditional regularity for bipartite graphs ppt talk, pdf talk

  • Testing of matrix-poset properties, Eldar Fischer and Ilan Newman, to appear in Combinatorica. These results first appeared as part of STOC'01.

  • Hard Metrics From Cayley Graphs Of Abelian Groups, Ilan Newman and Yuri Rabinovich in stacs07 ToC Vol 5 article 6 , talk: power point , pdf

  • Lower Bounds for Testing Euclidean Minimum Spanning Trees, Oren Ben-Zwi, Oded Lachish and Ilan Newman to appear in IPL

  • Space Complexity vs. Query Complexity, Oded Lachish, Ilan Newman and Asaf Shapira Random06. A final version to appear in J. Computational Complexity, special issue for Random 2006. pdf

  • Local versus Global Properties of Metric Spaces, Sanjeev Arora, Laszlo Lovasz, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala SODA06, final version SICOMP

  • A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity, Noga Alon, Eladr Fischer, Ilan Newman, Asaf Shapira STOC06, to appear in SICOMP special issue for STOC06

  • Partitioning multi-dimensional sets in a small number of ``uniform'' parts, Noga Alon, Ilan Newman, Alexander Shen, Gabor Tardos, Nikolai Vershchagin E. J. Combinatorics 2006

  • Testing Periodicity, Oded Lachish, Ilan Newman, Random05, final version in Algoritmica, pdf

  • Testing versus Estimation of Graph Properties, Eldar Fischer, Ilan Newman, STOC05. Full paper to appear in sicomp

  • Increasing Kolmogorov Complexity, Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai Vereshchagin, stacs05.

  • Robust Polynomials and Quantum Algorithms, Harry Buhrman, Ilan Newman Hein R\"ohrig, Ronald de Wolf, in Theory of Computing Systems, special issue for stacs05. . Journal source at Springer

  • Computing in fault tolerance broadcast networks, Ilan Newman, Complexity04. Random Structures and Algorithms (RS&A), vol 34(4): 478-501 (2008) - full version.

  • Sublinear-Time Approximation of Euclidean Minimum Spanning Tree, Artur Czumaj, Funda Ergun, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld and Christian Sohler, SODA03. to appear in SICOMP - full version.

  • Embedding k-Outerplanar Graphs into L1, Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich and Alistair Sinclair, SODA03.

  • A lower bound on the distortion of embedding planar metrics into Euclidean space, Ilan Newman and Yuri Rabinovich, in J. Discrete \& Computational Geometry, and SoCG02.

  • Functions that have read-twice, constant width, branching programs are not necessarily testable, Eldar Fischer, Ilan Newman, Jiri Sgall journal version (RS\& A). First in (conf. version) Complexity02

  • Monotonicity testing over general poset domains, Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky, STOC02.

  • Quantum Property testing, Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Rohrig, journal version (SICOMP) , SODA03 version Also appeared in EQIS'01: Erato Quantum Information Science, September 6-8, 2001, Tokyo Japan.

  • Testing of functions that have small width branching programs, FOCS00. , journal version (SICOMP) remark: As noted by Beate Bollig, the result here carries on to non-oblivious read-once BP's as well.

  • Cuts, Trees and L1-Embeddings of Graphs, Anupam Gupta, Ilan Newman, Yuri Rabinovich and Alistair Sinclair, FOCS99. , journal version (Combinatorica)

  • Regular Languages are Testable with a Constant Number of Queries, Noga Alon, Michael Krivelevich, Ilan Newman and Mario Szegedy, FOCS99 , journal version (SICOMP)

  • Communication-Processor Tradeoffs in Limited Resources PRAM, Adnan Agbaria, Yosi Ben-Asher and Ilan Newman, in SPAA99, journal version (Algorithmica).

  • Broadcasting on a Budget in Multi-Service Communication Model, Gene Itkis, Ilan Newman, Assaf Schuster, in 1998 International Conference on High Performance Computing, India Dec 17 - Dec 20.

  • Optimal Search in Trees, Yosi Ben-asher, Eitan Farchi, Ilan Newman, in SODA 97, full version in SIAM J. on Comp 98.

  • Public vs. Private coin flips in one round communication games, Ilan Newman and Mario Szegedy, in STOC96.

  • Self-Simulation for the Passive Optical Star Model, by Pascal Berthome, T. Duboux, Torben Hagerup, Ilan Newman, Assaf Schuster, ESA95. J. of Algorithms version

  • Randomized Single-Target Hot-Potato Routing, by Ishay Ben Aroya, Ilan Newman and Assaf Schuster, in ISTCS 1995, pp. 20-29, full version in J. of Algorithms.

  • Decision Trees with Boolean Threshold Queries, Yosi Ben-asher and Ilan Newman, JCSS and Structures 1995.

  • Geometric Approach for Optimal Routing on Mesh of Buses, Yosi Ben-asher, Ilan Newman, in SPDP 95 final version in JCSS.

  • Private vs. Common Random bits in communication complexity, Ilan Newman, in Information Processing Letters 39(1991) 67-71.

  • Non-deterministic Communication Complexity with Few Witnesses, by Mauricio Karchmer, Ilan Newman, Mike Saks and Avi Wigderson, in JCSS Vol. 49, No. 2, 1994,

  • Lower Bounds on Formula Size of Boolean Functions using Hypergraph-Entropy, Ilan Newman and Avi Wigderson, in SIAM J. of Discrete Math. Vol. 8 no. 4, 1995.

  • Combinatorial Characterization of Read Once Formulae, Mauricio Karchmer, Nati Linial, Ilan Newman, Mike Saks and Avi Wigderson, full version in J. Discrete Math. 114 (1993) pp. 275--282.

  • On Read Once Threshold Formulae and their Randomized Decision Tree Complexity, Rafi Heiman, Ilan Newman, and Avi Wigderson, Structure 90, full version in TCS 107 No. 1, 1993, pp. 63-76.

  • Search problem in the Decision Tree model, Laszlo Lovasz, Moni Naor, Ilan Newman and Avi Wigderson, FOCS 91, full version in SIAM journal on discrete math, Vol 8, No. 1, pp. 119-132.



    back to Ilan Newman homepage