Dissertation and Thesis

Now showing 1 - 10 of 44

Fourier Sketching: A Property Testing Perspective
(Indian Statistical Institute, Kolkata, 2026-10-29) Roy, Manmatha
Fourier analysis of Boolean functions is a fundamental tool with far-reaching applications in complexity theory, learning theory, and cryptography. In many natural settings, functions of interest exhibit Fourier sparsity: they can be well approximated using only a small number of significant Fourier coefficients. In this thesis, we study Fourier-sparse Boolean functions from the perspective of property testing, where the goal is to infer global structural properties of an unknown function using only a small number of queries to its truth table, and where the efficiency of an algorithm is measured by its query complexity. Originating in the context of PCP constructions and later evolving into an independent area, property testing provides a natural lens for understanding the intrinsic complexity of combinatorial objects. Our first contribution provides a refined analysis of a sketching-by-hashing framework that operates directly in the Fourier domain. While such an approach was previously explored by Gopalan et al. (2011), we significantly strengthen its theoretical guarantees by deriving sharper structural bounds for the hashing process. As a consequence, we obtain a query-efficient local list-correction algorithm for the Hadamard code. This tool yields several applications, including query-efficient testers for distribution-free Fourier sparsity, testing membership in subclasses of Fourier-sparse boolean functions, linear isomorphism testing with respect to a known Boolean function, and sumset size estimation for set functions. All of these problems are well studied in learning theory, cryptography, and additive combinatorics. Our second contribution introduces a sketching-by-hashing framework based on subspace restrictions, operating in the input domain of Boolean functions. By analyzing how functions behave under random affine subspace restrictions, we establish several structural results that lead to improved algorithms for testing Fourier sparsity. The same framework enables estimation of the heaviest Fourier coefficient up to small additive error, with query complexity depending only on the desired accuracy. These problems are relevant across several areas of computer science. A Fourier sparsity tester, for instance, can serve as a preprocessing step for learning algorithms over Fourier-sparse function classes, validating whether an unknown function belongs to the target hypothesis class; the ability to estimate the heaviest Fourier coefficient, on the other hand, can be leveraged to design distinguishers for symmetric-key ciphers. Taken together, our work strengthens the connection between sketching-by-hashing techniques and the property testing of Fourier-sparse Boolean functions, and advances the understanding of query complexity for learning and testing in the Fourier domain. We expect the algorithmic techniques developed here to find further applications across many areas of computer science.
Algorithms for Feature Selection
(Indian Statistical Institute, Kolkata, 2022-12) Lall, Snehalika
With the advancement of science and technology, data has increased both in sam- ple size and dimension. Examples of high-dimensional data include genomic data, text data, image retrieval, bioinformatics, etc. One of the major problems in handling such data is that all the features are not equally important. Hence, fea- ture engineering, feature selection and feature reduction are considered important pre-processing tasks to discard redundant, irrelevant features while preserving the prominent features of the data as much as possible. Feature selection, in practice, often improves the accuracy of down-stream machine learning problems, including clustering and classification. In this thesis, we aim to devise some novel and robust feature selection mecha- nisms in diverse domains of applications with a special focus on high dimensional biological data such as gene expression and single cell transcriptomic data. We develop a series of feature selection techniques equipped with structure-aware data sampling at its core. We adopt several concepts from statistics (e.g. copula and its variant), information theory (entropy), and advanced machine learning domain (variational graph autoencoder, generative adversarial network, and its variant) to design the feature selection models for high dimensional and noisy data. The proposed models perform extremely well both in supervised and unsu- pervised cases, even if the sample size is very low. Important outcomes from all the proposed methods are discussed in chapters. Moreover, an overall discussion about the applicability along with a brief mention of the shortcomings of all the discussed methods is provided. Some suggestions and guidance are provided to overcome the disadvantages which direct the future scope of improvement of all the devised methods.
Improved SIMD implementation of poly1305
(Indian Statistical Institute, Kolkata, 2018) Bhattacharyya, Sreyosi
On a class of board games
(Indian Statistical Institute, Kolkata, 2018) Manaswi
Sparse fuzzy switching regression model
(Indian Statistical Institute, Kolkata, 2016) Majumder, Biswajit
A transportation scheduling algorithm
(Indian Statistical Institute, Kolkata, 2016) Bhattacharjee, Arghya
Algorithms and bounds in online learning
(Indian Statistical Institute, Kolkata, 2016) Sharma, Ankit
Critical point analysis of the modified particle swarm optimization model
(Indian Statistical Institute, Kolkata, 2015) Pal, Arindam
Facility location on spherical surfaces
(Indian Statistical Institute, Kolkata, 2015) Dev, Subhadeep R
Large scale hierarchical text classification
(Indian Statistical Institute, Kolkata, 2013) Saha, Sourab

Dissertation and Thesis

Browse

Filters

Settings

Sort By

Results per page

Search Results