The past two decades have witnessed dramatic improvements in SAT
solving, enabling today's solvers to handle problems involving
millions of variables. Motivated by the power of SAT solvers, there is
a growing interest in tackling problems that lie in higher classes of
the polynomial hierarchy, wherein NP calls are to be replaced by SAT
solvers in practice. The complexity of such algorithms is measured in
terms of calls to NP oracles. However, SAT solvers are not mere
decision oracles: they also provide a satisfying assignment when the
formula is satisfiable. Therefore, a theory based on NP oracles is
limiting, and there is a need for a theory that takes into account the
power of SAT solvers. In this talk, I will discuss how such
consideration leads to new algorithms and new lower bounds in the
context of two fundamental problems: model counting and sampling.
Based on joint work (LICS-22 and ICALP-23) with Diptarka Chakaraborty,
Sourav Chakraborty, Remi Delannoy, and Gunjan Kumar
We give a complete description of the eigenvalues of all permutations in irreducible representations of symmetric and alternating groups.
(This talk is the speaker's pre-synopsis seminar)
Scattering amplitudes are the cornerstones of our current understanding of quantum field theories. On-shell methods offer efficient ways to calculate amplitudes in some theories and uncover beautiful structures usually obscured by the Feynman diagrammatics. The planar maximal supersymmetric (N=4) gauge theory is well suited for the use of on-shell methods, and the amplitudes have a positive geometry description in terms of the amplituhedron. We discuss the spontaneously symmetry broken N=4 super Yang-Mills theory and pure gauge theory in this talk. We study the so-called `on-shell functions' in the massive N=4 SYM, and realize the massive BCFW shifts as on-shell diagrams. We stumble upon mass deforming BCFW shifts. We discuss the maximal cut of simple loop diagrams and, using the generalized unitarity, find the loop amplitudes in massive N=4 SYM. In the second part of the talk, we discuss the pure gauge theory and realize its amplitudes from the positive geometry and combinatorics. The associahedron is a combinatorial object capturing the combinatorics of triangulations of an n-gon, and hence planar trivalent graphs. We make use of the Corolla polynomials to spin up the canonical form of the associahedron, yielding the gluon amplitudes. The similar Corolla polynomials for one loop lead us to the loop integrand of the n-gluon scattering. We use another representation of the Corolla polynomial to spin up the recently discovered curve integral formula.
Zoom link:
https://zoom.us/j/94529679427
Meeting ID: 945 2967 9427
Passcode: 661437