Zobrazeno 1 - 10
of 71
pro vyhledávání: '"Sarma, Jayalal"'
Decision trees are one of the most fundamental computational models for computing Boolean functions $f : \{0, 1\}^n \mapsto \{0, 1\}$. It is well-known that the depth and size of decision trees are closely related to time and number of processors res
Externí odkaz:
http://arxiv.org/abs/2501.00831
Designing algorithms for space bounded models with restoration requirements on the space used by the algorithm is an important challenge posed about the catalytic computation model introduced by Buhrman et al. (2014). Motivated by the scenarios where
Externí odkaz:
http://arxiv.org/abs/2409.07208
Autor:
M., Anoop S. K., Sarma, Jayalal
Publikováno v:
Fundamenta Informaticae, Volume 191, Issue 2 (July 8, 2024) fi:11200
Computing the rotation distance between two binary trees with $n$ internal nodes efficiently (in $poly(n)$ time) is a long standing open question in the study of height balancing in tree data structures. In this paper, we initiate the study of this p
Externí odkaz:
http://arxiv.org/abs/2304.03985
In this paper, we initiate study of the computational power of adaptive and non-adaptive monotone decision trees - decision trees where each query is a monotone function on the input bits. In the most general setting, the monotone decision tree heigh
Externí odkaz:
http://arxiv.org/abs/2301.00136
Autor:
Anoop, S.K.M.1 (AUTHOR) skmanoop@cse.iitm.ac.in, Sarma, Jayalal1 (AUTHOR) jayalal@cse.iitm.ac.in
Publikováno v:
Fundamenta Informaticae. 2024, Vol. 191 Issue 2, p79-104. 26p.
Autor:
Dinesh, Krishnamoorthy, Sarma, Jayalal
$\newcommand{\F}{\mathbb{F}}$We study the Boolean function parameters sensitivity ($s$), block sensitivity ($bs$), and alternation ($alt$) under specially designed affine transforms. For a function $f:\F_2^n\to \{0,1\}$, and $A=Mx+b$ for $M \in \F_2^
Externí odkaz:
http://arxiv.org/abs/1808.10191
$\newcommand{\EC}{\mathsf{EC}}\newcommand{\KW}{\mathsf{KW}}\newcommand{\DT}{\mathsf{DT}}\newcommand{\psens}{\mathsf{psens}} \newcommand{\calB}{{\cal B}} $ For a Boolean function $f:\{0,1\}^n \to \{0,1\}$ computed by a circuit $C$ over a finite basis
Externí odkaz:
http://arxiv.org/abs/1808.07199
Publikováno v:
In Theoretical Computer Science 19 June 2022 921:112-126
Autor:
Dinesh, Krishnamoorthy, Sarma, Jayalal
$\newcommand{\sp}{\mathsf{sparsity}}\newcommand{\s}{\mathsf{s}}\newcommand{\al}{\mathsf{alt}}$ The well-known Sensitivity Conjecture states that for any Boolean function $f$, block sensitivity of $f$ is at most polynomial in sensitivity of $f$ (denot
Externí odkaz:
http://arxiv.org/abs/1712.05735
Publikováno v:
Fundam. Inform., volume 145, number 4, pages 471-483 (2016)
We initiate a complexity theoretic study of the language based graph reachability problem (L-REACH) : Fix a language L. Given a graph whose edges are labeled with alphabet symbols of the language L and two special vertices s and t, test if there is p
Externí odkaz:
http://arxiv.org/abs/1701.03255