CAREER: New Approaches to Analytical and Combinatorial Problems in Computer Science

Modern life depends on the ability to solve large and complicated problems involving networks, decisions, and hidden patterns in data. Examples include moving goods efficiently through supply chains, routing information across communication systems, and identifying meaningful structure in large collections of data. This project develops new mathematical tools for solving such problems more effectively. One part of the work focuses on improving methods for planning and optimization in networks, with possible long-term relevance for logistics, telecommunications, and artificial intelligence. Another part asks when weak or indirect patterns in complex data can still reveal useful underlying structure, a question that matters for the foundations of computing and data analysis. The project also supports education and workforce development through course design, student mentoring, workshops, summer schools, and outreach activities that help bring advanced ideas in mathematics and computer science to a broader group of learners. At a technical level, the project studies how combinatorial and analytic techniques can be brought together to make progress on open problems in algorithms and complexity theory. On the optimization side, the research develops new interior point method frameworks for minimum-cost flow and related graph problems, with the goals of lowering iteration complexity, extending nearly linear-time methods to broader graph settings, and designing dynamic data structures for tasks such as incremental and decremental shortest paths and cycle detection. These dynamic tools may also lead to faster algorithms for static problems, including matching and flow problems. On the analytic side, the project investigates correlations in high-dimensional functions and constraint satisfaction problems, aiming to prove new inverse theorems for larger-arity settings and to apply them in areas such as property testing, approximation, multiplayer games, communication complexity, and additive combinatorics. A further direction studies combinatorial patterns such as longer combinatorial lines, seeking stronger bounds through new structural and higher-order analytic methods. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria. NSF Award ID: 2542272 | Program: 01003031DB NSF RESEARCH & RELATED ACTIVIT,01002627DB NSF RESEARCH & RELATED ACTIVIT,01002930DB NSF RESEARCH & RELATED ACTIVIT | Principal Investigator: Yang Liu | Institution: Carnegie Mellon University, PITTSBURGH, PA | Award Amount: $331,723 View on NSF Award Search: https://www.nsf.gov/awardsearch/show-award/?AWD_ID=2542272 View on Research.gov: https://www.research.gov/awardapi-service/v1/awards/2542272.html