Huacheng Yu

Calculated based on number of publications stored in Pure and citations from Scopus
20112024

Research activity per year

Filter
Conference contribution

Search results

  • 2024

    Randomized vs. Deterministic Separation in time-space tradeoffs of multi-output functions

    Yu, H. & Zhan, W., Jan 2024, 15th Innovations in Theoretical Computer Science Conference, ITCS 2024. Guruswami, V. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 99. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 287).

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

  • Sampling, flowers and communication

    Yu, H. & Zhan, W., Jan 2024, 15th Innovations in Theoretical Computer Science Conference, ITCS 2024. Guruswami, V. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 100. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 287).

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

  • 2023

    Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly

    Kol, G., Paramonov, D., Saxena, R. R. & Yu, H., Jan 1 2023, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023. Kalai, Y. T. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 80. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 251).

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

    1 Scopus citations
  • Dynamic 'Succincter'

    Li, T., Liang, J., Yu, H. & Zhou, R., 2023, Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023. IEEE Computer Society, p. 1715-1733 19 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

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

    2 Scopus citations
  • On Constructing Spanners from Random Gaussian Projections

    Assadi, S., Kapralov, M. & Yu, H., Sep 2023, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023. Megow, N. & Smith, A. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 57. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 275).

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

  • Super-Logarithmic Lower Bounds for Dynamic Graph Problems

    Larsen, K. G. & Yu, H., 2023, Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023. IEEE Computer Society, p. 1589-1604 16 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

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

    Open Access
  • Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries

    Li, T., Liang, J., Yu, H. & Zhou, R., 2023, Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023. IEEE Computer Society, p. 1842-1862 21 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

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

    Open Access
    4 Scopus citations
  • Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut

    Chen, L., Kol, G., Paramonov, D., Saxena, R. R., Song, Z. & Yu, H., 2023, 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023. Association for Computing Machinery, p. 878-924 47 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2023-January).

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

    4 Scopus citations
  • 2022

    Optimal Bounds for Approximate Counting

    Nelson, J. & Yu, H., Jun 12 2022, PODS 2022 - Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. Association for Computing Machinery, p. 119-127 9 p. (Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems).

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

    Open Access
    6 Scopus citations
  • Strong XOR Lemma for Communication with Bounded Rounds: (extended abstract)

    Yu, H., 2022, Proceedings - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, FOCS 2022. IEEE Computer Society, p. 1186-1192 7 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2022-October).

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

    6 Scopus citations
  • 2021

    Almost optimal super-constant-pass streaming lower bounds for reachability

    Chen, L., Kol, G., Paramonov, D., Saxena, R. R., Song, Z. & Yu, H., 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. 570-583 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

    Open Access
    20 Scopus citations
  • Near-optimal two-pass streaming algorithm for sampling random walks over directed graphs

    Chen, L., Kol, G., Paramonov, D., Saxena, R. R., Song, Z. & Yu, H., Jul 1 2021, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021. Bansal, N., Merelli, E. & Worrell, J. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 52. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 198).

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

    8 Scopus citations
  • Tight distributed sketching lower bound for connectivity

    Yu, H., 2021, ACM-SIAM Symposium on Discrete Algorithms, SODA 2021. Marx, D. (ed.). Association for Computing Machinery, p. 1856-1873 18 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

    Open Access
    6 Scopus citations
  • 2020

    Faster update time for turnstile streaming algorithms

    Alman, J. & Yu, H., 2020, 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020. Chawla, S. (ed.). Association for Computing Machinery, p. 1803-1813 11 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2020-January).

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

    Open Access
    5 Scopus citations
  • Fast software cache design for network appliances

    Zhou, D., Yu, H., Kaminsky, M. & Andersen, D. G., 2020, Proceedings of the 2020 USENIX Annual Technical Conference, ATC 2020. USENIX Association, p. 657-671 15 p. (Proceedings of the 2020 USENIX Annual Technical Conference, ATC 2020).

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

    3 Scopus citations
  • 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 proceedingConference contribution

    4 Scopus citations
  • Lower bound for succinct range minimum query

    Liu, M. & Yu, H., 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. 1402-1415 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

    Open Access
    2 Scopus citations
  • Multi-pass graph streaming lower bounds for cycle counting, max-cut, matching size, and other problems

    Assadi, S., Kol, G., Saxena, R. R. & Yu, H., Nov 2020, Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020. IEEE Computer Society, p. 354-364 11 p. 9317902. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2020-November).

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

    Open Access
    26 Scopus citations
  • Nearly optimal static Las Vegas succinct dictionary

    Yu, H., 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. 1389-1401 13 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

    Open Access
    7 Scopus citations
  • Succinct filters for sets of unknown sizes

    Liu, M., Yin, Y. & Yu, H., Jun 1 2020, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020. Czumaj, A., Dawar, A. & Merelli, E. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 79. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 168).

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

    12 Scopus citations
  • 2019

    Optimal succinct rank data structure via approximate nonnegative tensor decomposition

    Yu, H., Jun 23 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. 955-966 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

    Open Access
    7 Scopus citations
  • Pruning based distance sketches with provable guarantees on random graphs

    Zhang, H., Yu, H. & Goel, A., May 13 2019, The Web Conference 2019 - Proceedings of the World Wide Web Conference, WWW 2019. Association for Computing Machinery, Inc, p. 2301-2311 11 p. (The Web Conference 2019 - Proceedings of the World Wide Web Conference, WWW 2019).

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

    Open Access
    4 Scopus citations
  • 2018

    Cell-Probe lower bounds from online communication complexity

    Alman, J., Wang, J. R. & Yu, H., Jun 20 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. 239-252 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

    Open Access
    5 Scopus citations
  • Crossing the logarithmic barrier for dynamic boolean data structure lower bounds

    Larsen, K. G., Weinstein, O. & Yu, H., Jun 20 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 proceedingConference contribution

    Open Access
    13 Scopus citations
  • Crossing the logarithmic barrier for dynamic boolean data structure lower bounds

    Green Larsen, K., Weinstein, O. & Yu, H., Oct 23 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 proceedingConference contribution

    Open Access
    3 Scopus citations
  • 2017

    Beating brute force for systems of polynomial equations over finite fields

    Lokshtanov, D., Paturi, R., Tamaki, S., Williams, R. & Yu, H., 2017, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. Klein, P. N. (ed.). Association for Computing Machinery, p. 2190-2202 13 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 0).

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

    Open Access
    43 Scopus citations
  • DecreaseKeys are expensive for external memory priority queues

    Eenberg, K., Larsen, K. G. & Yu, H., Jun 19 2017, STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. McKenzie, P., King, V. & Hatami, H. (eds.). Association for Computing Machinery, p. 1081-1093 13 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F128415).

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

    Open Access
    8 Scopus citations
  • 2016

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

    Weinstein, O. & Yu, H., Dec 14 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 proceedingConference contribution

    Open Access
    11 Scopus citations
  • Cell-probe lower bounds for dynamic problems via a new communication model

    Yu, H., Jun 19 2016, STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. Mansour, Y. & Wichs, D. (eds.). Association for Computing Machinery, p. 362-374 13 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. 19-21-June-2016).

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

    Open Access
    7 Scopus citations
  • 2015

    An improved combinatorial algorithm for boolean matrix multiplication

    Yu, H., 2015, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings. Halldorsson, M. M., Kobayashi, N., Speckmann, B. & Iwama, K. (eds.). Springer Verlag, p. 1094-1105 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 proceedingConference contribution

    33 Scopus citations
  • Finding four-node subgraphs in triangle time

    Williams, V. V., Wang, J. R., Williams, R. & Yu, H., 2015, Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015. January ed. Association for Computing Machinery, p. 1671-1680 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2015-January, no. January).

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

    Open Access
    67 Scopus citations
  • Matching triangles and basing hardness on an extremely popular conjecture

    Abboud, A., Williams, V. V. & Yu, H., Jun 14 2015, STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 41-50 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. 14-17-June-2015).

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

    Open Access
    64 Scopus citations
  • More applications of the polynomial method to algorithm design

    Abboud, A., Williams, R. & Yu, H., 2015, Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015. January ed. Association for Computing Machinery, p. 218-230 13 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2015-January, no. January).

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

    Open Access
    119 Scopus citations
  • 2014

    Finding orthogonal vectors in discrete structures

    Williams, R. & Yu, H., 2014, Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. Association for Computing Machinery, p. 1867-1877 11 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

    43 Scopus citations
  • 2011

    A new variation of hat guessing games

    Ma, T., Sun, X. & Yu, H., 2011, Computing and Combinatorics - 17th Annual International Conference, COCOON 2011, Proceedings. p. 616-626 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6842 LNCS).

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

    Open Access
    6 Scopus citations