Finding explicit polynomials that require circuits of super-polynomial size is a major open question in algebraic complexity. Over the years, this question has seen significant progress in various structured settings, but this has not translated into lower bounds for circuits, where the state-of-the-art remains to be Omega(n log n). This has led to some works (e.g. Forbes, Shpilka and Volk (2018)) that investigate whether algebraic circuit lower bounds admit a "barrier" similar to the boolean setting.
The closely related question of blackbox identity testing, asks for a deterministic query algorithm that determines if the circuit being queried computes the "unsatisfiable" zero polynomial. Here again, the state-of-the-art for circuits remains to be a trivial, exponential-time algorithm.
In this talk, we will first see how the above two questions are connected. I will then describe some of my works that utilize these connections to throw some light on the questions themselves. In particular, these works use hardness-randomness connections to reveal a "threshold behaviour" of identity testing, and gather some insights into the "barrier question".
TCS Seminar | Alladi Ramakrishnan Hall
Apr 22 14:00-15:00
Jyotsana Jewel Parmar | NCBS Bangalore / University of Warwick, UK
Chromatin carries genetic information and is made of long polymers of DNA-protein
assemblies compacted at different levels and enclosed inside the nucleus. Apart from
functioning as the information bearer, chromatin also integrates external signals and
regulates the manifestation of this information. It has been shown by various studies that
chromatin organization is dynamic, however, shows several non-random features which are
driven by both active and passive components. Different regulatory processes e.g.,
chromatin remodelling, transcription activation and silencing, DNA repair etc., modify the 3D-
genome organization. In this work, I will study how these dynamic processes which act
locally, at nucleosome/gene level, would affect the overall global chromatin organization. My
approach will be to integrate active mechanics and polymer-physics based models with
experimental data obtained from sequencing (such as Hi-C and ChIP-seq) and imaging
techniques.
After more than a decade following the Higgs boson discovery, the LHC is set for two more decades of operations, during which it will also evolve into a precision machine. With this, the Effective Field Theory (EFT) is becoming prevalent in interpreting the high-energy interactions. In this talk, we will discuss the role played by the indirect deviations in Higgs couplings for the new non-resonant effects in the quest of heavy new physics. We will focus on the possible signatures of new interactions of the Higgs with the electroweak sector and the light quarks via various Higgs production channels in the Standard Model EFT framework. We highlight the potential of constraining such new interactions at the LHC. At the same time, we can also have signals of new physics where they can be
produced in presence of new light particles, such as Axion-Like Particles (ALPs). We will discuss an EFT which extends the SM by an ALP and mainly focus on the interactions of ALPs to heavy SM particles. We look for ALP signals when the ALP is kinematically too light to be on-shell and discuss the probes for these ALP interactions in the high energy regime at the LHC.