Papers are listed in reverse chronological order.

1. Deterministic list decoding of Reed-Solomon codes
   • Authors: Soham Chatterjee, Prahladh Harsha, and Mrinal Kumar
   • To appear in Proc. 58th ACM Symp. on Theory of Computing (STOC) (Salt Lake City, UT, 22–26 June), 2026.
   • [ arXiv | eccc ]
2. Fast list-recovery of univariate multiplicity and folded Reed-Solomon codes
   • Authors: Rohan Goyal, Prahladh Harsha, Mrinal Kumar, and Ashutosh Shankar
   • [ arXiv | eccc ]
3. Optimal Online Bipartite Matching in Degree-2 Graphs
   • Authors: Amey Bhangale, Arghya Chakraborty, and Prahladh Harsha
   • In Proc. 36th International Symposium on Algorithms and Computation (ISAAC) (Tainan, Taiwan, 7–10 Dec), vol. 359 of LIPIcs, pages 13:1–13:19, 2025. [BibTeX]
     ⧉ Copy

     @inproceedings{BhangaleCH2025,
       author =          {Amey Bhangale and Arghya Chakraborty and Prahladh Harsha},
       booktitle =     {Proc.\ $36$th International Symposium on Algorithms
                        and Computation (ISAAC)},
       editor =        {Ho-Lin Chen and Wing-Kai Hon and Meng-Tsung Tsai},
       pages =         {13:1--13:19},
       publisher =     {Schloss Dagstuhl},
       series =        {LIPIcs},
       title =         {Optimal Online Bipartite Matching in Degree-2 Graphs},
       volume =        {359},
       year =          {2025},
       city =          {Tainan, Taiwan},
       date =          {7--10~Dec},
       doi =           {10.4230/LIPIcs.ISAAC.2025.13},
       eprint =        {2511.16025},
     }

   • [ arXiv ]
4. Fast list-decoding of univariate multiplicity and folded Reed-Solomon codes
   • Authors: Rohan Goyal, Prahladh Harsha, Mrinal Kumar, and Ashutosh Shankar
   • In Proc. 65th IEEE Symp. on Foundations of Comp. Science (FOCS) (Chicago, IL, 27–30 Oct), pages 328–343, 2024. [BibTeX]
     ⧉ Copy

     @inproceedings{GoyalHKS2024,
       author =          {Rohan Goyal and Prahladh Harsha and Mrinal Kumar and
       Ashutosh Shankar},
       booktitle =     {Proc.\ $65$th IEEE Symp.\ on Foundations of Comp.\
                        Science (FOCS)},
       editor =        {Santosh Vempala},
       pages =         {328--343},
       title =         {Fast list-decoding of univariate multiplicity and
                        folded {R}eed-{S}olomon codes},
       year =          {2024},
       city =          {Chicago, IL},
       date =          {27--30~Oct},
       doi =           {10.1109/FOCS61266.2024.00028},
       eprint =        {2311.17841},
       eccc =          {2023/185},
     }

   • [ arXiv | eccc ]
5. An Improved Line-Point Low-Degree Test
   • Authors: Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, and Madhu Sudan
   • In Proc. 65th IEEE Symp. on Foundations of Comp. Science (FOCS) (Chicago, IL, 27–30 Oct), pages 1883–1892, 2024. [BibTeX]
     ⧉ Copy

     @inproceedings{HarshaKSS2024,
       author =          {Prahladh Harsha and Mrinal Kumar and Ramprasad Saptharishi
       and Madhu Sudan},
       booktitle =     {Proc.\ $65$th IEEE Symp.\ on Foundations of Comp.\
                        Science (FOCS)},
       editor =        {Santosh Vempala},
       pages =         {1883--1892},
       title =         {An Improved Line-Point Low-Degree Test},
       year =          {2024},
       city =          {Chicago, IL},
       date =          {27--30~Oct},
       doi =           {10.1109/FOCS61266.2024.00113},
       eprint =        {2311.12752},
       eccc =          {2023/182},
     }

   • [ arXiv | eccc ]
6. Dot-Product Proofs and Their Applications
   • Authors: Nir Bitansky, Prahladh Harsha, Yuval Ishai, Ron D. Rothblum, and David J. Wu
   • In Proc. 65th IEEE Symp. on Foundations of Comp. Science (FOCS) (Chicago, IL, 27–30 Oct), pages 806–825, 2024. [BibTeX]
     ⧉ Copy

     @inproceedings{BitanskyHIRW2024,
       author =          {Nir Bitansky and Prahladh Harsha and Yuval Ishai and Ron
       D. Rothblum and David J. Wu},
       booktitle =     {Proc.\ $65$th IEEE Symp.\ on Foundations of Comp.\
                        Science (FOCS)},
       editor =        {Santosh Vempala},
       pages =         {806--825},
       title =         {Dot-Product Proofs and Their Applications},
       year =          {2024},
       city =          {Chicago, IL},
       date =          {27--30~Oct},
       doi =           {10.1109/FOCS61266.2024.00057},
       eccc =          {2024/114},
       iacr =          {2024/1138},
     }

   • To appear in SIAM J. Comput., 2026.
   • Invited journal paper to special issue for FOCS 2024
   • [ eccc | iacr ]
7. Fast Numerical Multivariate Multipoint Evaluation
   • Authors: Sumanta Ghosh, Prahladh Harsha, Simao Herdade, Mrinal Kumar, and Ramprasad Saptharishi
   • In Proc. 64th IEEE Symp. on Foundations of Comp. Science (FOCS) (Santa Cruz, CA, 6–9 Nov), pages 1426–1439, 2023. [BibTeX]
     ⧉ Copy

     @inproceedings{GhoshHHKS2023,
       author =          {Sumanta Ghosh and Prahladh Harsha and Simao Herdade and
       Mrinal Kumar and Ramprasad Saptharishi},
       booktitle =     {Proc.\ $64$th IEEE Symp.\ on Foundations of Comp.\
                        Science (FOCS)},
       editor =        {Amit Sahai and Shubhangi Saraf and Thomas Vidick},
       pages =         {1426--1439},
       title =         {Fast Numerical Multivariate Multipoint Evaluation},
       year =          {2023},
       city =          {Santa Cruz, CA},
       date =          {6--9~Nov},
       doi =           {10.1109/FOCS57990.2023.00088},
       eprint =        {2304.01191},
       eccc =          {2023/033},
     }

   • To appear in SIAM J. Comput., 2026.
   • [ arXiv | eccc ]
8. Criticality of AC^0-Formulae
   • Authors: Prahladh Harsha, Tulasimohan Molli, and Ashutosh Shankar
   • In Proc. 38th Comput. Complexity Conf. (Warwick, United Kingdom, 17–20 July), vol. 264 of LIPIcs, pages 19:1–19:24, 2023. [BibTeX]
     ⧉ Copy

     @inproceedings{HarshaMS2023,
       author =          {Prahladh Harsha and Tulasimohan Molli and Ashutosh
       Shankar},
       booktitle =     {Proc.\ $38$th Comput.\ Complexity Conf.},
       editor =        {Amnon TaShma},
       pages =         {19:1--19:24},
       publisher =     {Schloss Dagstuhl},
       series =        {LIPIcs},
       title =         {Criticality of ${AC}^{0}$-Formulae},
       volume =        {264},
       year =          {2023},
       city =          {Warwick, United Kingdom},
       date =          {17--20~July},
       doi =           {10.4230/LIPIcs.CCC.2023.19},
       eprint =        {2212.08397},
       eccc =          {2022/182},
     }

   • [ arXiv | eccc ]
9. Downward Self-Reducibility in TFNP
   • Authors: Prahladh Harsha, Daniel Mitropolsky, and Alon Rosen
   • In Proc. 14th Innovations in Theor. Comput. Sci. (ITCS) (Cambride, MA, 10–13 Jan), vol. 251 of LIPIcs, pages 67:1–67:17, 2023. [BibTeX]
     ⧉ Copy

     @inproceedings{HarshaMR2023,
       author =          {Prahladh Harsha and Daniel Mitropolsky and Alon Rosen},
       booktitle =     {Proc.\ $14$th Innovations in Theor.\ Comput.\ Sci.\
                        (ITCS)},
       editor =        {Yael Kalai},
       pages =         {67:1--67:17},
       publisher =     {Schloss Dagstuhl},
       series =        {LIPIcs},
       title =         {Downward Self-Reducibility in {TFNP}},
       volume =        {251},
       year =          {2023},
       city =          {Cambride, MA},
       date =          {10--13~Jan},
       doi =           {10.4230/LIPIcs.ITCS.2023.67},
       eprint =        {2209.10509},
       eccc =          {2022/133},
     }

   • [ arXiv | eccc ]
10. Algorithmizing the Multiplicity Schwartz-Zippel Lemma
    • Authors: Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, and Ashutosh Shankar
    • In Proc. 34th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA) (Florence, Italy, 22–25 Jan), pages 2816–2835, 2023. [BibTeX]
      ⧉ Copy

      @inproceedings{BhandariHKS2023-msz,
        author =          {Siddharth Bhandari and Prahladh Harsha and Mrinal Kumar
        and Ashutosh Shankar},
        booktitle =     {Proc.\ $34$th Annual {ACM}-{SIAM} Symp.\ on Discrete
                         Algorithms (SODA)},
        editor =        {Nikhil Bansal and Viswanath Nagarajan},
        pages =         {2816--2835},
        title =         {Algorithmizing the {M}ultiplicity {S}chwartz-{Z}ippel
                         Lemma},
        year =          {2023},
        city =          {Florence, Italy},
        date =          {22--25~Jan},
        doi =           {10.1137/1.9781611977554.ch106},
        eprint =        {2111.11072},
        eccc =          {2021/163},
      }

    • TheoretiCS, 4(29), 2025. [BibTeX]
      ⧉ Copy

      @article{BhandariHKS2025,
        author =          {Siddharth Bhandari and Prahladh Harsha and Mrinal Kumar
        and Ashutosh Shankar},
        journal =       {Theoreti{CS}},
        note =          {(Preliminary version in \emph{34th SODA}, 2023)},
        number =        {29},
        title =         {Algorithmizing the {M}ultiplicity {S}chwartz-{Z}ippel
                         Lemma},
        volume =        {4},
        year =          {2025},
        doi =           {10.46298/theoretics.25.29},
        eprint =        {2111.11072},
        eccc =          {2021/163},
      }

    • [ arXiv | eccc ]
11. Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes
    • Authors: Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, and Srikanth Srinivasan
    • In Proc. 37th Comput. Complexity Conf. (Philadelphia, PA, USA, 21–23 July), vol. 234 of LIPIcs, pages 32:1–32:14, 2022. [BibTeX]
      ⧉ Copy

      @inproceedings{BhandariHSS2022,
        author =          {Siddharth Bhandari and Prahladh Harsha and Ramprasad
        Saptharishi and Srikanth Srinivasan},
        booktitle =     {Proc.\ $37$th Comput.\ Complexity Conf.},
        editor =        {Shachar Lovett},
        pages =         {32:1--32:14},
        publisher =     {Schloss Dagstuhl},
        series =        {LIPIcs},
        title =         {Vanishing Spaces of Random Sets and Applications to
                         {R}eed-{M}uller Codes},
        volume =        {234},
        year =          {2022},
        city =          {Philadelphia, PA, USA},
        date =          {21--23~July},
        doi =           {10.4230/LIPIcs.CCC.2022.32},
        eprint =        {2205.10749},
        eccc =          {2022/075},
      }

    • [ arXiv | eccc ]
12. Mixing of 3-term progressions in Quasirandom Groups
    • Authors: Amey Bhangale, Prahladh Harsha, and Sourya Roy
    • In Proc. 13th Innovations in Theor. Comput. Sci. (ITCS) (Virtual Conference, 31 Jan–3 Feb), vol. 215 of LIPIcs, pages 20:1–20:9, 2022. [BibTeX]
      ⧉ Copy

      @inproceedings{BhangaleHR2022,
        author =        {Amey Bhangale and Prahladh Harsha and Sourya Roy},
        booktitle =     {Proc.\ $13$th Innovations in Theor.\ Comput.\ Sci.\
                         (ITCS)},
        editor =        {Mark Braverman},
        pages =         {20:1--20:9},
        publisher =     {Schloss Dagstuhl},
        series =        {LIPIcs},
        title =         {Mixing of 3-term progressions in Quasirandom Groups},
        volume =        {215},
        year =          {2022},
        city =          {Virtual Conference},
        date =          {31~Jan--3~Feb},
        doi =           {10.4230/LIPIcs.ITCS.2022.20},
        eprint =        {2109.12627},
        eccc =          {2021/142},
      }

    • [ arXiv | eccc ]
13. Ideal-theoretic Explanation of Capacity-achieving Decoding
    • Authors: Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, and Madhu Sudan
    • In Proc. 25th International Conf. on Randomization and Computation (RANDOM) (Virtual Conference, 16–18 Aug), vol. 207 of LIPIcs, pages 56:1–56:21, 2021. [BibTeX]
      ⧉ Copy

      @inproceedings{BhandariHKS2021-affineFRS,
        author =          {Siddharth Bhandari and Prahladh Harsha and Mrinal Kumar
        and Madhu Sudan},
        booktitle =     {Proc.\ $25$th International Conf.\ on Randomization
                         and Computation (RANDOM)},
        editor =        {Wootters, Mary and Sanit\`{a}, Laura},
        pages =         {56:1--56:21},
        publisher =     {Schloss Dagstuhl},
        series =        {LIPIcs},
        title =         {Ideal-theoretic Explanation of Capacity-achieving
                         Decoding},
        volume =        {207},
        year =          {2021},
        city =          {Virtual Conference},
        date =          {16--18~Aug},
        doi =           {10.4230/LIPIcs.APPROX/RANDOM.2021.56},
        eprint =        {2103.07930},
        eccc =          {2021/036},
      }

    • IEEE Trans. Inform. Theory, 70(2):1107–1123, 2024. [BibTeX]
      ⧉ Copy

      @article{BhandariHKS2024-affineFRS,
        author =          {Siddharth Bhandari and Prahladh Harsha and Mrinal Kumar
        and Madhu Sudan},
        journal =       {IEEE Trans.\ Inform.\ Theory},
        note =          {(Preliminary version in \emph{25th RANDOM}, 2021)},
        number =        {2},
        pages =         {1107--1123},
        title =         {Ideal-theoretic Explanation of Capacity-achieving
                         Decoding},
        volume =        {70},
        year =          {2024},
        doi =           {10.1109/TIT.2023.3345890},
        eprint =        {2103.07930},
        eccc =          {2021/036},
      }

    • [ arXiv | eccc ]
14. Decoding Multivariate Multiplicity Codes over Product Sets
    • Authors: Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, and Madhu Sudan
    • In Proc. 53rd ACM Symp. on Theory of Computing (STOC) (Virtual Conference, 21–25 June), pages 1489–1501, 2021. [BibTeX]
      ⧉ Copy

      @inproceedings{BhandariHKS2021-mgrid,
        author =          {Siddharth Bhandari and Prahladh Harsha and Mrinal Kumar
        and Madhu Sudan},
        booktitle =     {Proc.\ $53$rd ACM Symp.\ on Theory of Computing
                         (STOC)},
        editor =        {Samir Khuller and Virginia Vassilevska Williams},
        pages =         {1489--1501},
        title =         {Decoding Multivariate Multiplicity Codes over Product
                         Sets},
        year =          {2021},
        city =          {Virtual Conference},
        date =          {21--25~June},
        doi =           {10.1145/3406325.3451027},
        eprint =        {2012.01530},
        eccc =          {2020/179},
      }

    • IEEE Trans. Inform. Theory, 70(1):154–169, 2024. [BibTeX]
      ⧉ Copy

      @article{BhandariHKS2024-mgrid,
        author =          {Siddharth Bhandari and Prahladh Harsha and Mrinal Kumar
        and Madhu Sudan},
        journal =       {IEEE Trans.\ Inform.\ Theory},
        note =          {(Preliminary version in \emph{53rd STOC}, 2021)},
        number =        {1},
        pages =         {154--169},
        title =         {Decoding Multivariate Multiplicity Codes over Product
                         Sets},
        volume =        {70},
        year =          {2024},
        doi =           {10.1109/TIT.2023.3306849},
        eprint =        {2012.01530},
        eccc =          {2020/179},
      }

    • [ arXiv | eccc ]
15. City-Scale Agent-Based Simulators for the Study of Non-pharmaceutical Interventions in the Context of the COVID-19 Epidemic.
    • Authors: Shubhada Agrawal, Siddharth Bhandari, Anirban Bhattacharjee, Anand Deo, Narendra M. Dixit, Prahladh Harsha, Sandeep Juneja, Poonam Kesarwani, Aditya Krishna Swamy, Preetam Patil, Nihesh Rathod, Ramprasad Saptharishi, Sharad Shriram, Piyush Srivastava, Rajesh Sundaresan, Nidhin Koshy Vaidhiyan, and Sarath Yasodharan
    • J. Indian Inst. Sci., 100:809–847, 2020. [BibTeX]
      ⧉ Copy

      @article{IISc-TIFR-covid19,
        author =          {Shubhada Agrawal and Siddharth Bhandari and Anirban
        Bhattacharjee and Anand Deo and Narendra M. Dixit and Prahladh Harsha and
        Sandeep Juneja and Poonam Kesarwani and Aditya Krishna Swamy and Preetam
        Patil and Nihesh Rathod and Ramprasad Saptharishi and Sharad Shriram and
        Piyush Srivastava and Rajesh Sundaresan and Nidhin Koshy Vaidhiyan and Sarath
        Yasodharan},
        journal =       {J. Indian Inst.\ Sci.},
        pages =         {809--847},
        title =         {City-Scale Agent-Based Simulators for the Study of
                         Non-pharmaceutical Interventions in the Context of
                         the {COVID-19} Epidemic.},
        volume =        {100},
        year =          {2020},
        doi =           {10.1007/s41745-020-00211-3},
        eprint =        {2008.04849},
      }

    • This article is based on an earlier working report titled COVID-19 Epidemic Study I: Unlocking the Lockdown in India.
    • [ url | arXiv | GitHub ]
16. COVID-19 Epidemic in Mumbai: Projections, full economic opening, and containment zones versus contact tracing and testing: An Update
    • Authors: Prahladh Harsha, Sandeep Juneja, Daksh Mittal, and Ramprasad Saptharishi
    • [ arXiv | GitHub ]
17. Explicit SoS lower bounds from high-dimensional expanders
    • Authors: Irit Dinur, Yuval Filmus, Prahladh Harsha, and Madhur Tulsiani
    • In Proc. 12th Innovations in Theor. Comput. Sci. (ITCS) (Virtual Conference, 6–8 Jan), vol. 185 of LIPIcs, pages 40:1–40:16, 2021. [BibTeX]
      ⧉ Copy

      @inproceedings{DinurFHT2021,
        author =          {Irit Dinur and Yuval Filmus and Prahladh Harsha and Madhur
        Tulsiani},
        booktitle =     {Proc.\ $12$th Innovations in Theor.\ Comput.\ Sci.\
                         (ITCS)},
        editor =        {James R. Lee},
        pages =         {40:1--40:16},
        publisher =     {Schloss Dagstuhl},
        series =        {LIPIcs},
        title =         {Explicit {SoS} lower bounds from high-dimensional
                         expanders},
        volume =        {185},
        year =          {2021},
        city =          {Virtual Conference},
        date =          {6--8~Jan},
        doi =           {10.4230/LIPIcs.ITCS.2021.38},
        eprint =        {2009.05218},
        eccc =          {2020/136},
      }

    • [ arXiv | eccc ]
18. COVID-19 Epidemic Study II: Phased Emergence From the Lockdown in Mumbai
    • Authors: Prahladh Harsha, Sandeep Juneja, Preetam Patil, Nihesh Rathod, Ramprasad Saptharishi, Sarath Yasodharan, Sharad Shriram, Piyush Srivastava, Rajesh Sundaresan, and Nidhin Koshy Vaidhiyan
    • [ arXiv | GitHub ]
19. Locally testable codes via high-dimensional expanders
    • Authors: Yotam Dikstein, Irit Dinur, Prahladh Harsha, and Noga Ron-Zewi
    • [ arXiv | eccc ]
20. Rigid matrices from rectangular PCPs or Hard Claims have Complex Proofs
    • Authors: Amey Bhangale, Prahladh Harsha, Orr Paradise, and Avishay Tal
    • In Proc. 61st IEEE Symp. on Foundations of Comp. Science (FOCS) (Virtual Conference, 16–19 Nov), pages 858–869, 2020. [BibTeX]
      ⧉ Copy

      @inproceedings{BhangaleHPT2020,
        author =          {Amey Bhangale and Prahladh Harsha and Orr Paradise and
        Avishay Tal},
        booktitle =     {Proc.\ $61$st IEEE Symp.\ on Foundations of Comp.\
                         Science (FOCS)},
        editor =        {Sandy Irani},
        pages =         {858--869},
        title =         {Rigid matrices from rectangular {PCP}s or {H}ard
                         {C}laims have {C}omplex {P}roofs},
        year =          {2020},
        city =          {Virtual Conference},
        date =          {16--19~Nov},
        doi =           {10.1109/FOCS46700.2020.00084},
        eprint =        {2005.03123},
        eccc =          {2020/075},
      }

    • SIAM J. Comput., 53(2):480–523, 2024. [BibTeX]
      ⧉ Copy

      @article{BhangaleHPT2024,
        author =          {Amey Bhangale and Prahladh Harsha and Orr Paradise and
        Avishay Tal},
        journal =       {SIAM J. Comput.},
        note =          {(Preliminary version in \emph{61st FOCS},2020)},
        number =        {2},
        pages =         {480--523},
        title =         {Rigid matrices from rectangular {PCP}s or {H}ard
                         {C}laims have {C}omplex {P}roofs},
        volume =        {53},
        year =          {2024},
        doi =           {10.1137/22M1495597},
        eprint =        {2005.03123},
        eccc =          {2020/075},
      }

    • [ arXiv | eccc ]
21. On the elementary construction of High-Dimensional Expanders of Kaufman and Oppenheim
    • Authors: Prahladh Harsha and Ramprasad Saptharishi
    • Theory Comput., 20(5):1–22, 2024. [BibTeX]
      ⧉ Copy

      @article{HarshaS2024,
        author =        {Prahladh Harsha and Ramprasad Saptharishi},
        journal =       {Theory Comput.},
        number =        {5},
        pages =         {1--22},
        title =         {On the elementary construction of High-Dimensional
                         Expanders of {K}aufman and {O}ppenheim},
        volume =        {20},
        year =          {2024},
        doi =           {10.4086/toc.2024.v020a005},
        eprint =        {1912.11225},
      }

    • [ arXiv ]
22. Improved Hardness for 3LIN via Linear Label Cover
    • Authors: Prahladh Harsha, Subhash Khot, Euiwoong Lee, and Devanathan Thiruvenkatachari
    • In Proc. 22nd International Conf. on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) (Cambridge, MA, 20–22 Sep), vol. 137 of LIPIcs, pages 9:1–9:16, 2019. [BibTeX]
      ⧉ Copy

      @inproceedings{HarshaKLT2019,
        author =          {Prahladh Harsha and Subhash Khot and Euiwoong Lee and
        Devanathan Thiruvenkatachari},
        booktitle =     {Proc.\ $22$nd International Conf.\ on Approximation
                         Algorithms for Combinatorial Optimization Problems
                         (APPROX)},
        editor =        {Dimitris Achlioptas and L\'{a}szl\'{o} A. V\^{e}gh},
        pages =         {9:1--9:16},
        publisher =     {Schloss Dagstuhl},
        series =        {LIPIcs},
        title =         {Improved Hardness for {3LIN} via Linear Label Cover},
        volume =        {137},
        year =          {2019},
        city =          {Cambridge, MA},
        date =          {20--22~Sep},
        doi =           {10.4230/LIPIcs.APPROX-RANDOM.2019.9},
        eccc =          {2019/093},
      }

    • [ eccc ]
23. From Local Testing to Robust Testing via Agreement Testing
    • Authors: Irit Dinur, Prahladh Harsha, Tali Kaufman, and Noga Ron-Zewi
    • In Proc. 10th Innovations in Theor. Comput. Sci. (ITCS) (San Diego, CA, 10–12 Jan), vol. 124 of LIPIcs, pages 29:1–29:18, 2019. [BibTeX]
      ⧉ Copy

      @inproceedings{DinurHKR2019,
        author =          {Irit Dinur and Prahladh Harsha and Tali Kaufman and Noga
        Ron-Zewi},
        booktitle =     {Proc.\ $10$th Innovations in Theor.\ Comput.\ Sci.\
                         (ITCS)},
        editor =        {Avrim Blum},
        pages =         {29:1--29:18},
        publisher =     {Schloss Dagstuhl},
        series =        {LIPIcs},
        title =         {From Local Testing to Robust Testing via Agreement
                         Testing},
        volume =        {124},
        year =          {2019},
        city =          {San Diego, CA},
        date =          {10--12~Jan},
        doi =           {10.4230/LIPIcs.ITCS.2019.29},
        eccc =          {2018/198},
      }

    • Theory Comput., 18(12):1–25, 2022. [BibTeX]
      ⧉ Copy

      @article{DinurHKR2022,
        author =          {Irit Dinur and Prahladh Harsha and Tali Kaufman and Noga
        Ron-Zewi},
        journal =       {Theory Comput.},
        note =          {(Preliminary version in \emph{10th ITCS}, 2019)},
        number =        {12},
        pages =         {1--25},
        title =         {From Local Testing to Robust Testing via Agreement
                         Testing},
        volume =        {18},
        year =          {2022},
        doi =           {10.4086/toc.2022.v018a012},
        eccc =          {2018/198},
      }

    • [ eccc ]
24. On the Probabilistic Degree of OR over the Reals
    • Authors: Siddharth Bhandari, Prahladh Harsha, Tulasimohan Molli, and Srikanth Srinivasan
    • In Proc. 38th IARCS Annual Conf. on Foundations of Software Tech. and Theoretical Comp. Science (FSTTCS) (Ahmedabad, India, 10–14 Dec), vol. 122 of LIPIcs, pages 5:1–5:12, 2018. [BibTeX]
      ⧉ Copy

      @inproceedings{BhandariHMS2018,
        author =          {Siddharth Bhandari and Prahladh Harsha and Tulasimohan
        Molli and Srikanth Srinivasan},
        booktitle =     {Proc. $38$th IARCS Annual Conf.\ on Foundations of
                         Software Tech.\ and Theoretical Comp.\ Science
                         (FSTTCS)},
        editor =        {Sumit Ganguly and Paritosh Pandya},
        pages =         {5:1--5:12},
        publisher =     {Schloss Dagstuhl},
        series =        {LIPIcs},
        title =         {On the Probabilistic Degree of {OR} over the {R}eals},
        volume =        {122},
        year =          {2018},
        city =          {Ahmedabad, India},
        date =          {10--14~Dec},
        doi =           {10.4230/LIPIcs.FSTTCS.2018.5},
        eprint =        {1812.01982},
        eccc =          {2018/207},
      }

    • Random Structures Algorithms, 59(1):53–67, 2021. [BibTeX]
      ⧉ Copy

      @article{BhandariHMS2021,
        author =          {Siddharth Bhandari and Prahladh Harsha and Tulasimohan
        Molli and Srikanth Srinivasan},
        journal =       {Random Structures Algorithms},
        note =          {(Preliminary version in \emph{38th FSTTCS}, 2018)},
        number =        {1},
        pages =         {53--67},
        title =         {On the Probabilistic Degree of {OR} over the {R}eals},
        volume =        {59},
        year =          {2021},
        doi =           {10.1002/rsa.20991},
        eprint =        {1812.01982},
        eccc =          {2018/207},
      }

    • [ arXiv | eccc ]
25. List Decoding with Double Samplers
    • Authors: Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, and Amnon TaShma
    • In Proc. 30th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA) (San Diego, CA, 6–9 Jan), pages 2134–2153, 2019. [BibTeX]
      ⧉ Copy

      @inproceedings{DinurHKNT2019,
        author =          {Irit Dinur and Prahladh Harsha and Tali Kaufman and Inbal
        Livni Navon and Amnon {TaShma}},
        booktitle =     {Proc.\ $30$th Annual {ACM}-{SIAM} Symp.\ on Discrete
                         Algorithms (SODA)},
        editor =        {Timothy M. Chan},
        pages =         {2134--2153},
        title =         {List Decoding with Double Samplers},
        year =          {2019},
        city =          {San Diego, CA},
        date =          {6--9~Jan},
        doi =           {10.1137/1.9781611975482.129},
        eprint =        {1808.00425},
        eccc =          {2018/198},
      }

    • SIAM J. Comput., 50(2):301–349, 2021. [BibTeX]
      ⧉ Copy

      @article{DinurHKNT2021,
        author =          {Irit Dinur and Prahladh Harsha and Tali Kaufman and Inbal
        Livni Navon and Amnon {TaShma}},
        journal =       {SIAM J. Comput.},
        note =          {(Preliminary version in \emph{30th SODA}, 2019)},
        number =        {2},
        pages =         {301--349},
        title =         {List Decoding with Double Samplers},
        volume =        {50},
        year =          {2021},
        doi =           {10.1137/19M1276650},
        eprint =        {1808.00425},
        eccc =          {2018/198},
      }

    • [ arXiv | eccc ]
26. On Multilinear Forms: Bias, Correlation, and Tensor Rank
    • Authors: Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, and Mrinal Kumar
    • In Proc. 24th International Conf. on Randomization and Computation (RANDOM) (Virtual Conference, 17–19 Aug), vol. 176 of LIPIcs, pages 29:1–29:23, 2020. [BibTeX]
      ⧉ Copy

      @inproceedings{BhrushundiHHKK2020,
        author =          {Abhishek Bhrushundi and Prahladh Harsha and Pooya Hatami
        and Swastik Kopparty and Mrinal Kumar},
        booktitle =     {Proc.\ $24$th International Conf.\ on Randomization
                         and Computation (RANDOM)},
        editor =        {Jaros\l{}aw Byrka and Raghu Meka},
        pages =         {29:1--29:23},
        publisher =     {Schloss Dagstuhl},
        series =        {LIPIcs},
        title =         {On Multilinear Forms: Bias, Correlation, and Tensor
                         Rank},
        volume =        {176},
        year =          {2020},
        city =          {Virtual Conference},
        date =          {17--19~Aug},
        doi =           {10.4230/LIPIcs.APPROX/RANDOM.2020.29},
        eprint =        {1804.09124},
      }

    • [ arXiv ]
27. Boolean function analysis on high-dimensional expanders
    • Authors: Yotam Dikstein, Irit Dinur, Yuval Filmus, and Prahladh Harsha
    • In Proc. 22nd International Conf. on Randomization and Computation (RANDOM) (Princeton, NJ, 20–22 Aug), vol. 116 of LIPIcs, pages 38:1–38:20, 2018. [BibTeX]
      ⧉ Copy

      @inproceedings{DiksteinDFH2018,
        author =          {Yotam Dikstein and Irit Dinur and Yuval Filmus and
        Prahladh Harsha},
        booktitle =     {Proc.\ $22$nd International Conf.\ on Randomization
                         and Computation (RANDOM)},
        editor =          {Eric Blais and Klaus Jansen and Jos\'{e} D. P. Rolim and
        David Steurer},
        pages =         {38:1--38:20},
        publisher =     {Schloss Dagstuhl},
        series =        {LIPIcs},
        title =         {Boolean function analysis on high-dimensional
                         expanders},
        volume =        {116},
        year =          {2018},
        city =          {Princeton, NJ},
        date =          {20--22~Aug},
        doi =           {10.4230/LIPIcs.APPROX-RANDOM.2018.38},
        eprint =        {1804.08155},
        eccc =          {2018/075},
      }

    • Combinatorica, 44:563–620, 2024. [BibTeX]
      ⧉ Copy

      @article{DiksteinDFH2024,
        author =          {Yotam Dikstein and Irit Dinur and Yuval Filmus and
        Prahladh Harsha},
        journal =       {Combinatorica},
        note =          {(Preliminary version in \emph{22nd RANDOM}, 2018)},
        pages =         {563--620},
        title =         {Boolean function analysis on high-dimensional
                         expanders},
        volume =        {44},
        year =          {2024},
        doi =           {10.1007/s00493-024-00084-5},
        eprint =        {1804.08155},
        eccc =          {2018/075},
      }

    • [ arXiv | eccc ]
28. Sparse juntas on the biased hypercube
    • Authors: Irit Dinur, Yuval Filmus, and Prahladh Harsha
    • In Proc. 30th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA) (San Diego, CA, 6–9 Jan), pages 2124–2133, 2019. [BibTeX]
      ⧉ Copy

      @inproceedings{DinurFH2019,
        author =        {Irit Dinur and Yuval Filmus and Prahladh Harsha},
        booktitle =     {Proc.\ $30$th Annual {ACM}-{SIAM} Symp.\ on Discrete
                         Algorithms (SODA)},
        editor =        {Timothy M. Chan},
        pages =         {2124--2133},
        title =         {Analyzing {B}oolean functions on the biased hypercube
                         via higher-dimensional agreement tests},
        year =          {2019},
        city =          {San Diego, CA},
        date =          {6--9~Jan},
        doi =           {10.1137/1.9781611975482.128},
        eprint =        {1711.09428,1711.09426},
        eccc =          {2017/180,2017/181},
      }

    • TheoretiCS, 3(18):1–44, 2024. [BibTeX]
      ⧉ Copy

      @article{DinurFH2024-ks,
        author =        {Irit Dinur and Yuval Filmus and Prahladh Harsha},
        journal =       {Theoreti{CS}},
        note =          {(Preliminary version in \emph{30th SODA}, 2019)},
        number =        {18},
        pages =         {1--44},
        title =         {Sparse juntas on the biased hypercube},
        volume =        {3},
        year =          {2024},
        doi =           {10.46298/theoretics.24.18},
        eprint =        {1711.09428},
        eccc =          {2017/180},
      }

    • A significant revision of the previous 2017 version [ arXiv | eccc ]
    • An extended abstract of the merged version of the earlier version and the hypergraph agreement theorem appeared as the conference version.
    • [ arXiv | eccc ]
29. Agreement tests on graphs and hypergraphs
    • Authors: Irit Dinur, Yuval Filmus, and Prahladh Harsha
    • In Proc. 30th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA) (San Diego, CA, 6–9 Jan), pages 2124–2133, 2019. [BibTeX]
      ⧉ Copy

      @inproceedings{DinurFH2019,
        author =        {Irit Dinur and Yuval Filmus and Prahladh Harsha},
        booktitle =     {Proc.\ $30$th Annual {ACM}-{SIAM} Symp.\ on Discrete
                         Algorithms (SODA)},
        editor =        {Timothy M. Chan},
        pages =         {2124--2133},
        title =         {Analyzing {B}oolean functions on the biased hypercube
                         via higher-dimensional agreement tests},
        year =          {2019},
        city =          {San Diego, CA},
        date =          {6--9~Jan},
        doi =           {10.1137/1.9781611975482.128},
        eprint =        {1711.09428,1711.09426},
        eccc =          {2017/180,2017/181},
      }

    • SIAM J. Comput., 54(2):279–320, 2025. [BibTeX]
      ⧉ Copy

      @article{DinurFH2025-agree,
        author =        {Irit Dinur and Yuval Filmus and Prahladh Harsha},
        journal =       {SIAM J. Comput.},
        note =          {(Preliminary version in \emph{30th SODA}, 2019)},
        number =        {2},
        pages =         {279--320},
        title =         {Agreement tests on graphs and hypergraphs},
        volume =        {54},
        year =          {2025},
        doi =           {10.1137/21M1397684},
        eprint =        {1711.09426},
        eccc =          {2017/181},
      }

    • An extended abstract of the merged version of this paper and the previous version of the sparse junta paper appeared as the conference version.
    • [ arXiv | eccc ]
30. On polynomial approximations over \mathbbZ/2^k \mathbbZ
    • Authors: Abhishek Bhrushundi, Prahladh Harsha, and Srikanth Srinivasan
    • In Proc. 34th Symp. on Theoretical Aspects of Comp. Science (STACS) (Hannover, Germany, 8–11 Mar), vol. 66 of LIPIcs, pages 12:1–12:12, 2017. [BibTeX]
      ⧉ Copy

      @inproceedings{BhrushundiHS2017,
        author =          {Abhishek Bhrushundi and Prahladh Harsha and Srikanth
        Srinivasan},
        booktitle =     {Proc.\ $34$th Symp.\ on Theoretical Aspects of Comp.\
                         Science (STACS)},
        editor =        {Heribert Vollmer and Brigitte Vall\'{e}e},
        pages =         {12:1--12:12},
        publisher =     {Schloss Dagstuhl},
        series =        {LIPIcs},
        title =         {On polynomial approximations over ${{\mathbb{Z}}/2^k
                         {\mathbb{Z}}}$},
        volume =        {66},
        year =          {2017},
        city =          {Hannover, Germany},
        date =          {8--11~Mar},
        doi =           {10.4230/LIPIcs.STACS.2017.12},
        eprint =        {1701.06268},
        eccc =          {2017/013},
      }

    • [ arXiv | eccc ]
31. Multiplayer parallel repetition for expander games
    • Authors: Irit Dinur, Prahladh Harsha, Rakesh Venkat, and Henry Yuen
    • In Proc. 8th Innovations in Theor. Comput. Sci. (ITCS) (Berkeley, CA, 9–11 Jan), vol. 67 of LIPIcs, pages 37:1–37:16, 2017. [BibTeX]
      ⧉ Copy

      @inproceedings{DinurHVY2017,
        author =          {Irit Dinur and Prahladh Harsha and Rakesh Venkat and Henry
        Yuen},
        booktitle =     {Proc.\ $8$th Innovations in Theor.\ Comput.\ Sci.\
                         (ITCS)},
        editor =        {Christos Papadimitriou},
        pages =         {37:1--37:16},
        publisher =     {Schloss Dagstuhl},
        series =        {LIPIcs},
        title =         {Multiplayer parallel repetition for expander games},
        volume =        {67},
        year =          {2017},
        city =          {Berkeley, CA},
        date =          {9--11~Jan},
        doi =           {10.4230/LIPIcs.ITCS.2017.37},
        eprint =        {1610.08349},
        eccc =          {2016/160},
      }

    • Invited paper for ITCS 2017
    • [ arXiv | eccc ]
32. Robust Multiplication-based Tests for Reed-Muller Codes
    • Authors: Prahladh Harsha and Srikanth Srinivasan
    • In Proc. 36th IARCS Annual Conf. on Foundations of Software Tech. and Theoretical Comp. Science (FSTTCS) (Chennai, India, 13–15 Dec), vol. 65 of LIPIcs, pages 17:1–17:14, 2016. [BibTeX]
      ⧉ Copy

      @inproceedings{HarshaS2016-rm,
        author =        {Prahladh Harsha and Srikanth Srinivasan},
        booktitle =     {Proc. $36$th IARCS Annual Conf.\ on Foundations of
                         Software Tech.\ and Theoretical Comp.\ Science
                         (FSTTCS)},
        editor =          {Akash Lal and S. Akshay and Saket Saurabh and Sandeep
        Sen},
        pages =         {17:1--17:14},
        publisher =     {Schloss Dagstuhl},
        series =        {LIPIcs},
        title =         {Robust Multiplication-based Tests for {R}eed-{M}uller
                         Codes},
        volume =        {65},
        year =          {2016},
        city =          {Chennai, India},
        date =          {13--15~Dec},
        doi =           {10.4230/LIPIcs.FSTTCS.2016.17},
        eprint =        {1612.03086},
      }

    • IEEE Trans. Inform. Theory, 65(1):184–197, 2019. [BibTeX]
      ⧉ Copy

      @article{HarshaS2019-rm,
        author =        {Prahladh Harsha and Srikanth Srinivasan},
        journal =       {IEEE Trans.\ Inform.\ Theory},
        note =          {(Preliminary version in \emph{36th FSTTCS}, 2016)},
        number =        {1},
        pages =         {184--197},
        title =         {Robust Multiplication-based Tests for {R}eed-{M}uller
                         Codes},
        volume =        {65},
        year =          {2019},
        doi =           {10.1109/TIT.2018.2863713},
        eprint =        {1612.03086},
      }

    • [ arXiv ]
33. On Polynomial Approximations to AC^0
    • Authors: Prahladh Harsha and Srikanth Srinivasan
    • In Proc. 20th International Workshop on Randomization and Computation (RANDOM) (Paris, France, 7–9 Sep), vol. 60 of LIPIcs, pages 32:1–32:14, 2016. [BibTeX]
      ⧉ Copy

      @inproceedings{HarshaS2016-ac0,
        author =        {Prahladh Harsha and Srikanth Srinivasan},
        booktitle =     {Proc.\ $20$th International Workshop on Randomization
                         and Computation (RANDOM)},
        editor =          {Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim
        and Chris Umans},
        pages =         {32:1--32:14},
        publisher =     {Schloss Dagstuhl},
        series =        {LIPIcs},
        title =         {On Polynomial Approximations to ${AC}^0$},
        volume =        {60},
        year =          {2016},
        city =          {Paris, France},
        date =          {7--9~Sep},
        doi =           {10.4230/LIPIcs.APPROX-RANDOM.2016.32},
        eprint =        {1604.08121},
      }

    • Random Structures Algorithms, 54(2):289–303, 2019. [BibTeX]
      ⧉ Copy

      @article{HarshaS2019-ac0,
        author =        {Prahladh Harsha and Srikanth Srinivasan},
        journal =       {Random Structures Algorithms},
        note =          {(Preliminary version in \emph{20th RANDOM}, 2016)},
        number =        {2},
        pages =         {289--303},
        title =         {On Polynomial Approximations to ${AC}^0$},
        volume =        {54},
        year =          {2019},
        doi =           {10.1002/rsa.20786},
        eprint =        {1604.08121},
      }

    • [ arXiv ]
34. Embedding approximately low-dimensional \ell^2_2 metrics into \ell_1
    • Authors: Amit Deshpande, Prahladh Harsha, and Rakesh Venkat
    • In Proc. 36th IARCS Annual Conf. on Foundations of Software Tech. and Theoretical Comp. Science (FSTTCS) (Chennai, India, 13–15 Dec), vol. 65 of LIPIcs, pages 10:1–10:13, 2016. [BibTeX]
      ⧉ Copy

      @inproceedings{DeshpandeHV2016,
        author =        {Amit Deshpande and Prahladh Harsha and Rakesh Venkat},
        booktitle =     {Proc. $36$th IARCS Annual Conf.\ on Foundations of
                         Software Tech.\ and Theoretical Comp.\ Science
                         (FSTTCS)},
        editor =          {Akash Lal and S. Akshay and Saket Saurabh and Sandeep
        Sen},
        pages =         {10:1--10:13},
        publisher =     {Schloss Dagstuhl},
        series =        {LIPIcs},
        title =         {Embedding approximately low-dimensional $\ell^2_2$
                         metrics into $\ell_1$},
        volume =        {65},
        year =          {2016},
        city =          {Chennai, India},
        date =          {13--15~Dec},
        doi =           {10.4230/LIPIcs.FSTTCS.2016.10},
        eprint =        {1512.04170},
      }

    • [ arXiv ]
35. Partition bound is quadratically tight for product distributions
    • Authors: Prahladh Harsha, Rahul Jain, and Jaikumar Radhakrishnan
    • In Proc. 43rd International Colloq. of Automata, Languages and Programming (ICALP) (Rome, Italy, 12–15July), vol. 55 of LIPIcs, pages 135:1–135:13, 2016. [BibTeX]
      ⧉ Copy

      @inproceedings{HarshaJR2016,
        author =          {Prahladh Harsha and Rahul Jain and Jaikumar
        Radhakrishnan},
        booktitle =     {Proc.\ $43$rd International Colloq.\ of Automata,
                         Languages and Programming (ICALP)},
        editor =          {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval
        Rabani and Davide Sangiorgi},
        pages =         {135:1--135:13},
        publisher =     {Schloss Dagstuhl},
        series =        {LIPIcs},
        title =         {Partition bound is quadratically tight for product
                         distributions},
        volume =        {55},
        year =          {2016},
        city =          {Rome, Italy},
        date =          {12--15July},
        doi =           {10.4230/LIPIcs.ICALP.2016.135},
        eprint =        {1512.01968},
      }

    • [ arXiv ]
36. Polynomially low error PCPs with polyloglog n queries via modular composition
    • Authors: Irit Dinur, Prahladh Harsha, and Guy Kindler
    • In Proc. 47th ACM Symp. on Theory of Computing (STOC) (Portland, OR, 14–17 June), pages 267–276, 2015. [BibTeX]
      ⧉ Copy

      @inproceedings{DinurHK2015,
        author =        {Irit Dinur and Prahladh Harsha and Guy Kindler},
        booktitle =     {Proc.\ $47$th ACM Symp.\ on Theory of Computing
                         (STOC)},
        editor =        {Rocco A. Servedio and Ronitt Rubinfeld},
        pages =         {267--276},
        title =         {Polynomially low error {PCP}s with polyloglog $n$
                         queries via modular composition},
        year =          {2015},
        city =          {Portland, OR},
        date =          {14--17~June},
        doi =           {10.1145/2746539.2746630},
        eprint =        {1505.06362},
        eccc =          {2015/085},
      }

    • [ arXiv | eccc ]
37. A Characterization of hard-to-cover CSPs
    • Authors: Amey Bhangale, Prahladh Harsha, and Girish Varma
    • In Proc. 30th Comput. Complexity Conf. (Portland, Oregon, 17–19 June), vol. 33 of LIPIcs, pages 280–303, 2015. [BibTeX]
      ⧉ Copy

      @inproceedings{BhangaleHV2015,
        author =        {Amey Bhangale and Prahladh Harsha and Girish Varma},
        booktitle =     {Proc.\ $30$th Comput.\ Complexity Conf.},
        editor =        {David Zuckerman},
        pages =         {280--303},
        publisher =     {Schloss Dagstuhl},
        series =        {LIPIcs},
        title =         {A Characterization of hard-to-cover {CSP}s},
        volume =        {33},
        year =          {2015},
        city =          {Portland, Oregon},
        date =          {17--19~June},
        doi =           {10.4230/LIPIcs.CCC.2015.280},
        eprint =        {1411.7747},
      }

    • Theory Comput., 16(16):1–29, 2020. [BibTeX]
      ⧉ Copy

      @article{BhangaleHV2020,
        author =        {Amey Bhangale and Prahladh Harsha and Girish Varma},
        journal =       {Theory Comput.},
        note =          {(Preliminary version in \emph{$30$th Computational
                         Complexity Conference}, 2015)},
        number =        {16},
        pages =         {1--29},
        title =         {A Characterization of hard-to-cover {CSP}s},
        volume =        {16},
        year =          {2020},
        doi =           {10.4086/toc.2020.v016a016},
        eprint =        {1411.7747},
      }

    • [ arXiv ]
38. Derandomized Graph Product Results Using the Low Degree Long Code
    • Authors: Irit Dinur, Prahladh Harsha, Srikanth Srinivasan, and Girish Varma
    • In Proc. 32nd International Symp. on Theoretical Aspects of Comp. Science (STACS) (Munich, Germany, 4–7 Mar), vol. 30 of LIPIcs, pages 275–287, 2015. [BibTeX]
      ⧉ Copy

      @inproceedings{DinurHSV2015,
        author =          {Irit Dinur and Prahladh Harsha and Srikanth Srinivasan and
        Girish Varma},
        booktitle =     {Proc.\ $32$nd International Symp.\ on Theoretical
                         Aspects of Comp.\ Science (STACS)},
        editor =        {Ernst W. Mayr and Nicolas Ollinger},
        pages =         {275--287},
        publisher =     {Schloss Dagstuhl},
        series =        {LIPIcs},
        title =         {{Derandomized Graph Product Results Using the Low
                         Degree Long Code}},
        volume =        {30},
        year =          {2015},
        city =          {Munich, Germany},
        date =          {4--7~Mar},
        doi =           {10.4230/LIPIcs.STACS.2015.275},
        eprint =        {1411.3517},
      }

    • [ arXiv ]
39. Super-polylogarithmic hypergraph coloring hardness via low-degree long codes
    • Authors: Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, and Girish Varma
    • In Proc. 46th ACM Symp. on Theory of Computing (STOC) (New York, NY, 31 May–3 June), pages 614–623, 2014. [BibTeX]
      ⧉ Copy

      @inproceedings{GuruswamiHHSV2014,
        author =          {Venkatesan Guruswami and Prahladh Harsha and Johan Håstad
        and Srikanth Srinivasan and Girish Varma},
        booktitle =     {Proc.\ $46$th ACM Symp.\ on Theory of Computing
                         (STOC)},
        editor =        {David B. Shmoys},
        pages =         {614--623},
        title =         {Super-polylogarithmic hypergraph coloring hardness
                         via low-degree long codes},
        year =          {2014},
        city =          {New York, NY},
        date =          {31~May--3~June},
        doi =           {10.1145/2591796.2591882},
        eprint =        {1311.7407},
      }

    • SIAM J. Comput., 46(1):132–159, 2017. [BibTeX]
      ⧉ Copy

      @article{GuruswamiHHSV2017,
        author =          {Venkatesan Guruswami and Prahladh Harsha and Johan Håstad
        and Srikanth Srinivasan and Girish Varma},
        journal =       {SIAM J. Comput.},
        note =          {(Preliminary version in \emph{46th STOC}, 2014)},
        number =        {1},
        pages =         {132--159},
        title =         {Super-polylogarithmic hypergraph coloring hardness
                         via low-degree long codes},
        volume =        {46},
        year =          {2017},
        doi =           {10.1137/140995520},
        eprint =        {1311.7407},
      }

    • [ arXiv ]
40. A Strong Direct Product Theorem for the Tribes Function via the Smooth-Rectangle Bound
    • Authors: Prahladh Harsha and Rahul Jain
    • In Proc. 33rd IARCS Annual Conf. on Foundations of Software Tech. and Theoretical Comp. Science (FSTTCS) (Guwahati, India, 12–14 Dec), vol. 24 of LIPIcs, pages 141–152, 2013. [BibTeX]
      ⧉ Copy

      @inproceedings{HarshaJ2013,
        author =        {Prahladh Harsha and Rahul Jain},
        booktitle =     {Proc. $33$rd IARCS Annual Conf.\ on Foundations of
                         Software Tech.\ and Theoretical Comp.\ Science
                         (FSTTCS)},
        editor =        {Anil Seth and Nisheeth K. Vishnoi},
        pages =         {141--152},
        publisher =     {Schloss Dagstuhl},
        series =        {LIPIcs},
        title =         {A Strong Direct Product Theorem for the Tribes
                         Function via the Smooth-Rectangle Bound},
        volume =        {24},
        year =          {2013},
        city =          {Guwahati, India},
        date =          {12--14~Dec},
        doi =           {10.4230/LIPIcs.FSTTCS.2013.141},
        eprint =        {1302.0275},
      }

    • [ arXiv ]
41. Almost settling the hardness of noncommutative determinant
    • Authors: Steve Chien, Prahladh Harsha, Alistair Sinclair, and Srikanth Srinivasan
    • In Proc. 43rd ACM Symp. on Theory of Computing (STOC) (San Jose, CA, 6–8 June), pages 499–508, 2011. [BibTeX]
      ⧉ Copy

      @inproceedings{ChienHSS2011,
        author =          {Steve Chien and Prahladh Harsha and Alistair Sinclair and
        Srikanth Srinivasan},
        booktitle =     {Proc.\ $43$rd ACM Symp.\ on Theory of Computing
                         (STOC)},
        editor =        {Lance Fortnow and Salil P. Vadhan},
        pages =         {499--508},
        title =         {Almost settling the hardness of noncommutative
                         determinant},
        year =          {2011},
        city =          {San Jose, CA},
        date =          {6--8~June},
        doi =           {10.1145/1993636.1993703},
        eprint =        {1101.1169},
      }

    • [ arXiv ]
42. An invariance principle for polytopes
    • Authors: Prahladh Harsha, Adam Klivans, and Raghu Meka
    • In Proc. 42nd ACM Symp. on Theory of Computing (STOC) (Cambridge, MA, 6–8 June), pages 543–552, 2010. [BibTeX]
      ⧉ Copy

      @inproceedings{HarshaKM2010,
        author =        {Prahladh Harsha and Adam Klivans and Raghu Meka},
        booktitle =     {Proc.\ $42$nd ACM Symp.\ on Theory of Computing
                         (STOC)},
        editor =        {Leonard J. Schulman},
        pages =         {543--552},
        title =         {An invariance principle for polytopes},
        year =          {2010},
        city =          {Cambridge, MA},
        date =          {6--8~June},
        doi =           {10.1145/1806689.1806764},
        eprint =        {0912.4884},
      }

    • J. ACM, 59(6):29, 2012. [BibTeX]
      ⧉ Copy

      @article{HarshaKM2012,
        author =        {Prahladh Harsha and Adam Klivans and Raghu Meka},
        journal =       {J. ACM},
        note =          {(Preliminary version in \emph{42nd STOC}, 2010)},
        number =        {6},
        pages =         {29},
        title =         {An invariance principle for polytopes},
        volume =        {59},
        year =          {2012},
        doi =           {10.1145/2395116.2395118},
        eprint =        {0912.4884},
      }

    • [ arXiv ]
43. Bounding the Sensitivity of Polynomial Threshold Functions
    • Authors: Prahladh Harsha, Adam Klivans, and Raghu Meka
    • In Proc. 42nd ACM Symp. on Theory of Computing (STOC) (Cambridge, MA, 6–8 June), pages 533–542, 2010. [BibTeX]
      ⧉ Copy

      @inproceedings{DiakonikolasHKMRST2010,
        author =          {Ilias Diakonikolas and Prahladh Harsha and Adam Klivans
        and Raghu Meka and Prasad Raghavendra and Rocco Servedio and Li-Yang Tan},
        booktitle =     {Proc.\ $42$nd ACM Symp.\ on Theory of Computing
                         (STOC)},
        editor =        {Leonard J. Schulman},
        pages =         {533--542},
        title =         {Bounding the average sensitivity and noise
                         sensitivity of polynomial threshold functions},
        year =          {2010},
        city =          {Cambridge, MA},
        date =          {6--8~June},
        doi =           {10.1145/1806689.1806763},
      }

    • Theory Comput., 10(1):1–24, 2014. [BibTeX]
      ⧉ Copy

      @article{HarshaKM2014,
        author =        {Prahladh Harsha and Adam Klivans and Raghu Meka},
        journal =       {Theory Comput.},
        note =          {(special Issue on Analysis of {B}oolean Functions;
                         Preliminary version in \emph{42nd STOC}, 2010)},
        number =        {1},
        pages =         {1--24},
        title =         {Bounding the Sensitivity of Polynomial Threshold
                         Functions},
        volume =        {10},
        year =          {2014},
        doi =           {10.4086/toc.2014.v010a001},
        eprint =        {0909.5175},
      }

    • The conference version appeared in merged form along with; Diakonikolas, Raghavendra, Servedio and Tan, Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions.
    • Invited journal paper for special issue on `Analysis of Boolean Functions'
    • [ arXiv ]
44. Composition of low-error 2-query PCPs using decodable PCPs
    • Authors: Irit Dinur and Prahladh Harsha
    • In Proc. 50th IEEE Symp. on Foundations of Comp. Science (FOCS) (Atlanta, GA, 24–27 Oct), pages 472–481, 2009. [BibTeX]
      ⧉ Copy

      @inproceedings{DinurH2009,
        author =        {Irit Dinur and Prahladh Harsha},
        booktitle =     {Proc.\ $50$th IEEE Symp.\ on Foundations of Comp.\
                         Science (FOCS)},
        editor =        {Daniel A. Spielman},
        pages =         {472--481},
        title =         {Composition of low-error 2-query {PCP}s using
                         decodable {PCP}s},
        year =          {2009},
        city =          {Atlanta, GA},
        date =          {24--27~Oct},
        doi =           {10.1109/FOCS.2009.8},
        eccc =          {2009/042},
      }

    • SIAM J. Comput., 42(6):2452–2486, 2013. [BibTeX]
      ⧉ Copy

      @article{DinurH2013-special,
        author =        {Irit Dinur and Prahladh Harsha},
        journal =       {SIAM J. Comput.},
        note =          {(special issue for FOCS 2009; Preliminary version in
                         \emph{51st FOCS}, 2009)},
        number =        {6},
        pages =         {2452--2486},
        title =         {Composition of low-error 2-query {PCP}s using
                         decodable {PCP}s},
        volume =        {42},
        year =          {2013},
        doi =           {10.1137/100788161},
        eccc =          {2009/042},
      }

    • Invited journal paper to special issue for FOCS 2009
    • [ eccc | pdf ]
45. Complexity of Inference in Graphical Models
    • Authors: Venkat Chandrasekaran, Nathan Srebro, and Prahladh Harsha
    • In Proc. 24th Conf. on Uncertainty in Artificial Intelligence (UAI) (Helsinki, Finland, 9–12 July), 2008. [BibTeX]
      ⧉ Copy

      @inproceedings{ChandrasekaranSH2008,
        author =          {Venkat Chandrasekaran and Nathan Srebro and Prahladh
        Harsha},
        booktitle =     {Proc.\ 24th Conf.\ on Uncertainty in Artificial
                         Intelligence (UAI)},
        editor =        {David A. McAllester and Petri Myllym{\"{a}}ki},
        publisher =     {{AUAI} Press},
        title =         {Complexity of Inference in Graphical Models},
        year =          {2008},
        city =          {Helsinki, Finland},
        date =          {9--12~July},
        eprint =        {1206.3240},
        url =           {https://www.auai.org/uai2008/UAI_camera_ready/
                        chandrasekaran.pdf},
      }

    • [ url | arXiv | pdf ]
46. Sound 2-query PCPPs are long
    • Authors: Eli Ben-Sasson, Prahladh Harsha, Oded Lachish, and Arie Matsliah
    • In Proc. 35th International Colloq. of Automata, Languages and Programming (ICALP), Part I (Reykjavik, Iceland, 6–13 July), vol. 5125 of LNCS, pages 686–697, 2008. [BibTeX]
      ⧉ Copy

      @inproceedings{BenSassonHLM2008,
        author =          {Eli {Ben-Sasson} and Prahladh Harsha and Oded Lachish and
        Arie Matsliah},
        booktitle =     {Proc.\ $35$th International Colloq.\ of Automata,
                         Languages and Programming (ICALP), Part I},
        editor =          {Luca Aceto and Ivan Damg\.{a}rd and Leslie Ann Goldberg
        and Magn\'{u}s M. Halld\'{o}rsson and Anna Ing\'{o}lfsd\'{o}ttir and Igor
        Walukiewicz},
        pages =         {686--697},
        publisher =     {Springer},
        series =        {LNCS},
        title =         {Sound 3-query {PCPP}s are long},
        volume =        {5125},
        year =          {2008},
        city =          {Reykjavik, Iceland},
        date =          {6--13~July},
        doi =           {10.1007/978-3-540-70575-8_56},
      }

    • ACM T. Comput. Theory, 1(2):1–49, 2009. [BibTeX]
      ⧉ Copy

      @article{BenSassonHLM2009,
        author =          {Eli {Ben-Sasson} and Prahladh Harsha and Oded Lachish and
        Arie Matsliah},
        journal =       {{ACM} T.\ Comput.\ Theory},
        note =          {(Preliminary version in \emph{35th ICALP}, 2008)},
        number =        {2},
        pages =         {1--49},
        title =         {Sound 2-query {PCPP}s are long},
        volume =        {1},
        year =          {2009},
        doi =           {10.1145/1595391.1595394},
      }

    • [ pdf ]
47. Minimizing Average Latency in Oblivious Routing
    • Authors: Prahladh Harsha, Thomas Hayes, Hariharan Narayanan, Harald Räcke, and Jaikumar Radhakrishnan
    • In Proc. 19th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA) (San Francisco, CA, 20–22 Jan), pages 200–207, 2008. [BibTeX]
      ⧉ Copy

      @inproceedings{HarshaHNRR2008,
        author =          {Prahladh Harsha and Thomas Hayes and Hariharan Narayanan
        and Harald Räcke and Jaikumar Radhakrishnan},
        booktitle =     {Proc.\ $19$th Annual {ACM}-{SIAM} Symp.\ on Discrete
                         Algorithms (SODA)},
        editor =        {Shang{-}Hua Teng},
        pages =         {200--207},
        title =         {Minimizing Average Latency in Oblivious Routing},
        year =          {2008},
        city =          {San Francisco, CA},
        date =          {20--22~Jan},
        doi =           {10.1145/1347082.1347105},
      }

    • [ pdf ]
48. The Communication Complexity of Correlation
    • Authors: Prahladh Harsha, Rahul Jain, David McAllester, and Jaikumar Radhakrishnan
    • In Proc. 22nd IEEE Conf. on Comput. Complexity (San Diego, CA, 13–16 June), pages 10–23, 2007. [BibTeX]
      ⧉ Copy

      @inproceedings{HarshaJMR2007,
        author =          {Prahladh Harsha and Rahul Jain and David McAllester and
        Jaikumar Radhakrishnan},
        booktitle =     {Proc.\ $22$nd IEEE Conf.\ on Comput.\ Complexity},
        editor =        {Peter Bro Miltersen},
        pages =         {10--23},
        title =         {The Communication Complexity of Correlation},
        year =          {2007},
        city =          {San Diego, CA},
        date =          {13--16~June},
        doi =           {10.1109/CCC.2007.32},
      }

    • IEEE Trans. Inform. Theory, 56(1):438–449, 2010. [BibTeX]
      ⧉ Copy

      @article{HarshaJMR2010,
        author =          {Prahladh Harsha and Rahul Jain and David McAllester and
        Jaikumar Radhakrishnan},
        journal =       {IEEE Trans.\ Inform.\ Theory},
        note =          {(Preliminary version in \emph{22nd {IEEE} Conference
                         on Computational Complexity}, 2007)},
        number =        {1},
        pages =         {438--449},
        title =         {The Communication Complexity of Correlation},
        volume =        {56},
        year =          {2010},
        doi =           {10.1109/TIT.2009.2034824},
      }

    • [ pdf ]
49. Short PCPs verifiable in polylogarithmic time
    • Authors: Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil Vadhan
    • In Proc. 20th IEEE Conf. on Comput. Complexity (San Jose, CA, 12–15 June), pages 120–134, 2005. [BibTeX]
      ⧉ Copy

      @inproceedings{BenSassonGHSV2005,
        author =          {Eli {Ben-Sasson} and Oded Goldreich and Prahladh Harsha
        and Madhu Sudan and Salil Vadhan},
        booktitle =     {Proc.\ $20$th IEEE Conf.\ on Comput.\ Complexity},
        editor =        {Luca Trevisan},
        note =          {Full version available at
        \url{http://www.tcs.tifr.res.in/~prahladh/papers/BGHSV2/BGHSV2005.pdf}},
        pages =         {120--134},
        title =         {Short {PCP}s verifiable in polylogarithmic time},
        year =          {2005},
        city =          {San Jose, CA},
        date =          {12--15~June},
        doi =           {10.1109/CCC.2005.27},
      }

    • [ pdf ]
50. Communication vs. Computation
    • Authors: Prahladh Harsha, Yuval Ishai, Joe Kilian, Kobbi Nissim, and Srinivasan Venkatesh
    • In Proc. 31st International Colloq. of Automata, Languages and Programming (ICALP) (Turku, Finland, 12–16 July), vol. 3142 of LNCS, pages 745–756, 2004. [BibTeX]
      ⧉ Copy

      @inproceedings{HarshaIKNV2004,
        author =          {Prahladh Harsha and Yuval Ishai and Joe Kilian and Kobbi
        Nissim and Srinivasan Venkatesh},
        booktitle =     {Proc.\ $31$st International Colloq.\ of Automata,
                         Languages and Programming (ICALP)},
        editor =          {Josep D\'{i}az and Juhani Karhum\"{a}ki and Arto
        Lepist\"{o} and Donald Sannella},
        pages =         {745--756},
        publisher =     {Springer},
        series =        {LNCS},
        title =         {Communication vs. Computation},
        volume =        {3142},
        year =          {2004},
        city =          {Turku, Finland},
        date =          {12--16~July},
        bibsource =     {DBLP, http://dblp.uni-trier.de},
        doi =           {10.1007/978-3-540-27836-8_63},
        isbn =          {3-540-22849-7},
      }

    • Comput. Complexity, 16(1):1–33, 2007. [BibTeX]
      ⧉ Copy

      @article{HarshaIKNV2007,
        author =          {Prahladh Harsha and Yuval Ishai and Joe Kilian and Kobbi
        Nissim and Srinivasan Venkatesh},
        journal =       {Comput.\ Complexity},
        note =          {(Preliminary version in \emph{31st ICALP}, 2004)},
        number =        {1},
        pages =         {1--33},
        publisher =     {Birkh\"{a}user Basel},
        title =         {Communication vs. Computation},
        volume =        {16},
        year =          {2007},
        doi =           {10.1007/s00037-007-0224-y},
      }

    • [ pdf ]
51. Robust PCPs of proximity, shorter PCPs and applications to coding
    • Authors: Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil Vadhan
    • In Proc. 36th ACM Symp. on Theory of Computing (STOC) (Chicago, IL, 13–15 June), pages 1–10, 2004. [BibTeX]
      ⧉ Copy

      @inproceedings{BenSassonGHSV2004,
        author =          {Eli {Ben-Sasson} and Oded Goldreich and Prahladh Harsha
        and Madhu Sudan and Salil Vadhan},
        booktitle =     {Proc.\ $36$th ACM Symp.\ on Theory of Computing
                         (STOC)},
        editor =        {L{\'{a}}szl{\'{o}} Babai},
        pages =         {1--10},
        title =         {Robust {PCP}s of Proximity, Shorter {PCP}s and
                         Applications to Coding},
        year =          {2004},
        city =          {Chicago, IL},
        date =          {13--15~June},
        doi =           {10.1145/1007352.1007361},
      }

    • SIAM J. Comput., 36(4):889–974, 2006. [BibTeX]
      ⧉ Copy

      @article{BenSassonGHSV2006-special,
        author =          {Eli {Ben-Sasson} and Oded Goldreich and Prahladh Harsha
        and Madhu Sudan and Salil Vadhan},
        journal =       {SIAM J. Comput.},
        note =          {(special issue on Randomness and Computation;
                         Preliminary version in \emph{36th STOC}, 2004)},
        number =        {4},
        pages =         {889--974},
        title =         {Robust {PCP}s of proximity, shorter {PCP}s and
                         applications to coding},
        volume =        {36},
        year =          {2006},
        doi =           {10.1137/S0097539705446810},
        eccc =          {2004/021},
      }

    • Invited paper to special issue on `Randomness and Computation'
    • [ eccc | pdf ]
52. Some 3CNF properties are hard to test
    • Authors: Eli Ben-Sasson, Prahladh Harsha, and Sofya Raskhodnikova
    • In Proc. 35th ACM Symp. on Theory of Computing (STOC) (San Diego, CA, 9–11 June), pages 345–354, 2003. [BibTeX]
      ⧉ Copy

      @inproceedings{BenSassonHR2003,
        author =          {Eli {Ben-Sasson} and Prahladh Harsha and Sofya
        Raskhodnikova},
        booktitle =     {Proc.\ $35$th ACM Symp.\ on Theory of Computing
                         (STOC)},
        editor =        {Lawrence L. Larmore and Michel X. Goemans},
        key =           {ACM},
        pages =         {345--354},
        title =         {Some {3CNF} properties are hard to test},
        year =          {2003},
        city =          {San Diego, CA},
        date =          {9--11~June},
        doi =           {10.1145/780542.780594},
      }

    • SIAM J. Comput., 35(1):1–21, 2005. [BibTeX]
      ⧉ Copy

      @article{BenSassonHR2005,
        author =          {Eli {Ben-Sasson} and Prahladh Harsha and Sofya
        Raskhodnikova},
        journal =       {SIAM J. Comput.},
        note =          {(Preliminary version in \emph{35th STOC}, 2003)},
        number =        {1},
        pages =         {1--21},
        title =         {Some {3CNF} properties are hard to test},
        volume =        {35},
        year =          {2005},
        doi =           {10.1137/S0097539704445445},
      }

    • [ pdf ]
53. Lower Bounds for Bounded Depth Frege Proofs via Buss-Pudl\'ak Games
    • Authors: Eli Ben-Sasson and Prahladh Harsha
    • ACM T. Comput. Log., 11(3):1–17, 2010. [BibTeX]
      ⧉ Copy

      @article{BenSassonH2010,
        author =        {Eli {Ben-Sasson} and Prahladh Harsha},
        journal =       {{ACM} T.\ Comput.\ Log.},
        number =        {3},
        pages =         {1--17},
        title =         {Lower Bounds for Bounded Depth {F}rege Proofs via
                         {B}uss-{P}udl{\'a}k Games},
        volume =        {11},
        year =          {2010},
        doi =           {10.1145/1740582.1740587},
        eccc =          {2003/004},
      }

    • [ eccc | pdf ]
54. Small PCPs with Low Query Complexity
    • Authors: Prahladh Harsha and Madhu Sudan
    • In Proc. 18th Annual Symp. on Theoretical Aspects of Comp. Science (STACS) (Dresden, Germany, 15–17 Feb), vol. 2010 of LNCS, pages 327–338, 2001. [BibTeX]
      ⧉ Copy

      @inproceedings{HarshaS2001,
        author =        {Prahladh Harsha and Madhu Sudan},
        booktitle =     {Proc.\ $18$th Annual Symp.\ on Theoretical Aspects of
                         Comp.\ Science (STACS)},
        editor =        {Afonso Ferreira and Horst Reichel},
        pages =         {327--338},
        publisher =     {Springer},
        series =        {LNCS},
        title =         {Small {PCP}s with Low Query Complexity},
        volume =        {2010},
        year =          {2001},
        city =          {Dresden, Germany},
        date =          {15--17~Feb},
        bibsource =     {DBLP, http://dblp.uni-trier.de},
        doi =           {10.1007/3-540-44693-1_29},
        isbn =          {3-540-41695-1},
      }

    • Comput. Complexity, 9(3–4):157–201, 2000. [BibTeX]
      ⧉ Copy

      @article{HarshaS2000,
        author =        {Prahladh Harsha and Madhu Sudan},
        journal =       {Comput.\ Complexity},
        month =         {Dec},
        note =          {(Preliminary version in \emph{18th STACS}, 2001)},
        number =        {3--4},
        pages =         {157--201},
        publisher =     {Birkh\"{a}user Verlag},
        title =         {Small {PCP}s with Low Query Complexity},
        volume =        {9},
        year =          {2000},
        doi =           {10.1007/PL00001606},
      }

    • [ pdf ]
55. Distributed Processing in Automata
    • Authors: Kamala Krithivasan, Sakthi Balan, and Prahladh Harsha
    • International Journal of Foundations of Computer Science, 10(4):443–463, 1999. [BibTeX]
      ⧉ Copy

      @article{KrithivasanBH1999,
        author =          {Kamala Krithivasan and Sakthi Balan and Prahladh Harsha},
        journal =       {International Journal of Foundations of Computer
                         Science},
        month =         {Dec},
        number =        {4},
        pages =         {443--463},
        publisher =     {World Scientific Publishing Company},
        title =         {Distributed Processing in Automata},
        volume =        {10},
        year =          {1999},
        doi =           {10.1142/S0129054199000319},
      }

    • [ pdf ]

1. Robust PCPs of Proximity and Shorter PCPs
   • Ph.D. Thesis, Massachusetts Institute of Technology, 2004.
   • Advisor: Prof. Madhu Sudan
   • [ url | html | BibTeX ]
     ⧉ Copy

     @phdthesis{Harsha2004,
       author =        {Prahladh Harsha},
       month =         {Sep},
       school =        {Massachusetts Institute of Technology},
       title =         {Robust {PCP}s of Proximity and Shorter {PCP}s},
       year =          {2004},
       advisor =       {Prof. Madhu Sudan},
       url =           {https://hdl.handle.net/1721.1/26720},
     }

2. Small PCPs with Low Query Complexity
   • Masters Thesis, Massachusetts Institute of Technology, 2000.
   • Advisor: Prof. Madhu Sudan
   • [ url | pdf | BibTeX ]
     ⧉ Copy

     @mastersthesis{Harsha2000,
       author =        {Prahladh Harsha},
       month =         {May},
       school =        {Massachusetts Institute of Technology},
       title =         {Small {PCP}s with Low Query Complexity},
       year =          {2000},
       advisor =       {Prof. Madhu Sudan},
       url =           {https://hdl.handle.net/1721.1/86448},
     }

3. Distributed-Automata and Simple Test Tube Systems
   • Undergraduate Thesis, Indian Institute of Technology, Madras (Chennai), 1998.
   • Advisor: Prof. Kamala Krithivasan
   • [ pdf | BibTeX ]
     ⧉ Copy

     @misc{Harsha1998,
       author =        {Prahladh Harsha},
       month =         {Aug},
       note =          {Undergraduate thesis, Indian Institute of Technology,
                        Madras (Chennai), May 1998},
       school =        {Indian Institute of Technology, Madras (Chennai)},
       title =         {Distributed-Automata and Simple Test Tube Systems},
       year =          {1998},
       advisor =       {Prof. Kamala Krithivasan},
     }

1. An exposition of recent list-size bounds of FRS Codes
   • Authors: Abhibhav Garg, Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, and Ashutosh Shankar
   • An exposition of Srivastava and Chen-Zhang's result on optimal list-size bounds for list-decoding FRS and univariate multiplicity codes
   • [ arXiv | eccc | BibTeX ]
     ⧉ Copy

     @unpublished{GargHKSS-listsize,
       author =          {Abhibhav Garg and Prahladh Harsha and Mrinal Kumar and
       Ramprasad Saptharishi and Ashutosh Shankar},
       note =          {(survey)},
       title =         {An exposition of recent list-size bounds of {FRS}
                        Codes},
       year =          {2025},
       eprint =        {2502.14358},
       eccc =          {2025/015},
     }

2. The Blooming of the c^3 LTC Flowers [Blogpost]
   • A post on the constant-query locally testable code construction due to Dinur, Evra, Livne, Lubotzky and Mozes; In Calvin Cafe: The Simons Institute Blog, September 2022.
   • [ url | BibTeX ]
     ⧉ Copy

     @misc{Harsha2022-ccube,
       author =        {Harsha, Prahladh},
       month =         {Sep},
       note =          {Calvin Café: The Simons Institute Blog},
       publisher =     {Simons Institute for the Theory of Computing},
       title =         {The Blooming of the $c^3$ {LTC} Flowers [Blogpost]},
       year =          {2022},
       url =           {https://blog.simons.berkeley.edu/2022/09/the-blooming-of-
                       the-c3-ltc-flowers/},
     }

3. Sampling Spanning Trees using HDXs
   • An exposition of the Anari-Liu-OveisGharan-Vinzant result on sampling of bases of matroid via HDXs, December 2021.
   • Original paper: Nima Anari and Kuikui Liu and Shayan Oveis-Gharan and Cynthia Vinzant, Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid, In STOC, pages 1-12. 2019.
   • [ pdf | BibTeX ]
     ⧉ Copy

     @misc{Harsha2021-alov,
       author =        {Prahladh Harsha},
       note =          {An exposition of the Anari-Liu-OveisGharan-Vinzant
                        result on sampling of bases of matroid via HDXs,
                        December 2021. [Original paper: Nima Anari and Kuikui
                        Liu and Shayan Oveis-Gharan and Cynthia Vinzant,
                        Log-concave polynomials II: high-dimensional walks
                        and an FPRAS for counting bases of a matroid, In
                        STOC, pages 1-12. 2019.]. pdf:
       https://www.tifr.res.in/~prahladh/teaching/2021-22/pseudorandom/notes/mat_sampling.pdf},
       title =         {Sampling Spanning Trees using {HDX}s},
     }

4. A note on the explicit constructions of tree codes over polylogarithmic-sized alphabet
   • Authors: Siddharth Bhandari and Prahladh Harsha
   • An exposition of Pudlak's and Cohen-Haeupler-Schulman's construction of binary tree codes over polylogarithmic-sized output
   • [ arXiv | eccc | BibTeX ]
     ⧉ Copy

     @unpublished{BhandariH-treecode,
       author =        {Siddharth Bhandari and Prahladh Harsha},
       note =          {(manuscript)},
       title =         {A note on the explicit constructions of tree codes
                        over polylogarithmic-sized alphabet},
       year =          {2020},
       eprint =        {2002.08231},
       eccc =          {2020/019},
     }

5. Research Vignette: The Many Dimensions of High-Dimensional Expanders [blogpost]
   • A post on the Simons Institute 2019 summer cluster on Error-Correcting Codes and High-Dimensional Expansion.; In Calvin Cafe: The Simons Institute Blog, June 2020.
   • [ url | BibTeX ]
     ⧉ Copy

     @misc{Harsha2020-hdx,
       author =        {Prahladh Harsha},
       month =         {June},
       note =          {Calvin Café: The Simons Institute Blog},
       publisher =     {Simons Institute for the Theory of Computing},
       title =         {Research Vignette: The Many Dimensions of
                        High-Dimensional Expanders [blogpost]},
       year =          {2020},
       url =           {https://blog.simons.berkeley.edu/2020/06/research-vignette-
                       the-many-dimensions-of-high-dimensional-expanders/},
     }

6. Locally Testable Codes [encyclopedia entry]
   • In Encyclopedia of Algorithms, pages 1-6. Springer, 2016.
   • [ BibTeX ]
     ⧉ Copy

     @incollection{Harsha2016-ltc,
       author =        {Prahladh Harsha},
       booktitle =     {Encyclopedia of Algorithms},
       editor =        {Kao, Ming-Yang},
       pages =         {1--6},
       publisher =     {Springer},
       title =         {Locally Testable Codes [encyclopedia entry]},
       year =          {2016},
       doi =           {10.1007/978-3-642-27848-8_707-1},
       isbn =          {978-3-642-27848-8},
     }

7. Limits of approximation algorithms: PCPs and unique games
   • Authors: Moses Charikar and Prahladh Harsha
   • Lecture notes of DIMACS tutorial at the DIMACS Center (July 20 - 21, 2009).
   • [ url | arXiv | BibTeX ]
     ⧉ Copy

     @misc{HarshaC2009-limits,
       author =        {Prahladh Harsha and Moses Charikar},
       note =          {(DIMACS Tutorial, July 20-21, 2009)},
       title =         {Limits of approximation algorithms: {PCP}s and unique
                        games},
       year =          {2009},
       eprint =        {1002.3864},
       url =           {https://dimacs.rutgers.edu/Workshops/Limits/},
     }

8. CS369E: Expanders in Computer Science (Stanford University, Spring 2005)
   • Authors: Cynthia Dwork and Prahladh Harsha
   • Lecture notes of course taught at Computer Science Department, Stanford University in Spring 2005.
   • [ url | pdf | BibTeX ]
     ⧉ Copy

     @misc{DworkH2005-expanders,
       author =        {Cynthia Dwork and Prahladh Harsha},
       note =          {A course on expanders at the {S}tandord {U}niversity,
                        Spring 2005},
       title =         {CS369E: Expanders in Computer Science},
       year =          {2005},
       url =           {https://www.tcs.tifr.res.in/~prahladh/teaching/05spring/},
     }