Noga Mordechai Alon

Calculated based on number of publications stored in Pure and citations from Scopus
1981 …2024

Research activity per year

Filter
Conference contribution

Search results

  • 2010

    High degree graphs contain large-star factors

    Alon, N. & Wormald, N., 2010, Fete of Combinatorics and Computer Science. p. 9-21 13 p. (Bolyai Society Mathematical Studies; vol. 20).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    9 Scopus citations
  • On constant time approximation of parameters of bounded degree graphs

    Alon, N., 2010, Property Testing - Current Research and Surveys. p. 234-239 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 contribution

    Open Access
    11 Scopus citations
  • Solving linear systems through nested dissection

    Alon, N. & Yuster, R., 2010, Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010. IEEE Computer Society, p. 225-234 10 p. 5671172. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    10 Scopus citations
  • Solving MAX-r-SAT above a tight lower bound

    Alon, N., Gutin, G., Kim, E. J., Szeider, S. & Yeo, A., 2010, Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms. Association for Computing Machinery (ACM), p. 511-517 7 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    32 Scopus citations
  • Testing Boolean function isomorphism

    Alon, N. & Blais, E., 2010, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings. p. 394-405 12 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 contribution

    Open Access
    18 Scopus citations
  • 2009

    Balanced hashing, color coding and approximate counting

    Alon, N. & Gutner, S., 2009, Parameterized and Exact Computation - 4th International Workshop, IWPEC 2009, Revised Selected Papers. p. 1-16 16 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5917 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    21 Scopus citations
  • Choice-memory tradeoff in allocations

    Alon, N., Lubetzky, E. & Gurel-Gurevich, O., 2009, Proceedings - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009. p. 230-238 9 p. 5438628. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    3 Scopus citations
  • Deterministic approximation algorithms for the nearest codeword problem

    Alon, N., Panigrahy, R. & Yekhanin, S., 2009, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings. p. 339-351 13 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 contribution

    Open Access
    29 Scopus citations
  • Fast FAST

    Alon, N., Lokshtanov, D. & Saurabh, S., 2009, Automata, Languages and Programming - 36th International Colloquium, ICALP 2009, Proceedings. PART 1 ed. p. 49-58 10 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5555 LNCS, no. PART 1).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    81 Scopus citations
  • On the power of two, three and four probes

    Alon, N. & Feige, U., 2009, Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms. Association for Computing Machinery (ACM), p. 346-354 9 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    30 Scopus citations
  • 2008

    Broadcasting with side information

    Alon, N., Hassidim, A., Lubetzky, E., Stav, U. & Weinstein, A., 2008, Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008. p. 823-832 10 p. 4691014. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    135 Scopus citations
  • K-wise independent random graphs

    Alon, N. & Nussboim, A., 2008, Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008. p. 813-822 10 p. 4691013. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    17 Scopus citations
  • Many random walks are faster than one

    Alon, N., Kozma, G., Avin, C., Lotker, Z., Koucky, M. & Tuttle, M. R., 2008, SPAA'08 - Proceedings of the 20th Annual Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery, p. 119-128 10 p. (Annual ACM Symposium on Parallelism in Algorithms and Architectures).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    75 Scopus citations
  • Optimal monotone encodings

    Alon, N. & Hod, R., 2008, Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings. PART 1 ed. p. 258-270 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5125 LNCS, no. PART 1).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Optimal universal graphs with deterministic embedding

    Alon, N. & Capalbo, M., 2008, Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. Association for Computing Machinery, p. 373-378 6 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    27 Scopus citations
  • Polychromatic colorings of plane graphs

    Alon, N., Berke, R., Buchin, K., Buchin, M., Csorba, P., Shannigrahi, S., Speckmann, B. & Zumstein, P., 2008, Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08. Association for Computing Machinery, p. 338-345 8 p. (Proceedings of the Annual Symposium on Computational Geometry).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    10 Scopus citations
  • Small sample spaces cannot fool low degree polynomials

    Alon, N., Ben-Eliezer, I. & Krivelevich, M., 2008, Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques - 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Proceedings. p. 266-275 10 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 contribution

    Open Access
    5 Scopus citations
  • The complexity of the outer face in arrangements of random segments

    Alon, N., Halperin, D., Nechushtan, O. & Sharir, M., 2008, Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08. p. 69-78 10 p. (Proceedings of the Annual Symposium on Computational Geometry).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
  • Weak ∈-nets and interval chains

    Alon, N., Kaplan, H., Nivasch, G., Sharir, M. & Smorodinsky, S., 2008, Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. p. 1194-1203 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    7 Scopus citations
  • 2007

    An elementary construction of constant-degree expanders

    Alon, N., Schwartz, O. & Shapira, A., 2007, Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007. Association for Computing Machinery, p. 454-458 5 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 07-09-January-2007).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    4 Scopus citations
  • Balanced families of perfect hash functions and their applications

    Alon, N. & Gutner, S., 2007, Automata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings. Springer Verlag, p. 435-446 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4596 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    12 Scopus citations
  • Better algorithms and bounds for directed maximum leaf problems

    Alon, N., Fomin, F. V., Gutin, G., Krivelevich, M. & Saurabh, S., 2007, FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science - 27th International Conference, Proceedings. Springer Verlag, p. 316-327 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4855 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    11 Scopus citations
  • Can a graph have distinct regular partitions?

    Alon, N., Shapira, A. & Stav, U., 2007, Computing and Combinatorics - 13th Annual International Conference, COCOON 2007, Proceedings. Springer Verlag, p. 428-438 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4598 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
  • Fast algorithms for maximum subset matching and all-pairs shortest paths in graphs with a (not so) small vertex cover

    Alon, N. & Yustcr, R., 2007, Algorithms - ESA 2007 - 15th Annual European Symposium, Proceedings. Springer Verlag, p. 175-186 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4698 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    12 Scopus citations
  • Finding disjoint paths in expanders deterministically and online

    Alon, N. & Capalbo, M., 2007, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007. p. 518-524 7 p. 4389521. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    13 Scopus citations
  • Improved approximation for directed cut problems

    Agarwal, A., Alon, N. & Charikar, M. S., 2007, STOC'07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing. p. 671-680 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    37 Scopus citations
  • Linear time algorithms for finding a dominating set of fixed size in degenerated graphs

    Alon, N. & Gutner, S., 2007, Computing and Combinatorics - 13th Annual International Conference, COCOON 2007, Proceedings. p. 394-405 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4598 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    12 Scopus citations
  • Parameterized algorithms for directed maximum leaf problems

    Alon, N., Fomin, F. V., Gutin, G., Krivelevich, M. & Saurabh, S., 2007, Automata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings. Springer Verlag, p. 352-362 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4596 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    17 Scopus citations
  • Quasi-randomness and algorithmic regularity for graphs with general degree distributions

    Alon, N., Coja-Oghlan, A., Hàn, H., Kang, M., Rödl, V. & Schacht, M., 2007, Automata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings. Springer Verlag, p. 789-800 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4596 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    3 Scopus citations
  • Testing k-wise and almost k-wise independence

    Alon, N., Andoni, A., Kaufman, T., Matulef, K., Rubinfeld, R. & Xie, N., 2007, STOC'07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing. p. 496-505 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    89 Scopus citations
  • 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 contribution

    87 Scopus citations
  • Additive approximation for edge-deletion problems (abstract)

    Alon, N., Shapira, A. & Sudakov, B., 2006, Automata, Languages and Programming - 33rd International Colloquium, ICALP 2006, Proceedings. Springer Verlag, p. 1-2 2 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4051 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Conflict-free colorings of shallow discs

    Alon, N. & Smorodinsky, S., 2006, Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06. Association for Computing Machinery (ACM), p. 41-43 3 p. (Proceedings of the Annual Symposium on Computational Geometry; vol. 2006).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    26 Scopus citations
  • Tell me who i am: An interactive recommendation system

    Alon, N., Awerbuch, B., Azar, Y. & Patt-Shamir, B., 2006, SPAA 2006: 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures. p. 1-10 10 p. (Annual ACM Symposium on Parallelism in Algorithms and Architectures; vol. 2006).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    18 Scopus citations
  • 2005

    A characterization of the (natural) graph properties testable with one-sided error

    Alon, N. & Shapira, A., 2005, Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005. p. 429-438 10 p. 1530735. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2005).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    51 Scopus citations
  • Additive approximation for edge-deletion problems

    Alon, N., Shapira, A. & Sudakov, B., 2005, Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005. p. 419-428 10 p. 1530734. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2005).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    28 Scopus citations
  • Generalization error bounds for collaborative prediction with low-rank matrices

    Srebro, N., Alon, N. & Jaakkola, T. S., 2005, Advances in Neural Information Processing Systems 17 - Proceedings of the 2004 Conference, NIPS 2004. Neural information processing systems foundation, (Advances in Neural Information Processing Systems).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    47 Scopus citations
  • 2002

    Guessing secrets efficiently via list decoding (extended abstract)

    Alon, N., Guruswami, V., Kaufman, T. & Sudan, M., 2002, Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002. Association for Computing Machinery, p. 254-262 9 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 06-08-January-2002).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    20 Scopus citations
  • Testing satisfiability

    Alon, N. & Shapira, A., 2002, Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002. Association for Computing Machinery, p. 645-654 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 06-08-January-2002).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    17 Scopus citations
  • 2001

    Constructing worst case instances for semidefinite programming based approximation algorithms

    Alon, N., Sudakov, B. & Zwick, U., 2001, Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. p. 92-100 9 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    1 Scopus citations
  • 2000

    Scalable secure storage when half the system is faulty

    Alon, N., Kaplan, H., Krivelevich, M., Malkhi, D. & Stern, J., 2000, Automata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings. Montanari, U., Rolim, J. D. P. & Welzl, E. (eds.). Springer Verlag, p. 576-587 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1853).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    28 Scopus citations
  • 1999

    Independent sets in hypergraphs with applications to routing via fixed paths

    Alon, N., Arad, U. & Azar, Y., 1999, Randomization, Approximation, and Combinatorial Optimization: Algorithms and Techniques - 3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999, Proceedings. Rolim, J. D. P., Sinclair, A., Hochbaum, D. & Jansen, K. (eds.). Springer Verlag, p. 16-27 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1671).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    14 Scopus citations
  • 1998

    Spectral techniques in graph algorithms

    Alon, N., 1998, LATIN 1998: Theoretical Informatics - 3rd Latin American Symposium, Proceedings. Lucchesi, C. L. & Moura, A. V. (eds.). Springer Verlag, p. 206-215 10 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1380).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    47 Scopus citations
  • 1996

    Derandomization via small sample spaces

    Alon, N., 1996, Algorithm Theory - SWAT 1996 - 5th Scandinavian Workshop on Algorithm Theory, Proceedings. Karlsson, R. & Lingas, A. (eds.). Springer Verlag, p. 1-3 3 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1097).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Improved parallel approximation of a class of integer programming problems

    Alon, N. & Srinivasan, A., 1996, Automata, Languages and Programming - 23rd International Colloquium, ICALP 1996, Proceedings. Meyer auf der Heide, F. & Monien, B. (eds.). Springer Verlag, p. 562-573 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1099).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    4 Scopus citations
  • On-line and off-line approximation algorithms for vector covering problems

    Alon, N., Csirik, J., Sevastianov, S. V., Vestjens, A. P. A. & Woeginger, G. J., 1996, Algorithms - ESA 1996 - 4th Annual European Symposium, Proceedings. Diaz, J. & Serna, M. (eds.). Springer Verlag, p. 406-418 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1136).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    6 Scopus citations
  • The space complexity of approximating the frequency moments

    Alon, N., Matias, Y. & Szegedy, M., Jul 1 1996, Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996. Association for Computing Machinery, p. 20-29 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F129452).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    593 Scopus citations
  • 1995

    Efficient dynamic-resharing “verifiable secret sharing” against mobile adversary

    Alon, N., Galil, Z. & Yung, M., 1995, Algorithms - ESA 1995 - 3rd Annual European Symposium, Proceedings. Spirakis, P. (ed.). Springer Verlag, p. 523-537 15 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 contribution

    18 Scopus citations
  • 1994

    A lower bound on the expected length of one-to-one codes

    Alon, N. & Orlitsky, A., 1994, Proceedings - 1994 IEEE International Symposium on Information Theory, ISIT 1994. Institute of Electrical and Electronics Engineers Inc., p. 203 1 p. 394765. (IEEE International Symposium on Information Theory - Proceedings).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    14 Scopus citations
  • A spectral technique for coloring random 3-colorable graphs (Preliminary version)

    Alon, N. & Kahale, N., May 23 1994, Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC 1994. Association for Computing Machinery, p. 346-355 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F129502).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    29 Scopus citations