25 research outputs found
A No-Go Theorem for Derandomized Parallel Repetition: Beyond Feige-Kilian
No full textIn this work we show a barrier towards proving a randomness-efficient parallel repetition, a promising avenue for achieving many tight inapproximability results. Feige and Kilian (STOC'95) proved an impossibility result for randomness-efficient parallel repetition for two prover games with small degree, i.e., when each prover has only few possibilities for the question of the other prover. In recent years, there have been indications that randomness-efficient parallel repetition (also called derandomized parallel repetition) might be possible for games with large degree, circumventing the impossibility result of Feige and Kilian. In particular, Dinur and Meir (CCC'11) construct games with large degree whose repetition can be derandomized using a theorem of Impagliazzo, Kabanets and Wigderson (SICOMP'12). However, obtaining derandomized parallel repetition theorems that would yield optimal inapproximability results has remained elusive.
This paper presents an explanation for the current impasse in progress, by proving a limitation on derandomized parallel repetition. We formalize two properties which we call "fortification-friendliness" and "yields robust embeddings". We show that any proof of derandomized parallel repetition achieving almost-linear blow-up cannot both (a) be fortification-friendly and (b) yield robust embeddings. Unlike Feige and Kilian, we do not require the small degree assumption.
Given that virtually all existing proofs of parallel repetition, including the derandomized parallel repetition result of Dinur and Meir, share these two properties, our no-go theorem highlights a major barrier to achieving almost-linear derandomized parallel repetition
Relaxed Locally Correctable Codes
No full textLocally decodable codes (LDCs) and locally correctable codes (LCCs) are error-correcting codes in which individual bits of the message and codeword, respectively, can be recovered by querying only few bits from a noisy codeword. These codes have found numerous applications both in theory and in practice.
A natural relaxation of LDCs, introduced by Ben-Sasson et al. (SICOMP, 2006), allows the decoder to reject (i.e., refuse to answer) in case it detects that the codeword is corrupt. They call such a decoder a relaxed decoder and construct a constant-query relaxed LDC with almost-linear blocklength, which is sub-exponentially better than what is known for (full-fledged) LDCs in the constant-query regime.
We consider an analogous relaxation for local correction. Thus, a relaxed local corrector reads only few bits from a (possibly) corrupt codeword and either recovers the desired bit of the codeword, or rejects in case it detects a corruption.
We give two constructions of relaxed LCCs in two regimes, where the first optimizes the query complexity and the second optimizes the rate:
1. Constant Query Complexity: A relaxed LCC with polynomial blocklength whose corrector only reads a constant number of bits of the codeword. This is a sub-exponential improvement over the best constant query (full-fledged) LCCs that are known.
2. Constant Rate: A relaxed LCC with constant rate (i.e., linear blocklength) with quasi-polylogarithmic query complexity. This is a nearly sub-exponential improvement over the query complexity of a recent (full-fledged) constant-rate LCC of Kopparty et al. (STOC, 2016)
Being Corrupt Requires Being Clever, But Detecting Corruption Doesn't
No full textWe consider a variation of the problem of corruption detection on networks posed by Alon, Mossel, and Pemantle '15. In this model, each vertex of a graph can be either truthful or corrupt. Each vertex reports about the types (truthful or corrupt) of all its neighbors to a central agency, where truthful nodes report the true types they see and corrupt nodes report adversarially. The central agency aggregates these reports and attempts to find a single truthful node. Inspired by real auditing networks, we pose our problem for arbitrary graphs and consider corruption through a computational lens. We identify a key combinatorial parameter of the graph m(G), which is the minimal number of corrupted agents needed to prevent the central agency from identifying a single corrupt node. We give an efficient (in fact, linear time) algorithm for the central agency to identify a truthful node that is successful whenever the number of corrupt nodes is less than m(G)/2. On the other hand, we prove that for any constant alpha > 1, it is NP-hard to find a subset of nodes S in G such that corrupting S prevents the central agency from finding one truthful node and |S| <= alpha m(G), assuming the Small Set Expansion Hypothesis (Raghavendra and Steurer, STOC '10). We conclude that being corrupt requires being clever, while detecting corruption does not.
Our main technical insight is a relation between the minimum number of corrupt nodes required to hide all truthful nodes and a certain notion of vertex separability for the underlying graph. Additionally, this insight lets us design an efficient algorithm for a corrupt party to decide which graphs require the fewest corrupted nodes, up to a multiplicative factor of O(log n)
A no-go theorem for derandomized parallel repetition
No full textThesis: S.M. in Computer Science and Engineering, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016.Cataloged from PDF version of thesis.Includes bibliographical references (pages 45-46).In this work we show a barrier towards proving a randomness-efficient parallel repetition, a promising avenue for achieving many tight inapproximability results. Feige and Kilian (STOC'95) proved an impossibility result for randomnessefficient parallel repetition for two prover games with small degree, i.e., when each prover has only few possibilities for the question of the other prover. In recent years, there have been indications that randomness-efficient parallel repetition (also called derandomized parallel repetition) might be possible for games with large degree, circumventing the impossibility result of Feige and Kilian. In particular, Dinur and Meir (CCC'11) construct games with large degree whose repetition can be derandomized using a theorem of Impagliazzo, Kabanets and Wigderson (SICOMP'12). However, obtaining derandomized parallel repetition theorems that would yield optimal inapproximability results has remained elusive. This paper presents an explanation for the current impasse in progress, by proving a limitation on derandomized parallel repetition. We formalize two properties which we call "fortification-friendliness" and "yields robust embeddings". We show that any proof of derandomized parallel repetition achieving almost-linear blow-up cannot both (a) be fortification-friendly and (b) yield robust embeddings. Unlike Feige and Kilian, we do not require the small degree assumption. Given that virtually all existing proofs of parallel repetition share these two properties, our no-go theorem highlights a major barrier to achieving almostlinear derandomized parallel repetition.by Govind Ramnarayan.S.M. in Computer Science and Engineerin
Distributed computation and inference
No full textThesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, May, 2020Cataloged from the official PDF of thesis.Includes bibliographical references (pages 319-331).In this thesis, we explore questions in algorithms and inference on distributed data. On the algorithmic side, we give a computationally efficient algorithm that allows parties to execute distributed computations in the presence of adversarial noise. This work falls into the framework of interactive coding, which is an extension of error correcting codes to interactive settings commonly found in theoretical computer science. On the inference side, we model social and biological processes and how they generate data, and analyze the computational limits of inference on the resulting data. Our first result regards the reconstruction of pedigrees, or family histories, from genetic data. We are given strings of genetic data for many individuals, and want to reconstruct how they are related. We show how to do this when we assume that both inheritance and mating are governed by some simple stochastic processes. This builds on previous work that posed the problem without a "random mating" assumption. Our second inference result concerns the problem of corruption detection on networks. In this problem, we have parties situated on a network that report on the identity of their neighbors - "truthful" or "corrupt." The goal is to understand which network structures are amenable to finding the true identities of the nodes. We study the problem of finding a single truthful node, give an efficient algorithm for finding such a node, and prove that optimally placing corrupt agents in the network is computationally hard. For the final result in this thesis, we present a model of opinion polarization. We show that in our model, natural advertising campaigns, with the sole goal of selling a product or idea, provably lead to the polarization of opinions on various topics. We characterize optimal strategies for advertisers in a simple setting, and show that executing an optimal strategy requires solving an NP-hard inference problem in the worst case.by Govind Ramnarayan.Ph. D.Ph.D. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Scienc
The Immortal King Rao
No full textThis is a pre-copyedited, author-produced version of an article accepted for publication in American Historical Review following peer review. The version of record Ramnarayan S Rawat, The Immortal King Rao, The American Historical Review, Volume 129, Issue 3, September 2024, Pages 1029–1031, https://doi.org/10.1093/ahr/rhae236 is available online at: https://doi.org/10.1093/ahr/rhae236.
© The Author(s) 2024. Published by Oxford University Press on behalf of the American Historical Association. All rights reserved. For permissions, please email: [email protected].
This article is published and distributed under the terms of the Oxford University Press, Standard Journals Publication Model (https://academic.oup.com/pages/standard-publication-reuse-rights).
This article will be embargoed until 09/06/2026.Vauhini Vara. The Immortal King Rao. New York: W. W. Norton & Company, 2022.
“We should be free to pursue our ambitions” (Chinna Rao, owner, coconut grove)
“My ambition is to program” (King Rao)
The Immortal King Rao is an innovative piece of writing that captures the social life of caste and provides a rich ethnography of Dalit ambition, initiative, and achievement through hard work. Several reviewers have written of the novel’s dystopian themes, the existence of a single shareholder’s government managed by an algorithm that has replaced nation-states, and the “exes” or large groups of people who have rejected this system and live in autonomous island zones. Vauhini Vara uses this original framework to offer new insights into Dalit lives by showcasing Dalit ambition and achievement, simultaneously tracing Dalit lives and mobility in India and in the United States while also expanding the genre of caste fiction. As a Dalit woman whose father grew up on a coconut farm in India, Vara has written a formidable novel on breaking free from the shackles of caste through education and migration—in India and abroad
Studies on Physico-Chemical Properties of Fried Oils
No full textThis Dissertation / Report is the outcome of investigation carried out by the creator(s) / author(s) at the department/division of Central Food Technological Research Institute (CFTRI), Mysore mentioned below in this page
