אילן נוימן - הפקולטה למדעי המחשב והמידע

פרסומים▼

Testing forbidden order-pattern properties on hypergrids, Chandramouleeswaran, H., Newman, I., Pelleg, T. & Varma, N., 2026, Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026. Larsen, K. G. & Saha, B. (eds.). Association for Computing Machinery, p. 3072-3100 29 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2026-January).
Online embedding of metrics, Newman, I. & Rabinovich, Y., Jun 2025, In: Israel Journal of Mathematics. 267, 2, p. 967-993 27 p.
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).
Strongly Sublinear Algorithms for Testing Pattern Freeness, Newman, I. & Varma, N., 2024, In: TheoretiCS. 3, 1.
Large simple d-cycles in simplicial complexes, Meshulam, R., Newman, I. & Rabinovich, Y., Sep 2023, In: Israel Journal of Mathematics. 256, 2, p. 581-597 17 p.
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).
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).
Hamiltonian and pseudo-Hamiltonian cycles and fillings in simplicial complexes, Mathew, R., Newman, I., Rabinovich, Y. & Rajendraprasad, D., Sep 2021, In: Journal of Combinatorial Theory. Series B. 150, p. 119-143 25 p.
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).
Testing of graph properties, Newman, I., 3 Jun 2021, Encyclopedia of Mathematics and its Applications: Topics in Algorithmic Graph Theory. Cambridge University Press, p. 68-104 37 p.
Testing of graph properties, Newman, I., 2021, Topics in Algorithmic Graph Theory. Beineke, L. W., Golumbic, M. C. & Wilson, R. J. E. (eds.). Cambridge University Press, p. 68–104 (Encyclopedia of Mathematics and its Applications).
Coresets for Decision Trees of Signals, Jubran, I., Sanches Shayda, E. E., Newman, I. & Feldman, D., 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).
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).
Large Simple d-Cycles in Simplicial Complexes, Meshulam, R., Newman, I. & Rabinovich, Y., 10 Oct 2019.
Testing for forbidden order patterns in an array, Newman, I., Rabinovich, Y., Rajendraprasad, D. & Sohler, C., Sep 2019, In: Random Structures and Algorithms. 55, 2, p. 402-426 25 p.
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).
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).
Ascending auctions and Walrasian equilibrium, Ben-Zwi, O., Lavi, R. & Newman, I., 7 Jan 2013.
On multiplicative λ-approximations and some geometric applications, Newman, I. & Rabinovich, Y., 2013, In: SIAM Journal on Computing. 42, 3, p. 855-883 29 p.
Hierarchy Theorems for Property Testing, Goldreich, O., Krivelevich, M., Newman, I. & Rozenberg, E., Mar 2012, In: Computational Complexity. 21, 1, p. 129-192 64 p.
Local versus global properties of metric spaces, Arora, S., Lovász, L., Newman, I., Rabani, Y., Rabinovich, Y. & Vempala, S., 2012, In: SIAM Journal on Computing. 41, 1, p. 250-271 22 p.
Optimal Bi-Valued Auctions, Ben-Zwi, O. & Newman, I., 23 Jun 2011.
Treewidth governs the complexity of target set selection, Ben-Zwi, O., Hermelin, D., Lokshtanov, D. & Newman, I., Feb 2011, In: Discrete Optimization. 8, 1, p. 87-96 10 p.
The Stackelberg minimum spanning tree game, Cardinal, J., Demaine, E. D., Fiorini, S., Joret, G., Langerman, S., Newman, I. & Weimann, O., Feb 2011, In: Algorithmica. 59, 2, p. 129-144 16 p.
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).
Hard Metrics from Cayley Graphs of Abelian Groups, Newman, I. & Rabinovich, Y., 3 Jul 2009, In: Theory of Computing. 5, p. 125-134 10 p., 6.
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).
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).
A combinatorial characterization of the testable graph properties: It's all about regularity, Alon, N., Fischer, E., Newman, I. & Shapira, A., 2009, In: SIAM Journal on Computing. 39, 1, p. 143-167 25 p.
Complementing missing and inaccurate profiling using a minimum cost circulation algorithm, Levin, R., Newman, I. & Haber, G., 2008, In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 4917 LNCS, p. 291-304 14 p.
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).
Partitioning multi-dimensional sets in a small number of "uniform" parts, Alon, N., Newman, I., Shen, A., Tardos, G. & Vereshchagin, N., Jan 2007, In: European Journal of Combinatorics. 28, 1, p. 134-144 11 p.
Local versus Global Properties of Metric Spaces Extended abstract, Arora, S., Lovászt, L., Newman, I., Rabani, Y., Rabinovich, Y. & Vempala, S., 2006, p. 41-50. 10 p.
Increasing kolmogorov complexity, Buhrman, H., Fortnow, L., Newman, I. & Vereshchagin, N., 2005, In: Lecture Notes in Computer Science. 3404, p. 412-421 10 p.
Embedding k-outerplanar graphs into ℓ1, Chekuri, C., Gupta, A., Newman, I., Rabinovich, Y. & Sinclair, A., 2003, p. 527-536. 10 p.
Quantum property testing, Buhrman, H., Fortnow, L., Newman, I. & Röhrig, H., 2003, p. 480-488. 9 p.
Testing membership in languages that have small width branching programs, Newman, I., May 2002, In: SIAM Journal on Computing. 31, 5, p. 1557-1570 14 p.
Functions that have read-twice constant width branching programs are not necessarily testable, Fischer, E. & Newman, I., 2002, In: Proceedings of the Annual IEEE Conference on Computational Complexity. p. 73-79 7 p.
Communication-processor tradeoffs in a limited resources PRAM, Agbaria, A., Ben-Asher, Y. & Newman, I., 2002, In: Algorithmica. 34, 3, p. 276-297 22 p.
Testing of matrix properties, Fischer, E. & Newman, I., 2001, Proceedings of the 33rd annual ACM symposium on theory of computing. Association for Computing Machinery (ACM), p. 286-295 10 p. (Conference Proceedings of the Annual ACM Symposium on Theory of Computing).
Self-Simulation for the Passive Optical Star, Berthomé, P., Hagerup, T., Newman, I. & Schuster, A., Jan 2000, In: Journal of Algorithms. 34, 1, p. 128-147 20 p.
Geometric Approach for Optimal Routing on a Mesh with Buses, Ben-Asher, Y. & Newman, I., Jun 1997, In: Journal of Computer and System Sciences. 54, 3, p. 475-486 12 p.
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).
Hot-Potato Algorithms for Permutation Routing, Newman, I. & Schuster, A., Nov 1995, In: IEEE Transactions on Parallel and Distributed Systems. 6, 11, p. 1168-1176 9 p.
Geometric approach for optimal routing on mesh with buses, Ben-Asher, Y. & Newman, I., 1995, In: IEEE Symposium on Parallel and Distributed Processing - Proceedings. p. 145-152 8 p.
On read-once threshold formulae and their randomized decision tree complexity, Heiman, R., Newman, I. & Wigderson, A., 4 Jan 1993, In: Theoretical Computer Science. 107, 1, p. 63-76 14 p.
Private vs. common random bits in communication complexity, Newman, I., 31 Jul 1991, In: Information Processing Letters. 39, 2, p. 67-71 5 p.
On grid intersection graphs, Hartman, I. B. A., Newman, I. & Ziv, R., 19 Jan 1991, In: Discrete Mathematics. 87, 1, p. 41-52 12 p.
Approximation algorithms for covering a graph by vertex‐disjoint paths of maximum total weight, Moran, S., Newman, I. & Wolfstahl, Y., Jan 1990, In: Networks. 20, 1, p. 55-64 10 p.
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).

תחומי מחקר▼

אלגוריתמים
סיבוכיות

הפקולטה למדעי המחשב והמידע

אוניברסיטת חיפה

פרופ' אילן נוימן

פרסומים▼

תחומי מחקר▼