Zobrazeno 1 - 10
of 53
pro vyhledávání: '"Sanyal, Swagato"'
Given an Abelian group G, a Boolean-valued function f: G -> {-1,+1}, is said to be s-sparse, if it has at most s-many non-zero Fourier coefficients over the domain G. In a seminal paper, Gopalan et al. proved "Granularity" for Fourier coefficients of
Externí odkaz:
http://arxiv.org/abs/2406.18700
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
Autor:
Sanyal, Swagato
Let R_eps denote randomized query complexity for error probability eps, and R:=R_{1/3}. In this work we investigate whether a perfect composition theorem R(f o g^n)=Omega(R(f).R(g)) holds for a relation f in {0,1}^n * S and a total inner function g:{
Externí odkaz:
http://arxiv.org/abs/2401.15352
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
We show that the deterministic decision tree complexity of a (partial) function or relation $f$ lifts to the deterministic parity decision tree (PDT) size complexity of the composed function/relation $f \circ g$ as long as the gadget $g$ satisfies a
Externí odkaz:
http://arxiv.org/abs/2211.17214
Relations between the decision tree complexity and various other complexity measures of Boolean functions is a thriving topic of research in computational complexity. It is known that decision tree complexity is bounded above by the cube of block sen
Externí odkaz:
http://arxiv.org/abs/2209.08042
In a district-based election, we apply a voting rule $r$ to decide the winners in each district, and a candidate who wins in a maximum number of districts is the winner of the election. We present efficient sampling-based algorithms to predict the wi
Externí odkaz:
http://arxiv.org/abs/2203.00083
Autor:
Kar, Debajyoti, Kosan, Mert, Mandal, Debmalya, Medya, Sourav, Silva, Arlei, Dey, Palash, Sanyal, Swagato
Ensuring fairness in machine learning algorithms is a challenging and essential task. We consider the problem of clustering a set of points while satisfying fairness constraints. While there have been several attempts to capture group fairness in the
Externí odkaz:
http://arxiv.org/abs/2109.04554
We study the relationship between various one-way communication complexity measures of a composed function with the analogous decision tree complexity of the outer function. We consider two gadgets: the AND function on 2 inputs, and the Inner Product
Externí odkaz:
http://arxiv.org/abs/2105.01963
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