Zobrazeno 1 - 10
of 27
pro vyhledávání: '"Paraashar, Manaswi"'
Determining the approximate degree composition for Boolean functions remains a significant unsolved problem in Boolean function complexity. In recent decades, researchers have concentrated on proving that approximate degree composes for special types
Externí odkaz:
http://arxiv.org/abs/2407.08385
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
A tournament is a complete directed graph. A king in a tournament is a vertex v such that every other vertex is reachable from v via a path of length at most 2. It is well known that every tournament has at least one king, one of which is a maximum o
Externí odkaz:
http://arxiv.org/abs/2402.14751
Two Boolean functions f, g : F_2^{n} \to {-1, 1} are called linearly isomorphic if there exists an invertible matrix M \in F_2^{n\times n} such that f\circ M = g. Testing linear isomorphism is a generalization of, now classical in the context of prop
Externí odkaz:
http://arxiv.org/abs/2308.02662
A tournament is a complete directed graph. It is well known that every tournament contains at least one vertex v such that every other vertex is reachable from v by a path of length at most 2. All such vertices v are called *kings* of the underlying
Externí odkaz:
http://arxiv.org/abs/2308.02472
Autor:
Chakraborty, Sourav, Kayal, Chandrima, Mittal, Rajat, Paraashar, Manaswi, Sanyal, Swagato, Saurabh, Nitin
For any Boolean functions $f$ and $g$, the question whether $R(f\circ g) = \tilde{\Theta}(R(f)R(g))$, is known as the composition question for the randomized query complexity. Similarly, the composition question for the approximate degree asks whethe
Externí odkaz:
http://arxiv.org/abs/2307.03900
The role of symmetry in Boolean functions $f:\{0,1\}^n \to \{0,1\}$ has been extensively studied in complexity theory. For example, symmetric functions, that is, functions that are invariant under the action of $S_n$, is an important class of functio
Externí odkaz:
http://arxiv.org/abs/2103.12355
Autor:
Chakraborty, Sourav, Chattopadhyay, Arkadev, Høyer, Peter, Mande, Nikhil S., Paraashar, Manaswi, de Wolf, Ronald
Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean function f : {-1,1}^n to {-1,1} and G in {AND_2, XOR_2}, the bounded-error quantum communication complexity of the composed function f o G equals O(Q(f) log n), where Q(f) denotes t
Externí odkaz:
http://arxiv.org/abs/2012.05233
Autor:
Chakraborty, Sourav, Mande, Nikhil S., Mittal, Rajat, Molli, Tulasimohan, Paraashar, Manaswi, Sanyal, Swagato
Chang's lemma (Duke Mathematical Journal, 2002) is a classical result with applications across several areas in mathematics and computer science. For a Boolean function $f$ that takes values in {-1,1} let $r(f)$ denote its Fourier rank. For each posi
Externí odkaz:
http://arxiv.org/abs/2012.02335
In this work, we resolve the query complexity of global minimum cut problem for a graph by designing a randomized algorithm for approximating the size of minimum cut in a graph, where the graph can be accessed through local queries like {\sc Degree},
Externí odkaz:
http://arxiv.org/abs/2007.09202