CS Events

Qualifying Exam Circuit satisfiability: Geometric insights and polynomial threshold functions
Export Event Save iCal Send to Google Calendar Send to Yahoo Calendar Send to Outlook Live Send to Microsoft Outlook Save iCal Preserve formatting in description (only supported in some calendar applications) Close Wednesday, April 23, 2025, 01:00pm - 03:00pm

Speaker: Adarsh Srinivasan

Location : CoRE 301

Committee: 

Assistant Professor Karthik Srikanta

Professor Michael Saks

Assistant Professor Sumegha Garg

Associate Professor Amélie Marian

Event Type: Qualifying Exam

Abstract: A fundamental question in theoretical computer science iswhether we can improve over exhaustive search for NP-completeproblems. Of these, the circuit satisfiability problem (Circuit-SAT)holds particular importance, as even modest improvements forrestricted circuit classes yield significant insights intocomputational complexity theory. In this talk, I will present somerecent progress on two frontiers of circuit satisfiability.Geometric properties of k-SAT: We develop algorithms that computegeometric properties of the set of satisfying assignments for k-CNFformulas (CNF formulas of width k). By re-analyzing the classical PPZand Schöning algorithms for k-SAT, we achieve running times comparableto state-of-the-art k-SAT solvers.Cubic threshold functions and probabilistic rank: Threshold circuits,where each gate computes a threshold function, are a powerful class ofboolean circuits with connections to neural networks and physicalcomputing models. Using the technique of probabilistic rank, we derivenew satisfiability algorithms and lower bounds for circuits withpolynomial threshold functions of degree 3 as gates.Publications: 1) https://arxiv.org/abs/2305.028502) https://www.arxiv.org/abs/2408.03465

: 

Contact  Assistant Professor Karthik Srikanta

Zoom: https://rutgers.zoom.us/my/as4100?pwd=dzJpa252THhLNlNFbG00ZlZwcXBJUT09