BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Computer Science and Engineering - ECPv6.13.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Computer Science and Engineering
X-ORIGINAL-URL:https://homecse.iitd.ac.in
X-WR-CALDESC:Events for Computer Science and Engineering
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Kolkata
BEGIN:STANDARD
TZOFFSETFROM:+0530
TZOFFSETTO:+0530
TZNAME:IST
DTSTART:20250101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Kolkata:20251013T120000
DTEND;TZID=Asia/Kolkata:20251013T130000
DTSTAMP:20261012T013009
CREATED:20251007T162719Z
LAST-MODIFIED:20251007T162719Z
UID:2088-1760356800-1760360400@homecse.iitd.ac.in
SUMMARY:Frontiers in Boolean Circuit Lower Bounds by Dr. Vaibhav Krishan
DESCRIPTION:Venue: Bharti501 \nAbstract:\nBoolean circuits provide a combinatorial representation of computation\, where the number of gates (the size) represents running time\, and the number of layers (the depth) capture parallel running time.\nThey form a framework for answering fundamental questions such as P vs NP: proving that some NP problem requires circuits of superpolynomial size would separate P from NP. \nWith limited progress on this question for general circuits\, early breakthroughs focused on restricted circuit classes.\nHåstad (STOC `86) proved that constant-depth circuits with AND\, OR\, and NOT gates require exponential size to compute the parity function (which determines whether the sum of inputs is even or odd).\nRazborov (Matematicheskie Zametki `87) and\, independently\, Smolensky (STOC `87)\, extended this to circuits augmented with parity or modular gates (for prime moduli)\, showing that such circuits require exponential size to compute the majority function (which determines whether the sum of inputs is at least half their number). \nFollowing these foundational results\, research has advanced along two principal directions\, though further progress has become increasingly challenging.\nIn this talk\, I will present some of my work contributing new advances at the frontier of both directions. \n______________________________________________________________________________________________________________________________________ \nPart I: Threshold Circuits. \nThe first part of the talk will focus on constant-depth threshold circuits\, circuits that can use majority gates\, or more generally\, threshold gates.\nThreshold gates can be seen as a simple abstraction for neurons\, and threshold circuits were among the earliest models studied to understand the computational power of neural networks.\nThese circuits are quite powerful; for instance\, they can efficiently implement integer arithmetic operations such as exponentiation and square root. \nIn joint work with Bajpai\, Kush\, Limaye\, and Srinivasan\, Algorithmica `21\, we study a generalization of threshold circuits\, called polynomial threshold circuits\, that use polynomial threshold gates.\nA polynomial threshold gate outputs a Boolean value based on the sign of a polynomial evaluated over the inputs.\nWe design an algorithm to count the number of assignments on which a polynomial threshold circuit outputs 1.\nFor any constant depth\, our algorithm runs faster-than-brute-force when the circuit size is slightly superlinear and the degree of each gate is bounded by a constant.\nPrior to our work\, no such algorithm was known even for a single polynomial threshold gate\, except in the special case of degree 2.\nFaster-than-brute-force algorithms are known to imply circuit lower bounds (Williams\, JACM `14)\, although the particular lower bounds implied by our work were already established by Kane\, Kabanets\, and Lu (STOC `17). \nOur work builds on a long line of research initiated by Impagliazzo\, Paturi\, and Saks (SIAM J. Comput. `97)\, who proved a tight lower bound for threshold circuits with a slightly superlinear number of wires computing the parity function.\nTheir core idea\, simplification of threshold circuits under random partial assignments\, has inspired a series of influential results\, leading to average-case lower bounds and satisfiability algorithms (Chen\, Santhanam\, and Srinivasan\, Theory Comput. `18)\, as well as pseudorandom generator constructions (Hatami\, Hoza\, Tal\, and Tell\, FOCS `22).\nEven seemingly small improvements to these results could lead to major breakthroughs in circuit complexity (Chen and Tell\, STOC `19)\, marking a central frontier for the community. \n______________________________________________________________________________________________________________________________________ \nPart II: Modular Circuits \nThe second part of my talk will focus on circuits with modular gates for general (not necessarily prime) moduli.\nHere\, in a joint work with S. Vishwanathan\, we develop an approach toward resolving a long-standing conjecture (Barrington\, JCSS `89)\, that constant-depth circuits with modular gates (the modulus does not grow with input size) require superpolynomial size to compute the majority function.\nThe classical lower-bound techniques of Håstad and Razborov-Smolensky fail to extend to this setting\, while the algorithms-to-lower bounds framework of Williams (JACM `14) does not apply to simple functions such as majority\, making new ideas necessary. \nVarious approaches to this conjecture have been proposed over the years.\nIn earlier work (Krishan\, CSR 2019)\, I showed that torus polynomials provide the most refined framework for tackling this problem.\nTorus polynomials were introduced by Bhrushundi\, Hosseini\, Lovett\, and Rao (ITCS `19) for proving lower bounds against such modular circuits.\nUsing torus polynomials\, we translate the lower bound conjecture to the task of finding feasible solutions to an infinite family of linear programs.\nThis reformulation allows for incremental progress\, by finding solutions for progressively larger sets from the family. \nWe find solutions for almost all of these programs\, leaving only a finite set unresolved.\nFinding feasible solutions for the remaining cases would lead to a resolution of the conjecture.\nTo make this task more tractable\, we show that the family of programs has far fewer degrees of freedom than initially expected\, and we describe a potential set of feasible solutions for some of the remaining cases.\nI will conclude the talk with open problems and directions for future progress. \n  \nBio: Vaibhav is a postdoctoral researcher at The Institute of Mathematical Sciences\, Chennai. He completed his Ph.D. at IIT Bombay under the supervision of Prof. Sundar Vishwanathan and Prof. Nutan Limaye. Before beginning his Ph.D.\, he worked as a quantitative researcher and a data scientist for four years.
URL:https://homecse.iitd.ac.in/event/frontiers-in-boolean-circuit-lower-bounds-by-dr-vaibhav-krishan/
LOCATION:Bharti 501\, IIT Campus\, Hauz Khas\, New Delhi
END:VEVENT
END:VCALENDAR