1994 …2022

Research activity per year

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

Search results

  • 2021

    Rolling backwards can move you forward: On embedding problems in sparse expanders

    Draganić, N., Krivelevich, M. & Nenadov, R., 2021, ACM-SIAM Symposium on Discrete Algorithms, SODA 2021. Marx, D. (ed.). Association for Computing Machinery, p. 123-134 12 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

  • 2020

    Greedy Maximal Independent Sets via Local Limits

    Krivelevich, M., Mészáros, T., Michaeli, P. & Shikhelman, C., 1 Jun 2020, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, A of A 2020. Drmota, M. & Heuberger, C. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 20. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 159).

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

  • Very fast construction of bounded-degree spanning graphs via the semi-random graph process

    Ben-Eliezer, O., Gishboliner, L., Hefetz, D. & Krivelevich, M., 2020, 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020. Chawla, S. (ed.). Association for Computing Machinery, p. 718-737 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2020-January).

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

  • 2018

    The genus of the Erdos-Rényi random graph and the fragile genus property

    Dowden, C., Kang, M. & Krivelevich, M., 1 Jun 2018, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2018. Ward, M. D. & Fill, J. A. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 17. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 110).

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

  • 2015

    Contagious sets in expanders

    Coja-Oghlan, A., Feige, U., Krivelevich, M. & Reichman, D., 2015, Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015. January ed. Association for Computing Machinery, p. 1953-1987 35 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2015-January, no. January).

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

    Open Access
  • 2014

    Positional games

    Krivelevich, M., 2014, Invited Lectures. Jang, S. Y., Kim, Y. R., Lee, D-W., Yie, I., Kim, Y. R., Lee, D-W. & Yie, I. (eds.). KYUNG MOON SA Co. Ltd., p. 355-379 25 p. (Proceeding of the International Congress of Mathematicans, ICM 2014; vol. 4).

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

  • Smoothed analysis on connected graphs

    Krivelevich, M., Reichman, D. & Samotij, W., 1 Sep 2014, Leibniz International Proceedings in Informatics, LIPIcs. Jansen, K., Rolim, J. D. P., Devanur, N. R. & Moore, C. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 810-825 16 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 28).

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

  • 2012

    Expanders are universal for the class of all spanning trees

    Johannsen, D., Krivelevich, M. & Samotij, W., 2012, Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. p. 1539-1551 13 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

  • 2011

    Hitting time results for Maker-Breaker games

    Ben-Shimon, S., Ferber, A., Hefetz, D. & Krivelevich, M., 2011, Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011. p. 900-912 13 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

  • Packing tight Hamilton cycles in 3-uniform hypergraphs

    Frieze, A., Krivelevich, M. & Loh, P. S., 2011, Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011. Association for Computing Machinery, p. 913-932 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

    Open Access
  • 2010

    Comparing the strength of query types in property testing: The case of testing k-colorability

    Ben-Eliezer, I., Kaufman, T., Krivelevich, M. & Ron, D., 2010, Property Testing - Current Research and Surveys. p. 253-259 7 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

  • 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

  • 2009

    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

  • On smoothed k-CNF formulas and the Walksat algorithm

    Coja-Oghlan, A., Feige, U., Frieze, A., Krivelevich, M. & Vilenchik, D., 2009, Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms. Association for Computing Machinery, p. 451-460 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

  • 2008

    Comparing the strength of query types in property testing: The case of testing k-colorability

    Ben-Eliezer, I., Kaufman, T., Krivelevich, M. & Ron, D., 2008, Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. p. 1213-1222 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

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

  • 2007

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

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

  • Why almost all k-colorable graphs are easy

    Coja-Oghlan, A., Krivelevich, M. & Vilenchik, D., 2007, STACS 2007 - 24th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. Springer Verlag, p. 121-132 12 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

  • 2006

    Semirandom models as benchmarks for coloring algorithms

    Krivelevich, M. & Vilenchik, D., 2006, Proceedings of the 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics. Society for Industrial and Applied Mathematics (SIAM), p. 211-221 11 p. (Proceedings of the 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics; vol. 2006).

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

  • 2003

    Testing low-degree polynomials over GF(2)

    Alon, N., Kaufman, T., Krivelevich, M., Litsyn, S. & Ron, D., 2003, Approximation, Randomization, and Combinatorial Optimization : Algorithms and Techniques: 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2003, Princeton, NJ, USA, August 24-26, 2003. Proceedings. Asora, S., Jansen, K., Rolim, J. D. P. & Sahai, A. (eds.). Berlin Heidelberg: Springer Verlag, p. 188-199 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 2764).

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

  • Tight bounds for testing bipartiteness in general graphs

    Kaufman, T., Krivelevich, M. & Ron, D., 2003, Approximation, Randomization, and Combinatorial Optimization : Algorithms and Techniques: 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2003, Princeton, NJ, USA, August 24-26, 2003. Proceedings. Asora, S., Jansen, K., Rolim, J. D. P. & Sahai, A. (eds.). Berlin Heidelberg: Springer Verlag, p. 341-353 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 2764).

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

  • 2001

    Approximating coloring and maximum independent sets in 3-uniform hypergraphs

    Krivelevich, M., Nathaniel, R. & Sudakov, B., 2001, Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. p. 327-328 2 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

  • Efficient recognition of random unsatisfiable k-SAT instances by spectral methods

    Goerdt, A. & Krivelevich, M., 2001, STACS 2001 - 18th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. Ferreira, A. & Reichel, H. (eds.). Springer Verlag, p. 294-304 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 2010).

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

  • 2000

    Approximating the independence number and the chromatic number in expected polynomial time

    Krivelevich, M. & Vu, V. H., 2000, Automata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings. Montanari, U., Rolim, J. D. P. & Welzl, E. (eds.). Springer Verlag, p. 13-24 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 contributionpeer-review

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

  • 1998

    Approximate coloring of uniform hypergraphs (Extended Abstract)

    Krivelevich, M. & Sudakov, B., 1998, Algorithms, ESA 1998 - 6th Annual European Symposium, Proceedings. Springer Verlag, p. 477-489 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1461 LNCS).

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