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

Search results

  • 2022

    Circuits resilient to short-circuit errors.

    Efremenko, K., Haeupler, B., Kalai, Y. T., Kamath, P., Kol, G., Resch, N. & Saxena, R. R., 2022, STOC. Leonardi, S. & Gupta, A. (eds.). Association for Computing Machinery, p. 582-594 13 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

  • Statistically Near-Optimal Hypothesis Selection

    Bousquet, O., Braverman, M., Kol, G., Efremenko, K. & Moran, S., 1 Jan 2022, Proceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021. IEEE Computer Society, p. 909-919 11 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2022-February).

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

  • 2021

    Computation over the Noisy Broadcast Channel with Malicious Parties.

    Efremenko, K., Kol, G., Paramonov, D. & Saxena, R. R., 2021, In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021).. p. 82:1-82:19 19 p.

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

    2 Scopus citations
  • Optimal Error Resilience of Adaptive Message Exchange

    Efremenko, K., Kol, G. & Saxena, R. R., 15 Jun 2021, STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Khuller, S. & Williams, V. V. (eds.). Association for Computing Machinery, p. 1235-1247 13 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

    1 Scopus citations
  • Tight Bounds for General Computation in Noisy Broadcast Networks

    Efremenko, K., Kol, G., Paramonov, D. & Saxena, R. R., 2021, Proceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021. IEEE Computer Society, p. 634-645 12 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2022-February).

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

  • 2020

    Binary Interactive Error Resilience Beyond 1/8 (or why (½)3>1/8)

    Efremenko, K., Kol, G. & Saxena, R. R., 19 Nov 2020, Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020. IEEE Computer Society, p. 470-481 12 p. 9317957. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2020-November).

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

    2 Scopus citations
  • Fast and Bayes-Consistent Nearest neighbors

    Efremenko, K., Kontorovich, A. & Noivirt, M., 2020, The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy]. Chiappa, S. & Calandra, R. (eds.). PMLR, Vol. 108. p. 1276-1286 11 p. (Proceedings of Machine Learning Research).

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

  • Interactive coding with constant round and communication blowup

    Efremenko, K., Haramaty, E. & Kalai, Y. T., 1 Jan 2020, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020. Vidick, T. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 7. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 151).

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

    1 Scopus citations
  • Interactive error resilience beyond 2/7

    Efremenko, K., Kol, G. & Saxena, R. R., 8 Jun 2020, STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G. & Chuzhoy, J. (eds.). Association for Computing Machinery, p. 565-578 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

    3 Scopus citations
  • Noisy Beeps

    Efremenko, K., Kol, G. & Saxena, R. R., 31 Jul 2020, PODC 2020 - Proceedings of the 39th Symposium on Principles of Distributed Computing. Association for Computing Machinery, p. 418-427 10 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

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

    5 Scopus citations
  • 2019

    Optimal short-circuit resilient formulas

    Braverman, M., Efremenko, K., Gelles, R. & Yitayew, M. A., 1 Jul 2019, 34th Computational Complexity Conference, CCC 2019. Shpilka, A. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, (Leibniz International Proceedings in Informatics, LIPIcs; vol. 137).

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

    1 Scopus citations
  • Radio network coding requires logarithmic overhead

    Efremenko, K., Kol, G. & Saxena, R., 1 Nov 2019, Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019. IEEE Computer Society, p. 348-369 22 p. 8948679. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2019-November).

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

    3 Scopus citations
  • 2018

    Barriers for rank methods in arithmetic complexity

    Efremenko, K., Garg, A., Oliveira, R. & Wigderson, A., 1 Jan 2018, 9th Innovations in Theoretical Computer Science, ITCS 2018. Karlin, A. R. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 1. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 94).

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

    16 Scopus citations
  • Interactive coding over the noisy broadcast channel

    Efremenko, K., Kol, G. & Saxena, R., 20 Jun 2018, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Henzinger, M., Kempe, D. & Diakonikolas, I. (eds.). Association for Computing Machinery, p. 890-901 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

    5 Scopus citations
  • 2017

    ϵ-MSR codes with small sub-packetization

    Rawat, A. S., Tamo, I., Guruswami, V. & Efremenko, K., 9 Aug 2017, 2017 IEEE International Symposium on Information Theory, ISIT 2017. Institute of Electrical and Electronics Engineers Inc., p. 2043-2047 5 p. 8006888. (IEEE International Symposium on Information Theory - Proceedings).

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

    7 Scopus citations
  • 2016

    Constant-Rate Coding for Multiparty Interactive Communication is Impossible

    Braverman, M., Efremenko, K., Gelles, R. & Haeupler, B., 19 Jun 2016, STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. Mansour, Y. & Wichs, D. (eds.). New York: Association for Computing Machinery, p. 999–1010 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

    Open Access
    14 Scopus citations
  • Reliable Communication over Highly Connected Noisy Networks

    Alon, N., Braverman, M., Efremenko, K., Gelles, R. & Haeupler, B., 25 Jul 2016, PODC 2016 - Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing. New York: Association for Computing Machinery, p. 165–173 9 p.

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

    21 Scopus citations
  • 2015

    Maximal Noise in Interactive Communication over Erasure Channels and Channels with Feedback

    Efremenko, K., Gelles, R. & Haeupler, B., 2015, Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science. New York: Association for Computing Machinery, p. 11–20 10 p.

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

    13 Scopus citations
  • 2014

    List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise

    Braverman, M. & Efremenko, K., 1 Oct 2014, 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. IEEE, p. 236-245 10 p. 6979008. (Annual Symposium on Foundations of Computer Science).

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

    35 Scopus citations
  • 2012

    From irreducible representations to locally decodable codes

    Efremenko, K., 26 Jun 2012, STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing. p. 327-337 11 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

    4 Scopus citations
  • 2010

    Local list-decoding with a constant number of queries

    Ben-Aroya, A., Efremenko, K. & Ta-Shma, A., 1 Jan 2010, Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010. IEEE Computer Society, p. 715-722 8 p. 5671342. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

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

    20 Scopus citations
  • 2009

    3-query locally decodable codes of subexponential length

    Efremenko, K., 9 Nov 2009, STOC'09 - Proceedings of the 2009 ACM International Symposium on Theory of Computing. p. 39-44 6 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

    99 Scopus citations
  • From coding theory to efficient pattern matching

    Clifford, R., Efremenko, K., Porat, E. & Rothschild, A., 1 Jan 2009, Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms. Association for Computing Machinery (ACM), p. 778-784 7 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

    28 Scopus citations
  • How well do random walks parallelize?

    Efremenko, K. & Reingold, O., 6 Nov 2009, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings. p. 476-489 14 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

    33 Scopus citations
  • Mismatch Sampling

    Clifford, R., Efremenko, K., Porat, B., Porat, E. & Rothschild, A., 2009, String Processing and Information Retrieval. Amir, A., Turpin, A. & Moffat, A. (eds.). Berlin, Heidelberg: Springer, p. 99-108 10 p. (Lecture Notes in Computer Science; vol. 5280).

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

  • 2008

    A Black Box for Online Approximate Pattern Matching

    Clifford, R., Efremenko, K., Porat, B. & Porat, E., 2008, Combinatorial Pattern Matching - 19th Annual Symposium, CPM 2008, Proceedings. Ferragina, P. & Landau, G. M. (eds.). Berlin, Heidelberg: Springer Berlin Heidelberg, p. 143-151 9 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5029 LNCS).

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

    11 Scopus citations
  • Approximating general metric distances between a pattern and a text

    Porat, E. & Efremenko, K., 1 Jan 2008, Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. Association for Computing Machinery, p. 419-427 9 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

    9 Scopus citations
  • 2007

    K-mismatch with don't cares

    Clifford, R., Efremenko, K., Porat, E. & Rothschild, A., 1 Jan 2007, Algorithms - ESA 2007 - 15th Annual European Symposium, Proceedings. Springer Verlag, p. 151-162 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 contributionpeer-review

    27 Scopus citations