اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدComputability of Probability Distributions and Characteristic Functions
119
0
0.0
(
0
)
تأليف
Takakazu Mori
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
As a part of our works on effective properties of probability distributions, we deal with the corresponding characteristic functions. A sequence of probability distributions is computable if and only if the corresponding sequence of characteristic functions is computable. As for the onvergence problem, the effectivized Glivenkos theorem holds. Effectivizations of Bochners theorem and de Moivre-Laplace central limit theorem are also proved.
قيم البحث
اقرأ أيضاً
This volume of the Electronic Proceedings in Theoretical Computer Science (EPTCS) contains extended abstracts of talks to be presented at the Seventh International Conference on Computability and Complexity in Analysis (CCA 2010) that will take place
in Zhenjiang, China, June 21-25, 2010. This conference is the seventeenth event in the series of CCA annual meetings. The CCA conferences are aimed at promoting the study and advancement of the theory of computability and complexity over real-valued data and its application.
In this paper we investigate algorithmic randomness on more general spaces than the Cantor space, namely computable metric spaces. To do this, we first develop a unified framework allowing computations with probability measures. We show that any comp
utable metric space with a computable probability measure is isomorphic to the Cantor space in a computable and measure-theoretic sense. We show that any computable metric space admits a universal uniform randomness test (without further assumption).
The $k$-dimensional Weisfeiler-Leman algorithm is a powerful tool in graph isomorphism testing. For an input graph $G$, the algorithm determines a canonical coloring of $s$-tuples of vertices of $G$ for each $s$ between 1 and $k$. We say that a numer
ical parameter of $s$-tuples is $k$-WL-invariant if it is determined by the tuple color. As an application of Dvov{r}aks result on $k$-WL-invariance of homomorphism counts, we spot some non-obvious regularity properties of strongly regular graphs and related graph families. For example, if $G$ is a strongly regular graph, then the number of paths of length 6 between vertices $x$ and $y$ in $G$ depends only on whether or not $x$ and $y$ are adjacent (and the length 6 is here optimal). Or, the number of cycles of length 7 passing through a vertex $x$ in $G$ is the same for every $x$ (where the length 7 is also optimal).
The Humbert-Bessel are multi-index functions with various applications in electromagnetism. New families of functions sharing some similarities with Bessel functions are often introduced in the mathematical literature, but at a closer analysis they a
re not new, in the strict sense of the word, and are shown to be expressible in terms of already discussed forms. This is indeed the case of the re-modified Bessel functions, whose properties have been analyzed within the context of coincidence problems in probability theory. In this paper we show that these functions are particular cases of the Humbert-Bessel ones.
For Boolean satisfiability problems, the structure of the solution space is characterized by the solution graph, where the vertices are the solutions, and two solutions are connected iff they differ in exactly one variable. In 2006, Gopalan et al. st
udied connectivity properties of the solution graph and related complexity issues for CSPs, motivated mainly by research on satisfiability algorithms and the satisfiability threshold. They proved dichotomies for the diameter of connected components and for the complexity of the st-connectivity question, and conjectured a trichotomy for the connectivity question. Recently, we were able to establish the trichotomy [arXiv:1312.4524]. Here, we consider connectivity issues of satisfiability problems defined by Boolean circuits and propositional formulas that use gates, resp. connectives, from a fixed set of Boolean functions. We obtain dichotomies for the diameter and the two connectivity problems: on one side, the diameter is linear in the number of variables, and both problems are in P, while on the other side, the diameter can be exponential, and the problems are PSPACE-complete. For partially quantified formulas, we show an analogous dichotomy.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
