Zobrazeno 1 - 10
of 19 337
pro vyhledávání: '"SUDAN, MADHU"'
A $(1 \pm \epsilon)$-sparsifier of a hypergraph $G(V,E)$ is a (weighted) subgraph that preserves the value of every cut to within a $(1 \pm \epsilon)$-factor. It is known that every hypergraph with $n$ vertices admits a $(1 \pm \epsilon)$-sparsifier
Externí odkaz:
http://arxiv.org/abs/2407.03934
Autor:
Maji, Moupiya, More, Surhud, Sule, Aniket, Balasubramanya, Vishaak, Bhandari, Ankit, Chand, Hum, Chavan, Kshitij, Dasgupta, Avik, De, Anindya, Gangopadhyay, Jayant, Gulati, Mamta, Hasan, Priya, Ishtiyaq, Syed, Madani, Meraj, Misra, Kuntal, N, Amoghavarsha, Oberoi, Divya, Pattnaik, Subhendu, Patwardhan, Mayuri, Ramanujam, Niruj Mohan, Ranadive, Pritesh, Sawant, Disha, Sharma, Paryag, Sharma, Twinkle, Shetye, Sai, Singhal, Akshat, Srivastava, Ajit M., Sudan, Madhu, Syed, Mumtaz, Vikranth, Pulamathi, Yadav, Virendra
We present the results of a nation-wide baseline survey, conducted by us, for the status of Astronomy education among secondary school students in India. The survey was administered in 10 different languages to over 2000 students from diverse backgro
Externí odkaz:
http://arxiv.org/abs/2406.12308
CSP sparsification, introduced by Kogan and Krauthgamer (ITCS 2015), considers the following question: when can an instance of a constraint satisfaction problem be sparsified (by retaining a weighted subset of the constraints) while still roughly cap
Externí odkaz:
http://arxiv.org/abs/2404.06327
Autor:
Amireddy, Prashanth, Behera, Amik Raj, Paraashar, Manaswi, Srinivasan, Srikanth, Sudan, Madhu
We consider the task of locally correcting, and locally list-correcting, multivariate linear functions over the domain $\{0,1\}^n$ over arbitrary fields and more generally Abelian groups. Such functions form error-correcting codes of relative distanc
Externí odkaz:
http://arxiv.org/abs/2403.20305
Recently, a number of variants of the notion of cut-preserving hypergraph sparsification have been studied in the literature. These variants include directed hypergraph sparsification, submodular hypergraph sparsification, general notions of approxim
Externí odkaz:
http://arxiv.org/abs/2402.13151
We prove that the most natural low-degree test for polynomials over finite fields is ``robust'' in the high-error regime for linear-sized fields. Specifically we consider the ``local'' agreement of a function $f: \mathbb{F}_q^m \to \mathbb{F}_q$ from
Externí odkaz:
http://arxiv.org/abs/2311.12752
We introduce a notion of code sparsification that generalizes the notion of cut sparsification in graphs. For a (linear) code $\mathcal{C} \subseteq \mathbb{F}_q^n$ of dimension $k$ a $(1 \pm \epsilon)$-sparsification of size $s$ is given by a weight
Externí odkaz:
http://arxiv.org/abs/2311.00788
We study processes of societal knowledge accumulation, where the validity of a new unit of knowledge depends both on the correctness of its derivation and on the validity of the units it depends on. A fundamental question in this setting is: If a con
Externí odkaz:
http://arxiv.org/abs/2309.05638
The goal of the trace reconstruction problem is to recover a string $x\in\{0,1\}^n$ given many independent {\em traces} of $x$, where a trace is a subsequence obtained from deleting bits of $x$ independently with some given probability $p\in [0,1).$
Externí odkaz:
http://arxiv.org/abs/2308.14993
We study the question of local testability of low (constant) degree functions from a product domain $S_1 \times \dots \times {S}_n$ to a field $\mathbb{F}$, where ${S_i} \subseteq \mathbb{F}$ can be arbitrary constant sized sets. We show that this fa
Externí odkaz:
http://arxiv.org/abs/2305.04983