Please use this identifier to cite or link to this item: http://hdl.handle.net/10263/7473
Full metadata record
DC FieldValueLanguage
dc.contributor.authorKayal, Chandrima-
dc.date.accessioned2024-11-12T12:09:11Z-
dc.date.available2024-11-12T12:09:11Z-
dc.date.issued2024-05-
dc.identifier.citation202p.en_US
dc.identifier.urihttp://hdl.handle.net/10263/7473-
dc.descriptionThis thesis is under the supervision of Prof.Sourav Chakrabortyen_US
dc.description.abstractBoolean functions are one of the central objects in the study of Computer Science. Any decision problem can be expressed as a Boolean function that takes an $n$-bit string as input and gives a single-bit output. Its versatility in capturing various problems in a simple form makes it crucial to understand the different properties of Boolean functions. There are various aspects to understanding Boolean functions. In this thesis, we will be focusing on the study of Boolean functions using the query complexity model. Various complexity measures are motivated and generated from the query complexity world, for example, Deterministic query complexity, Randomized query complexity, Quantum query complexity, sensitivity, block sensitivity, and many more. Investigating the interplay among these measures has been an active area of research in computational complexity theory for over three decades, with implications reaching across different areas of theoretical computer science. Exploring specialized classes of Boolean functions enhances our understanding of their inherent complexities. Analyzing complexity measures within specific function classes illuminates broader patterns and aids in identifying critical properties essential for general study. Among these classes, those characterized by complete symmetry have gotten significant attention for their widespread applicability across diverse domains. Symmetry, as a defining property, influences the behavior of Boolean functions. While 'Symmetric Boolean functions' that is the Boolean functions that are invariant under any permutation of the input string, have undergone extensive study and are nearly well understood, functions exhibiting partial symmetry remain less understood. Our investigation navigates through the landscape of partial symmetry, focusing on the following: 1. UNDERSTANDING THE IMPACT OF PARTIAL SYMMETRY ON COMBINATORIAL MEASURES: Examining the relationship between various combinatorial measures and their behavior under partial symmetry. Precisely, we prove separation results for the classes of transitive functions. 2. EXPLORING COMPLEXITY MEASURES UNDER FUNCTION COMPOSITION: In particular, two big open problems in this area are that it is not known how randomized query complexity and approximate degree behave under composition. We made some progress towards the main open problems as well, and we have proved the composition theorem for both the complexity measures for the functions with partial symmetry.en_US
dc.language.isoenen_US
dc.publisherIndian Statistical Institute, Kolkataen_US
dc.relation.ispartofseriesISI Ph. D Thesis;TH-
dc.subjectBoolean functionsen_US
dc.subjectCombinatorial complexityen_US
dc.subjectComputer Scienceen_US
dc.subjectComplexity Measuresen_US
dc.titleEffects of symmetry in combinatorial complexity measures of Boolean functionsen_US
dc.typeThesisen_US
Appears in Collections:Theses

Files in This Item:
File Description SizeFormat 
Thesis__Chandrima_ 30-10-24.pdfThesis1.15 MBAdobe PDFView/Open
Form 17-Chandrima Kayal-12-11-24.pdfForm 1784.83 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.