| 2023 | ICALP | Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions. | Ishan Bansal, Joseph Cheriyan, Logan Grout, Sharat Ibrahimpur |
| 2021 | ISAAC | An Improved Approximation Algorithm for the Matching Augmentation Problem. | Joseph Cheriyan, Robert Cummings, Jack Dippel, Jasper Zhu |
| 2013 | FOCS | Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs. | Joseph Cheriyan, Lszl A. Vgh |
| 2013 | ICALP | On Integrality Ratios for Asymmetric TSP in the Sherali-Adams Hierarchy. | Joseph Cheriyan, Zhihan Gao, Konstantinos Georgiou, Sahil Singla |
| 2012 | SODA | Approximating rooted Steiner networks. | Joseph Cheriyan, Bundit Laekhanukit, Guyslain Naves, Adrian Vetta |
| 2005 | SODA | An O(VE) algorithm for ear decompositions of matching-covered graphs. | Marcelo Henriques de Carvalho, Joseph Cheriyan |
| 2005 | STOC | Approximation algorithms for network design with metric costs. | Joseph Cheriyan, Adrian Vetta |
| 2004 | ESA | Hardness and Approximation Results for Packing Steiner Trees. | Joseph Cheriyan, Mohammad R. Salavatipour |
| 2002 | STOC | Approximation algorithms for minimum-cost k-vertex connected subgraphs. | Joseph Cheriyan, Santosh S. Vempala, Adrian Vetta |
| 2001 | FOCS | Approximating Directed Multicuts. | Joseph Cheriyan, Howard J. Karloff, Yuval Rabani |
| 2001 | IPCO | Edge Covers of Setpairs and the Iterative Rounding Method. | Joseph Cheriyan, Santosh S. Vempala |
| 1999 | ESA | On 2-Coverings and 2-Packings of Laminar Families. | Joseph Cheriyan, Tibor Jordn, R. Ravi |
| 1998 | IPCO | An Improved Approximation Algorithm for Minimum Size 2-Edge Connected Spanning Subgraphs. | Joseph Cheriyan, Andrs Seb, Zoltn Szigeti |
| 1997 | SODA | Buy-at-Bulk Network Design: Approximating the Single-Sink Edge Installation Problem. | F. Sibel Salman, Joseph Cheriyan, R. Ravi, S. Subramanian |
| 1996 | FOCS | Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching (extended abstract). | Joseph Cheriyan, Ramakrishna Thurimella |
| 1996 | STOC | Fast Algorithms for | Joseph Cheriyan, Ramakrishna Thurimella |
| 1995 | ESA | Approximation Algorithms for Feasible Cut and Multicut Problems. | Bo Yu, Joseph Cheriyan |
| 1994 | SODA | A Las Vegas O(n | Joseph Cheriyan |
| 1993 | SODA | Random Weighted Laplacians, Lovsz Minimum Digraphs and Finding Minimum Separators. | Joseph Cheriyan |
| 1993 | SPAA | Parallel and Output Sensitive Algorithms for Combinatorial and Linear Algebra Problems. | Joseph Cheriyan, John H. Reif |
| 1992 | SODA | Directed | Joseph Cheriyan, John H. Reif |
| 1991 | STOC | Algorithms for Parallel k-Vertex Connectivity and Sparse Certificates (Extended Abstract) | Joseph Cheriyan, Ramakrishna Thurimella |
| 1990 | ICALP | Can A Maximum Flow be Computed on o(nm) Time? | Joseph Cheriyan, Torben Hagerup, Kurt Mehlhorn |
| 1989 | FOCS | A Randomized Maximum-Flow Algorithm | Joseph Cheriyan, Torben Hagerup |