publication . Preprint . 2016

Continuous Sensitivity and Reversibility

İlhan, Aslı Güçlükan; Ünlü, Özgün;
Open Access English
  • Published: 22 Jan 2016
Abstract
Let $n$ be a positive integer and $f$ a differentiable function from a convex subset $C$ of the Euclidean space $\mathbb{R}^n$ to a smooth manifold. We define an invariant of $f$ via counting certain threshold functions associated to $f$. We call this invariant the continuous sensitivity of $f$ and denote it by $\mathrm{cs}_{C}(f)$. This invariant is a real number between $0$ and $n$ and measures how sensitive $f$ is to change in its input variables. For example, if $f$ is a constant function then $\mathrm{cs}_{C}(f)=0$. On the other extreme, if $\mathrm{cs}_{C}(f)=n$ then $f$ is one-to-one on $C$. This last statement is important for reversibility problems. To ...
Read more
Subjects
free text keywords: Mathematics - Combinatorics, Computer Science - Discrete Mathematics
Download from
arXiv.org e-Print Archive
Preprint . 2016
Provider: arXiv.org e-Print Archive
36 references, page 1 of 3

[1] Anas N. Al-Rabadi. Reversible logic synthesis. Springer-Verlag, Berlin, 2004. From fundamentals to quantum computing. [OpenAIRE]

[2] Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, and Song Zuo. Tighter relations between sensitivity and other complexity measures. In Automata, languages, and programming. Part I, volume 8572 of Lecture Notes in Comput. Sci., pages 101-113. Springer, Heidelberg, 2014.

[3] F. Bazso´. Derivation of vector-valued Boolean functions. Acta Math. Hungar., 87(3):197-203, 2000.

[4] C. H. Bennett. Logical reversibility of computation. IBM J. Res. Develop., 17:525-532, 1973.

[5] Leonard Bolc and Piotr Borowik. Many-valued logics. Vol. 1. Springer-Verlag, Berlin, 1992. Theoretical foundations. [OpenAIRE]

[6] J. Bourgain. On the distributions of the Fourier spectrum of Boolean functions. Israel J. Math., 131:269-276, 2002.

[7] Jehoshua Bruck. Harmonic analysis of polynomial threshold functions. SIAM J. Discrete Math., 3(2):168-177, 1990.

[8] Daizhan Cheng and Xiangru Xu. Bi-decomposition of multi-valued logical functions and its applications. Automatica J. IFAC, 49(7):1979-1985, 2013.

[9] Yves Crama and Peter L. Hammer. Boolean functions, volume 142 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 2011. Theory, algorithms, and applications.

[10] Craig Gotsman and Nathan Linial. Spectral properties of threshold functions. Combinatorica, 14(1):35-50, 1994.

[11] Ana Gra¸ca, Jo˜ao Marques-Silva, Inˆes Lynce, and Arlindo L. Oliveira. Haplotype inference with pseudo-Boolean optimization. Ann. Oper. Res., 184:137-162, 2011.

[12] Claire Kenyon and Samuel Kutin. Sensitivity, block sensitivity, and l-block sensitivity of Boolean functions. Inform. and Comput., 189(1):43-53, 2004.

[13] Martin Kutrib. Aspects of reversibility for classical automata. In Computing with new resources, volume 8808 of Lecture Notes in Comput. Sci., pages 83-98. Springer, Cham, 2014. [OpenAIRE]

[14] R. Landauer. Irreversibility and heat generation in the computing process. IBM J. Res. Develop., 5:183-191, 1961.

[15] V. K. Leont'ev. On pseudo-Boolean polynomials. Comput. Math. Math. Phys., 55(11):1926- 1932, 2015. [OpenAIRE]

36 references, page 1 of 3
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue