No photo of Omri Weinstein

View Scopus Profile

Omri Weinstein

 https://orcid.org/0000-0002-9357-2299
    Calculated based on number of publications stored in Pure and citations from Scopus
    20112024

    Research activity per year

    • 35 Conference contribution
    • 10 Article
    • 1 Conference article
    Filter
    Conference contribution

    Search results

    • 2024

      Hardness Amplification for Dynamic Binary Search Trees

      Jiang, S., Lecomte, V., Weinstein, O. & Yingchareonthawornchai, S., 4 Dec 2024, 35th International Symposium on Algorithms and Computation, ISAAC 2024. Mestre, J. & Wirth, A. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, (Leibniz International Proceedings in Informatics, LIPIcs; vol. 322).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • 2023

      Quartic Samples Suffice for Fourier Interpolation

      Song, Z., Sun, B., Weinstein, O. & Zhang, R., 2023, Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023. IEEE Computer Society, p. 1414-1425 12 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      2 Scopus citations

    • The Complexity of Dynamic Least-Squares Regression

      Jiang, S., Peng, B. & Weinstein, O., 2023, Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023. IEEE Computer Society, p. 1605-1627 23 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      1 Scopus citations
    • 2022

      A Faster Interior-Point Method for Sum-Of-Squares Optimization

      Jiang, S., Natura, B. & Weinstein, O., 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, p. 79:1-79:20 20 p. 79. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 229).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      4 Scopus citations

    • Fast Distance Oracles for Any Symmetric Norm

      Deng, Y., Song, Z., Weinstein, O. & Zhang, R., 2022, Advances in Neural Information Processing Systems 35 - 36th Conference on Neural Information Processing Systems, NeurIPS 2022. Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K. & Oh, A. (eds.). Neural information processing systems foundation, (Advances in Neural Information Processing Systems; vol. 35).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      3 Scopus citations
    • 2021

      A faster algorithm for solving general LPs

      Jiang, S., Song, Z., Weinstein, O. & Zhang, H., 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. 823-832 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      41 Scopus citations

    • Training (overparametrized) neural networks in near-linear time

      van den Brand, J., Peng, B., Song, Z. & Weinstein, O., 1 Feb 2021, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021. Lee, J. R. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 63. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 185).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      13 Scopus citations
    • 2020

      An adaptive step toward the multiphase conjecture

      Ko, Y. K. & Weinstein, O., Nov 2020, Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020. IEEE Computer Society, p. 752-761 10 p. 9317945. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2020-November).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access

    • How to store a random walk

      Viola, E., Weinstein, O. & Yu, H., 2020, 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020. Chawla, S. (ed.). Association for Computing Machinery, p. 426-445 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2020-January).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      4 Scopus citations

    • Lower bounds for oblivious near-neighbor search

      Larsen, K. G., Malkin, T., Weinstein, O. & Yeo, K., 2020, 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020. Chawla, S. (ed.). Association for Computing Machinery, p. 1116-1134 19 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2020-January).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      6 Scopus citations

    • Polynomial data structure lower bounds in the group model

      Golovnev, A., Posobin, G., Regev, O. & Weinstein, O., Nov 2020, Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020. IEEE Computer Society, p. 740-751 12 p. 9317940. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2020-November).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • Settling the relationship between wilber’s bounds for dynamic optimality

      Lecomte, V. & Weinstein, O., 1 Aug 2020, 28th Annual European Symposium on Algorithms, ESA 2020. Grandoni, F., Herman, G. & Sanders, P. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 68. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 173).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      2 Scopus citations
    • 2019

      Local decodability of the Burrows-Wheeler transform

      Sinha, S. & Weinstein, O., 23 Jun 2019, STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Charikar, M. & Cohen, E. (eds.). Association for Computing Machinery, p. 744-755 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      3 Scopus citations

    • Massively parallel algorithms for finding well-connected components in sparse graphs

      Assadi, S., Sun, X. & Weinstein, O., 16 Jul 2019, PODC 2019 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery, p. 461-470 10 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      32 Scopus citations

    • Static data structure lower bounds imply rigidity

      Dvir, Z., Golovnev, A. & Weinstein, O., 23 Jun 2019, STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Charikar, M. & Cohen, E. (eds.). Association for Computing Machinery, p. 967-978 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      15 Scopus citations
    • 2018

      Crossing the logarithmic barrier for dynamic boolean data structure lower bounds

      Larsen, K. G., Weinstein, O. & Yu, H., 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. 485-492 8 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      13 Scopus citations

    • Crossing the logarithmic barrier for dynamic boolean data structure lower bounds

      Green Larsen, K., Weinstein, O. & Yu, H., 23 Oct 2018, 2018 Information Theory and Applications Workshop, ITA 2018. Institute of Electrical and Electronics Engineers Inc., 8503262. (2018 Information Theory and Applications Workshop, ITA 2018).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      3 Scopus citations
    • 2017

      ETH hardness for densest-k-Subgraph with perfect completeness

      Braverman, M., Ko, Y. K., Rubinstein, A. & Weinstein, O., 2017, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. Klein, P. N. (ed.). Association for Computing Machinery, p. 1326-1341 16 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 0).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      28 Scopus citations

    • The minrank of random graphs

      Golovnev, A., Regev, O. & Weinstein, O., 1 Aug 2017, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 20th International Workshop, APPROX 2017 and 21st International Workshop, RANDOM 2017. Rolim, J. D. P., Jansen, K., Williamson, D. P. & Vempala, S. S. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 46. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 81).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      5 Scopus citations
    • 2016

      Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication

      Weinstein, O. & Yu, H., 14 Dec 2016, Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016. IEEE Computer Society, p. 305-314 10 p. 7782944. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2016-December).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      11 Scopus citations

    • An improved upper bound for the most informative boolean function conjecture

      Ordentlich, O., Shayevitz, O. & Weinstein, O., 10 Aug 2016, Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory. Institute of Electrical and Electronics Engineers Inc., p. 500-504 5 p. 7541349. (IEEE International Symposium on Information Theory - Proceedings; vol. 2016-August).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      8 Scopus citations

    • Distributed signaling games

      Feldman, M., Tennenholtz, M. & Weinstein, O., 1 Aug 2016, 24th Annual European Symposium on Algorithms, ESA 2016. Zaroliagis, C. & Sankowski, P. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 41. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 57).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • On the Communication Complexity of Approximate Fixed Points

      Roughgarden, T. & Weinstein, O., 14 Dec 2016, Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016. IEEE Computer Society, p. 229-238 10 p. 7782935. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2016-December).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      16 Scopus citations
    • 2015

      An interactive information odometer and applications

      Braverman, M. & Weinstein, O., 14 Jun 2015, STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 341-350 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. 14-17-June-2015).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      20 Scopus citations

    • Approximating the best Nash Equilibrium in no (1ogn)-time breaks the exponential time hypothesis

      Braverman, M., Ko, Y. K. & Weinstein, O., 2015, Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015. January ed. Association for Computing Machinery, p. 970-982 13 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2015-January, no. January).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      39 Scopus citations

    • The simultaneous communication of disjointness with applications to data streams

      Weinstein, O. & Woodruff, D. P., 2015, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings. Halldorsson, M. M., Kobayashi, N., Speckmann, B. & Iwama, K. (eds.). Springer Verlag, p. 1082-1093 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 9134).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      18 Scopus citations

    • Welfare and revenue guarantees for competitive bundling equilibrium

      Dobzinski, S., Feldman, M., Talgam-Cohen, I. & Weinstein, O., 2015, Web and Internet Economics - 11th International Conference, WINE 2015, Proceedings. Schäfer, G. & Markakis, E. (eds.). Springer Verlag, p. 300-313 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 9470).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      6 Scopus citations

    • Welfare Maximization with Limited Interaction

      Alon, N., Nisan, N., Raz, R. & Weinstein, O., 11 Dec 2015, Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015. IEEE Computer Society, p. 1499-1512 14 p. 7354469. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2015-December).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      23 Scopus citations
    • 2014

      Toward better formula lower bounds: An information complexity approach to the KRW composition conjecture

      Gavinsky, D., Meir, O., Weinstein, O. & Wigderson, A., 2014, STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 213-222 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      14 Scopus citations
    • 2013

      Direct products in communication complexity

      Braverman, M., Weinstein, O., Rao, A. & Yehudayoff, A., 2013, Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013. p. 746-755 10 p. 6686211. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      51 Scopus citations

    • Direct product via round-preserving compression

      Braverman, M., Rao, A., Weinstein, O. & Yehudayoff, A., 2013, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings. PART 1 ed. p. 232-243 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7965 LNCS, no. PART 1).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      23 Scopus citations

    • From information to exact communication

      Braverman, M., Garg, A., Pankratov, D. & Weinstein, O., 2013, STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing. p. 151-160 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      57 Scopus citations

    • Information lower bounds via self-reducibility

      Braverman, M., Garg, A., Pankratov, D. & Weinstein, O., 2013, Computer Science - Theory and Applications - 8th International Computer Science Symposium in Russia, CSR 2013. Springer Verlag, p. 183-194 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7913 LNCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      11 Scopus citations
    • 2012

      A discrepancy lower bound for information complexity

      Braverman, M. & Weinstein, O., 2012, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings. p. 459-470 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7408 LNCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      25 Scopus citations
    • 2011

      Approximating the influence of monotone boolean functions in O(√n) query complexity

      Ron, D., Rubinfeld, R., Safra, M. & Weinstein, O., 2011, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 14th International Workshop, APPROX 2011 and 15th International Workshop, RANDOM 2011, Proceedings. p. 664-675 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6845 LNCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      7 Scopus citations
    Your message has successfully been sent.
    Your message was not sent due to an error.