No photo of Makrand Sinha

View Scopus Profile

Makrand Sinha

  • 19 Conference contribution
  • 4 Article
  • 1 Conference article
Filter
Conference contribution

Search results

  • 2024

    Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack

    Schade, J., Sinha, M. & Weltge, S., 2024, Integer Programming and Combinatorial Optimization - 25th International Conference, IPCO 2024, Proceedings. Vygen, J. & Byrka, J. (eds.). Springer, p. 379-392 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 14679 LNCS).

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

  • Simple Constructions of Linear-Depth t-Designs and Pseudorandom Unitaries

    Metger, T., Poremba, A., Sinha, M. & Yuen, H., 2024, Proceedings - 2024 IEEE 65th Annual Symposium on Foundations of Computer Science, FOCS 2024. IEEE Computer Society, p. 485-492 8 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

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

    Open Access

  • The NISQ Complexity of Collision Finding

    Hamoudi, Y., Liu, Q. & Sinha, M., 2024, Advances in Cryptology – EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Joye, M. & Leander, G. (eds.). Springer, p. 3-32 30 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 14654 LNCS).

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

  • The Power of Adaptivity in Quantum Query Algorithms

    Girish, U., Sinha, M., Tal, A. & Wu, K., Jun 10 2024, STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing. Mohar, B., Shinkar, I. & O�Donnell, R. (eds.). Association for Computing Machinery, p. 1488-1497 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

    Open Access
  • 2023

    Fourier Growth of Communication Protocols for XOR Functions

    Girish, U., Sinha, M., Tal, A. & Wu, K., 2023, Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023. IEEE Computer Society, p. 721-732 12 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

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

    Open Access

  • Quantum Cryptography in Algorithmica

    Kretschmer, W., Qian, L., Sinha, M. & Tal, A., Jun 2 2023, STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing. Saha, B. & Servedio, R. A. (eds.). Association for Computing Machinery, p. 1589-1602 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

    Open Access
  • 2022

    Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms

    Bansal, N., Sinha, M. & de Wolf, R., Jul 1 2022, 37th Computational Complexity Conference, CCC 2022. Lovett, S. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 28. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 234).

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

  • Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing

    Bansal, N., Jiang, H., Meka, R., Singla, S. & Sinha, M., Jan 1 2022, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022. Braverman, M. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 13. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 215).

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

  • Smoothed Analysis of the Komlós Conjecture

    Bansal, N., Jiang, H., Meka, R., Singla, S. & Sinha, M., Jul 1 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, 14. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 229).

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

  • 2021

    k-forrelation optimally separates Quantum and classical query complexity

    Bansal, N. & Sinha, M., Jun 15 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. 1303-1316 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

    Open Access

  • Majorizing measures for the optimizer

    Borst, S., Dadush, D., Olver, N. & Sinha, M., Feb 1 2021, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021. Lee, J. R. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 73. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 185).

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

  • Online discrepancy minimization for stochastic arrivals

    Bansal, N., Jiang, H., Meka, R., Singla, S. & Sinha, M., 2021, ACM-SIAM Symposium on Discrete Algorithms, SODA 2021. Marx, D. (ed.). Association for Computing Machinery, p. 2842-2861 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

  • 2020

    Online vector balancing and geometric discrepancy

    Bansal, N., Jiang, H., Singla, S. & Sinha, M., Jun 8 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. 1139-1152 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

  • 2019

    Exponential Separation between Quantum Communication and Logarithm of Approximate Rank

    Sinha, M. & De Wolf, R., Nov 2019, Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019. IEEE Computer Society, p. 966-981 16 p. 8948635. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2019-November).

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

  • 2018

    Edge estimation with independent set oracles

    Beame, P., Har-Peled, S., NatarajanRamamoorthy, S., Rashtchian, C. & Sinha, M., Jan 1 2018, 9th Innovations in Theoretical Computer Science, ITCS 2018. Karlin, A. R. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 38. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 94).

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

  • Lower bounds for approximating the matching polytope

    Sinha, M., 2018, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. Czumaj, A. (ed.). Association for Computing Machinery, p. 1585-1604 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

    Open Access
  • 2016

    A direct-sum theorem for read-once branching programs

    Rao, A. & Sinha, M., Sep 1 2016, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016. Jansen, K., Mathieu, C., Rolim, J. D. P. & Umans, C. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, (Leibniz International Proceedings in Informatics, LIPIcs; vol. 60).

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

  • Fooling pairs in randomized communication complexity

    Moran, S., Sinha, M. & Yehudayoff, A., 2016, Structural Information and Communication Complexity - 23rd International Colloquium, SIROCCO 2016, Revised Selected Papers. Suomela, J. (ed.). Springer, p. 49-59 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 9988 LNCS).

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

  • On the communication complexity of greater-than

    Ramamoorthy, S. N. & Sinha, M., Apr 4 2016, 2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015. Institute of Electrical and Electronics Engineers Inc., p. 442-444 3 p. 7447037. (2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015).

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