If you made any changes in Pure these will be visible here soon.
Filter
Conference contribution

Search results

  • 2022

    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 proceedingConference contributionpeer-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, MA., 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 proceedingConference contributionpeer-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 proceedingConference contributionpeer-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 proceedingConference contributionpeer-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 proceedingConference contributionpeer-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 proceedingConference contributionpeer-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 proceedingConference contributionpeer-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. p. 675-684 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • 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 proceedingConference contributionpeer-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 proceedingConference contributionpeer-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 proceedingConference contributionpeer-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 proceedingConference contributionpeer-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 proceedingConference contributionpeer-review

  • 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 proceedingConference contributionpeer-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 proceedingConference contributionpeer-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 proceedingConference contributionpeer-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 proceedingConference contributionpeer-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 proceedingConference contributionpeer-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 proceedingConference contributionpeer-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 proceedingConference contributionpeer-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 proceedingConference contributionpeer-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 proceedingConference contributionpeer-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 proceedingConference contributionpeer-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 proceedingConference contributionpeer-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 proceedingConference contributionpeer-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 proceedingConference contributionpeer-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 proceedingConference contributionpeer-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 proceedingConference contributionpeer-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 proceedingConference contributionpeer-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 proceedingConference contributionpeer-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 proceedingConference contributionpeer-review