20022024

Research activity per year

Filter
Conference contribution

Search results

  • 2023

    Testing Versus Estimation of Graph Properties, Revisited

    Gishboliner, L., Kushnir, N. & Shapira, A., Sep 2023, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023. Megow, N. & Smith, A. (eds.). 46. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 275).

    Tel Aviv University

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

  • 2022

    Counting Homomorphic Cycles in Degenerate Graphs

    Gishboliner, L., Levanzov, Y., Shapira, A. & Yuster, R., 2022, ACM-SIAM Symposium on Discrete Algorithms, SODA 2022. p. 417-430 14 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2022-January).

    Tel Aviv University, University of Haifa

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

  • 2020

    Testing linear inequalities of subgraph statistics

    Gishboliner, L., Shapira, A. & Stagni, H., Jan 2020, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020. Vidick, T. (ed.). 43. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 151).

    Tel Aviv University

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

  • 2019

    Testing graphs against an unknown distribution

    Gishboliner, L. & Shapira, A., 23 Jun 2019, STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Charikar, M. & Cohen, E. (eds.). p. 535-546 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Tel Aviv University

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

    Open Access
  • 2018

    A generalized turán problem and its applications

    Gishboliner, L. & Shapira, A., 20 Jun 2018, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Henzinger, M., Kempe, D. & Diakonikolas, I. (eds.). p. 376-389 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Tel Aviv University

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

  • Efficient testing without efficient regularity

    Gishboliner, L. & Shapira, A., 1 Jan 2018, 9th Innovations in Theoretical Computer Science, ITCS 2018. Karlin, A. R. (ed.). 54. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 94).

    Tel Aviv University

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

  • 2017

    Removal lemmas with polynomial bounds

    Gishboliner, L. & Shapira, A., 19 Jun 2017, STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. McKenzie, P., King, V. & Hatami, H. (eds.). p. 510-522 13 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F128415).

    Tel Aviv University

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

    Open Access
  • 2015

    Decomposing a graph into expanding subgraphs

    Moshkovitz, G. & Shapira, A., 2015, Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015. January ed. p. 1283-1295 13 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2015-January, no. January).

    Tel Aviv University

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

    Open Access
  • 2012

    Testing odd-cycle-freeness in Boolean functions

    Bhattacharyya, A., Grigorescu, E., Raghavendra, P. & Shapira, A., 2012, Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. p. 1140-1149 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

    Open Access
  • 2011

    Randomized greedy: New variants of some classic approximation algorithms

    Costello, K. P., Shapira, A. & Tetali, P., 2011, Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011. p. 647-655 9 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

  • 2007

    An elementary construction of constant-degree expanders

    Alon, N., Schwartz, O. & Shapira, A., 1 Jan 2007, Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007. 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 contributionpeer-review

  • Can a graph have distinct regular partitions?

    Alon, N., Shapira, A. & Stav, U., 1 Jan 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 contributionpeer-review

    Open Access
  • 2006

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

    Alon, N., Fischer, E., Newman, I. & Shapira, A., 5 Sep 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

  • Additive approximation for edge-deletion problems (abstract)

    Alon, N., Shapira, A. & Sudakov, B., 1 Jan 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 contributionpeer-review

  • 2005

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

    Alon, N. & Shapira, A., 1 Dec 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 contributionpeer-review

    Open Access
  • Additive approximation for edge-deletion problems

    Alon, N., Shapira, A. & Sudakov, B., 1 Dec 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 contributionpeer-review

  • 2002

    Testing satisfiability

    Alon, N. & Shapira, A., 1 Jan 2002, Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002. 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 contributionpeer-review