(Talk will be in-person. Zoom link for remote attendance --
https://zoom.us/j/92557905378
Meeting ID: 925 5790 5378
Passcode: 057022)
Nisan's classic result [SICOMP '91] shows that the randomized decision tree depth complexity of a total Boolean function is at least the cube of its deterministic decision tree depth complexity. However, the role of randomness on decision tree size complexity has not been explored. Adding to Nisan's result, we show that the logarithm of the deterministic decision tree size complexity of any total Boolean function is at most the fourth power of the logarithm of its bounded-error randomized decision tree size complexity, up to a polylogarithmic factor in the input dimension. Drawing an analogy, one can associate the depth of a decision tree with time complexity and its size with space complexity. Consequently, Nisan's result can be viewed as derandomizing time, while our result can be seen as derandomizing space. Our result has several implications for derandomizing query complexity in more generalized variants of decision trees. Specifically, we show that for total Boolean functions
1. The deterministic AND-OR query complexity is at most the fourth power of its randomized counterpart, ignoring a polylog n factor.
2. The deterministic AND (OR) query complexity is at most the cube of its randomized counterpart, ignoring a polylog n factor. This resolves an open question by Knop, Lovett, McGuire, and Yuan [SIGACT News '21].
Combining our result with Ehrenfeucht and Haussler's [Information and Computation'89] work, we also get that the class of functions computable by randomized decision trees of polynomial size is PAC-learnable in quasi-polynomial time. To obtain our main result on decision tree size, we use as an intermediate measure the block number of a Boolean function, studied first by Kulkarni and Tal [CJTCS'16], which can be thought of as a counting analogue of block sensitivity of a Boolean function that played a central role in Nisan's aforementioned result.
Joint work with Arkadev Chattopadhyay, Nikhil Mande, Jaikumar Radhakrishnan, and Swagato Sanyal.
To appear in STOC 2023.
TCS Seminar | Alladi Ramakrishnan Hall
Jun 09 15:30-17:00
Ankur Sarkar | IMSc
Smooth Structures on the product of a manifold with a standard sphere
Mathematics Seminar | Alladi Ramakrishnan Hall
Jun 14 15:30-16:30
Madhulika Dixit | Department of Biotechnology, IIT Madras
Daily and optimal trafficking of circulating leukocytes from bone marrow to peripheral organs and back is paramount for immunity, tissue repair and homeostasis. In addition to the circadian control, the temporal and spatial redistribution of naïve lymphocytes as well as their functionality is intricately linked to whole body metabolism. This is evident from the fact that metabolic aberrations as seen during diabetes and obesity is strongly associated with chronic inflammation and consequent cardiovascular complications. Despite being the early responders to biochemical changes in blood, and being periodically exposed to altering levels of glucose and insulin upon fasting and feeding, it is unclear if feeding induced biochemical changes in blood have any impact on trafficking of circulating lymphocytes. In a recent study conducted on healthy men, we observed that oral feeding following over-night fasting, enhances the adhesive properties of quiescent circulating lymphocytes, in order to mediate their homing to injured blood vessels through a mechanism involving non-canonical insulin signalling. Intriguingly, the adhesive property of circulating lymphocytes was found to be compromised in individuals exhibiting impaired glucose metabolism. My talk will summarize our recent findings in this regard.
Biomolecular condensates are membrane-less organelles found in cells. The current understanding is that the phase separation of proteins and nucleic acids leads to the formation of these organelles. Oftentimes, the condensates also contain internal structures. With the help of a simple model system consisting of a polymer as a model for nucleic acid and interacting spherical particles(binders) as a model for proteins, we show that both the protein-DNA interactions and protein-protein interactions can play a role in determining the internal organization of the condensate. In particular, we observe a layered organization of the condensate when the polymer consists of two blocks, one half with a stronger affinity for the binders than the other half. I will end the discussion by stating the possible biological consequences of layered organization.
Join Zoom Meeting
https://zoom.us/j/93256759063
Meeting ID: 932 5675 9063
Passcode: 052624
Plants constantly interact with different biotic and abiotic factors in their environment. Herbivore insects are one of the common biotic interactors. Since insect herbivores cause damage, plants use defense strategies against these herbivores. In response, the insect herbivores evolve counter-defense strategies. This race towards one-upmanship is constantly on in the nature, so it is popularly called as an ‘evolutionary arms race’. Since most of these defense and counter-defense are chemically based, they are also considered to be a part of the ‘biochemical warfare’ between plants and insects. Insect herbivore's natural enemies like parasitoids, predators, pathogens, etc. add another dimension to this interaction and make it 'tritrophic'. In ecological terms, plants exert a bottom-up force by using defense chemicals, natural enemies exert a top-down force on the insect herbivores. From the agricultural viewpoint, herbivores are pests, plants' defense chemicals are biopesticides, and the natural enemies are the biocontrol agents. We integrate the classical ecological, and modern omics methods like genomics, transcriptomics and metabolomics to study these interactions and find agriculturally important solutions. In my seminar, I will discuss some of the interesting biochemical warfare strategies and how understanding these strategies can help our insect-pest management programs in agriculture.