Ilan Newman

View Scopus Profile

Ilan Newman

 https://orcid.org/0000-0002-4845-4111
    1990 …2024

    Research activity per year

    Filter
    Conference contribution

    Search results

    • 2024

      Hardness Condensation by Restriction

      Göös, M., Newman, I., Riazanov, A. & Sokolov, D., 10 Jun 2024, STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing. Mohar, B., Shinkar, I. & O�Donnell, R. (eds.). Association for Computing Machinery, p. 2016-2027 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
    • 2022

      Parameterized Convexity Testing

      Lahiri, A., Newman, I. & Varma, N., 2022, SIAM Symposium on Simplicity in Algorithms, SOSA 2022. Society for Industrial and Applied Mathematics Publications, p. 174-181 8 p. (SIAM Symposium on Simplicity in Algorithms, SOSA 2022).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • Strongly Sublinear Algorithms for Testing Pattern Freeness

      Newman, I. & Varma, N., 1 Jul 2022, 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022. Bojanczyk, M., Merelli, E. & Woodruff, D. P. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 98. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 229).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • 2021

      Coresets for Decision Trees of Signals

      Jubran, I., Sanches Shayda, E. E., Newman, I. & Feldman, D., 7 Oct 2021, Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021. Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P. S. & Wortman Vaughan, J. (eds.). Neural information processing systems foundation, p. 30352-30364 13 p. (Advances in Neural Information Processing Systems; vol. 36).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • New sublinear algorithms and lower bounds for LIS estimation

      Newman, I. & Varma, N., 1 Jul 2021, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021. Bansal, N., Merelli, E. & Worrell, J. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 100. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 198).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • 2020

      Online embedding of metrics

      Newman, I. & Rabinovich, Y., 1 Jun 2020, 17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020. Albers, S. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 32. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 162).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • 2017

      Testing for forbidden order patterns in an array

      Newman, I., Rabinovich, Y., Rajendraprasad, D. & Sohler, C., 2017, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. Klein, P. N. (ed.). Association for Computing Machinery, p. 1582-1597 16 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 0).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
    • 2016

      Every property of outerplanar graphs is testable

      Babu, J., Khoury, A. & Newman, I., 1 Sep 2016, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016. Jansen, K., Mathieu, C., Rolim, J. D. P. & Umans, C. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, (Leibniz International Proceedings in Informatics, LIPIcs; vol. 60).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • 2012

      On multiplicative λ-approximations and some geometric applications

      Newman, I. & Rabinovich, Y., 2012, Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. Association for Computing Machinery, p. 51-67 17 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
    • 2011

      Every property of hyperfinite graphs is testable

      Newman, I. & Sohler, C., 2011, STOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 675-684 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
    • 2010

      Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs

      Chepoi, V., Dragan, F. F., Newman, I., Rabinovich, Y. & Vaxès, Y., 2010, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings. p. 95-109 15 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6302 LNCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • Hierarchy theorems for property testing

      Goldreich, O., Krivelevich, M., Newman, I. & Rozenberg, E., 2010, Property Testing - Current Research and Surveys. p. 289-294 6 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6390 LNCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • Property testing of massively parametrized problems - A survey

      Newman, I., 2010, Property Testing - Current Research and Surveys. p. 142-157 16 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6390 LNCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • 2009

      A new derandomization of auctions

      Ben-Zwi, O., Newman, I. & Wolfovitz, G., 2009, Algorithmic Game Theory - Second International Symposium, SAGT 2009, Proceedings. p. 233-237 5 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5814 LNCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • An exact almost optimal algorithm for target set selection in social networks

      Ben-Zwi, O., Hermelin, D., Lokshtanov, D. & Newman, I., 2009, EC'09 - Proceedings of the 2009 ACM Conference on Electronic Commerce. p. 355-362 8 p. (Proceedings of the ACM Conference on Electronic Commerce).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access

    • Hierarchy theorems for property testing

      Goldreich, O., Krivelevich, M., Newman, I. & Rozenberg, E., 2009, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings. p. 504-519 16 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5687 LNCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • LCS approximation via embedding into local non-repetitive strings

      Landau, G. M., Levy, A. & Newman, I., 2009, Combinatorial Pattern Matching - 20th Annual Symposium, CPM 2009, Proceedings. p. 92-105 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5577 LNCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • The stackelberg minimum spanning tree game on planar and bounded-treewidth graphs

      Cardinal, J., Demaine, E. D., Fiorini, S., Joret, G., Newman, I. & Weimann, O., 2009, Internet and Network Economics - 5th International Workshop, WINE 2009, Proceedings. p. 125-136 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5929 LNCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • 2008

      On the query complexity of testing orientations for being Eulerian

      Fischer, E., Lachish, O., Newman, I., Matsliah, A. & Yahalom, O., 2008, Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques - 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Proceedings. p. 402-415 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5171 LNCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • 2007

      Hard metrics from Cayley graphs of abelian groups

      Newman, I. & Rabinovich, Y., 2007, STACS 2007 - 24th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. Springer Verlag, p. 157-162 6 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4393 LNCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • Testing properties of constraint-graphs

      Halevy, S., Lachish, O., Newman, I. & Tsur, D., 2007, Proceedings - Twenty-Second Annual IEEE Conference on Computational Complexity, CCC 2007. p. 264-277 14 p. 4262769. (Proceedings of the Annual IEEE Conference on Computational Complexity).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • Testing st-connectivity

      Chakraborty, S., Fischer, E., Lachish, O., Matsliah, A. & Newman, I., 2007, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 10th International Workshop, APPROX 2007 and 11th International Workshop, RANDOM 2007, Proceedings. Springer Verlag, p. 380-394 15 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4627 LNCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • The Stackelberg minimum spanning tree game

      Cardinal, J., Demaine, E. D., Fiorini, S., Joret, G., Langerman, S., Newman, I. & Weimann, O., 2007, Algorithms and Data Structures - 10th International Workshop, WADS 2007, Proceedings. Springer Verlag, p. 64-76 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4619 LNCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • 2006

      A combinatorial characterization of the testable graph properties: It's all about regularity

      Alon, N., Fischer, E., Newman, I. & Shapira, A., 2006, STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing. p. 251-260 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. 2006).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • Space complexity vs. query complexity

      Lachish, O., Newman, I. & Shapira, A., 2006, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 a. Springer Verlag, p. 426-437 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4110 LNCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • 1998

      Broadcasting on a budget in the multi-service communication model

      Itkis, G., Newman, I. & Schuster, A., 1998, Proceedings - 5th International Conference on High Performance Computing, HiPC 1998. IEEE Computer Society, p. 163-170 8 p. (Proceedings - Symposium on Computer Architecture and High Performance Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • 1996

      Public vs. private coin flips in one round communication games

      Newman, I. & Szegedy, M., 1 Jul 1996, Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996. Association for Computing Machinery, p. 561-570 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F129452).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • 1995

      Randomized single-target hot-potato routing

      Aroya, I. B., Newman, I. & Schuster, A., 1995, Proceedings ISTCS 1995 - 3rd Israel Symposium on the Theory of Computing and Systems. Institute of Electrical and Electronics Engineers Inc., p. 20-29 10 p. 377050. (Proceedings ISTCS 1995 - 3rd Israel Symposium on the Theory of Computing and Systems).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • Self-simulation for the passive optical star model

      Berthomé, P., Duboux, T. H., Hagerup, T., Newman, I. & Schuster, A., 1995, Algorithms - ESA 1995 - 3rd Annual European Symposium, Proceedings. Spirakis, P. (ed.). Springer Verlag, p. 369-380 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 979).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • 1992

      Non-deterministic communication complexity with few witnesses

      Karchmer, M., Saks, M., Newman, I. & Wigderson, A., 1992, Proceedings of the Seventh Annual Structure in Complexity Theory Conference. Publ by ERROR: no PUB record found for PX none CN nonpie IG 75516, p. 275-281 7 p. (Proceedings of the Seventh Annual Structure in Complexity Theory Conference).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • 1991

      Search problems in the decision tree model

      Lovasz, L., Naor, M., Newman, I. & Wigderson, A., Dec 1991, Annual Symposium on Foundations of Computer Science (Proceedings). Publ by IEEE, p. 576-585 10 p. (Annual Symposium on Foundations of Computer Science (Proceedings)).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • 1990

      On read-once threshold formulae and their randomized decision tree complexity

      Heiman, R., Newman, I. & Wigderson, A., 1990, Proc Fifth Annu Struct Complexity Theor. Publ by IEEE, p. 78-87 10 p. (Proc Fifth Annu Struct Complexity Theor).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • Perfect hashing, graph entropy, and circuit complexity

      Newman, I., Ragde, P. & Wigderson, A., 1990, Proc Fifth Annu Struct Complexity Theor. Publ by IEEE, p. 91-99 9 p. (Proc Fifth Annu Struct Complexity Theor).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review