Hasil untuk "Folklore"

J. Sanders

Alptug Aytekin, Mohamed Nomeir, Lei Hu et al.

An important part of the information theory folklore had been about the output statistics of codes that achieve the capacity and how the empirical distributions compare to the output distributions induced by the optimal input in the channel capacity problem. Results for a variety of such empirical output distributions of good codes have been known in the literature, such as the comparison of the output distribution of the code to the optimal output distribution in vanishing and non-vanishing error probability cases. Motivated by these, we aim to achieve similar results for the quantum codes that are used for classical communication, that is the setting in which the classical messages are communicated through quantum codewords that pass through a noisy quantum channel. We first show the uniqueness of the optimal output distribution, to be able to talk more concretely about the optimal output distribution. Then, we extend the vanishing error probability results to the quantum case, by using techniques that are close in spirit to the classical case. We also extend non-vanishing error probability results to the quantum case on block codes, by using the second-order converses for such codes based on hypercontractivity results for the quantum generalized depolarizing semi-groups.

Andrew Jacobsen, Dorian Baudry, Shinji Ito et al.

We revisit the standard perturbation-based approach of Abernethy et al. (2008) in the context of unconstrained Bandit Linear Optimization (uBLO). We show the surprising result that in the unconstrained setting, this approach effectively reduces Bandit Linear Optimization (BLO) to a standard Online Linear Optimization (OLO) problem. Our framework improves on prior work in several ways. First, we derive expected-regret guarantees when our perturbation scheme is combined with comparator-adaptive OLO algorithms, leading to new insights about the impact of different adversarial models on the resulting comparator-adaptive rates. We also extend our analysis to dynamic regret, obtaining the optimal $\sqrt{P_T}$ path-length dependencies without prior knowledge of $P_T$. We then develop the first high-probability guarantees for both static and dynamic regret in uBLO. Finally, we discuss lower bounds on the static regret, and prove the folklore $Ω(\sqrt{dT})$ rate for adversarial linear bandits on the unit Euclidean ball, which is of independent interest.

Keith Levin

In many applications, weighted networks are constructed based on time series data: each time series is associated to a vertex and edge weights are given by pairwise correlations. The result is a network whose edge dependency structure violates the assumptions of most common network models. Nonetheless, it is common to analyze these "correlation networks" using embedding methods derived from edge-independent network models, based on a belief that the edges are approximately independent. In this work, we put this modeling choice on firm theoretical ground. We show that when the time series are expressible in terms of a small number of Fourier basis elements (or in some other suitably-chosen basis), correlation networks correspond to latent space networks with dependent edge noise in which the vertex-level latent variables encode the basis coefficients. Further, we show that when time series are observed subject to noise, spectral embedding of the resulting noisy correlation network still recovers these true vertex-level latent representations under suitable assumptions. This characterization of embeddings as learning Fourier coefficients appears to be folklore in the signal processing community in the context of principal component analysis, but is, to the best of our knowledge, new to the statistical network analysis literature.

Jinge Bao, Minbo Gao, Qisheng Wang

The relative entropy between quantum states quantifies their distinguishability. The estimation of certain relative entropies has been investigated in the literature, e.g., the von Neumann relative entropy and sandwiched Rényi relative entropy. In this paper, we present a comprehensive study of the estimation of the quantum Tsallis relative entropy. We show that for any constant $α\in (0, 1)$, the $α$-Tsallis relative entropy between two quantum states of rank $r$ can be estimated with sample complexity $\operatorname{poly}(r)$, which can be made more efficient if we know their state-preparation circuits. As an application, we obtain an approach to tolerant quantum state certification with respect to the quantum Hellinger distance with sample complexity $\widetilde{O}(r^{3.5})$, which exponentially outperforms the folklore approach based on quantum state tomography when $r$ is polynomial in the number of qubits. In addition, we show that the quantum state distinguishability problems with respect to the quantum $α$-Tsallis relative entropy and quantum Hellinger distance are $\mathsf{QSZK}$-complete in a certain regime, and they are $\mathsf{BQP}$-complete in the low-rank case.

Kengo Nakamura, Masaaki Nishino, Shuhei Denzumi

Binary decision diagram (BDD) and zero-suppressed binary decision diagram (ZDD) are data structures to represent a family of (sub)sets compactly, and it can be used as succinct indexes for a family of sets. To build BDD/ZDD representing a desired family of sets, there are many transformation operations that take BDDs/ZDDs as inputs and output BDD/ZDD representing the resultant family after performing operations such as set union and intersection. However, except for some basic operations, the worst-time complexity of taking such transformation on BDDs/ZDDs has not been extensively studied, and some contradictory statements about it have arisen in the literature. In this paper, we show that many transformation operations on BDDs/ZDDs, including all operations for families of sets that appear in Knuth's book, cannot be performed in worst-case polynomial time in the size of input BDDs/ZDDs. This refutes some of the folklore circulated in past literature and resolves an open problem raised by Knuth. Our results are stronger in that such blow-up of computational time occurs even when the ordering, which has a significant impact on the efficiency of treating BDDs/ZDDs, is chosen arbitrarily.

Tapas Chatterjee, Sagar Mandal, Sourav Mandal

Does $20$ have a friend? Or is it a solitary number? A folklore conjecture asserts that $20$ has no friends i.e. it is a solitary number. In this article, we prove that, a friend $N$ of $20$ is of the form $N=2\cdot5^{2a}\cdot m^2$, with $(3,m)=(7,m)=1$ and it has at least six distinct prime divisors. Furthermore, we show that $Ω(N)\geq 2ω(N)+6a-5$ and if $Ω(m)\leq K$ then $N< 10\cdot 6^{(2^{K-2a+3}-1)^2}$, where $Ω(n)$ and $ω(n)$ denote the total number of prime divisors and the number of distinct prime divisors of the integer $n$ respectively. In addition, we deduce that, not all exponents of odd prime divisors of friend $N$ of $20$ are congruent to $-1$ modulo $f$, where $f$ is the order of $5$ in $(\mathbb{Z}/p\mathbb{Z})^\times$ such that $3\mid f$ and $p$ is a prime congruent to $1$ modulo $6$. Also, we prove necessary upper bounds for all prime divisors of friends of 20 in terms of the number of divisors of the friend. In addition, we prove that, if $P$ is the largest prime divisor of $N$ then $P<N^{\frac{1}{4}}$.

Yuqian Sun, Zhouyi Li, Ke Fang et al.

In this paper, we present "1001 Nights", an AI-native game that allows players lead in-game reality through co-created storytelling with the character driven by large language model. The concept is inspired by Wittgenstein's idea of the limits of one's world being determined by the bounds of their language. Using advanced AI tools like GPT-4 and Stable Diffusion, the second iteration of the game enables the protagonist, Shahrzad, to realize words and stories in her world. The player can steer the conversation with the AI King towards specific keywords, which then become battle equipment in the game. This blend of interactive narrative and text-to-image transformation challenges the conventional border between the game world and reality through a dual perspective. We focus on Shahrzad, who seeks to alter her fate compared to the original folklore, and the player, who collaborates with AI to craft narratives and shape the game world. We explore the technical and design elements of implementing such a game with an objective to enhance the narrative game genre with AI-generated content and to delve into AI-native gameplay possibilities.

Noga Alon, Dmitrii Avdiukhin, Dor Elboim et al.

Contrastive learning is a highly successful technique for learning representations of data from labeled tuples, specifying the distance relations within the tuple. We study the sample complexity of contrastive learning, i.e. the minimum number of labeled tuples sufficient for getting high generalization accuracy. We give tight bounds on the sample complexity in a variety of settings, focusing on arbitrary distance functions, both general $\ell_p$-distances, and tree metrics. Our main result is an (almost) optimal bound on the sample complexity of learning $\ell_p$-distances for integer $p$. For any $p \ge 1$ we show that $\tilde Θ(\min(nd,n^2))$ labeled tuples are necessary and sufficient for learning $d$-dimensional representations of $n$-point datasets. Our results hold for an arbitrary distribution of the input samples and are based on giving the corresponding bounds on the Vapnik-Chervonenkis/Natarajan dimension of the associated problems. We further show that the theoretical bounds on sample complexity obtained via VC/Natarajan dimension can have strong predictive power for experimental results, in contrast with the folklore belief about a substantial gap between the statistical learning theory and the practice of deep learning.

Hary Soedarto Harjono, Bambang Hariyadi, Priyanto et al.

The basic competence of students to be able to describe the values and content of hikayat or folklore, which is one of the achievement targets for learning literature in high school cannot be grasped optimally without the support of appropriate learning media. Therefore, the main objective of this research is to develop learning media in the form of an application that can be used to explore and describe the values included in the Cik Upik folklore, which is a form of Malay oral literature. In doing so, research and development model of ADDIE (Analysis-Development-Design-Implementation-Evaluation) is carried out by involving subject matter experts in Indonesian language and folklores and media experts as validators for instrument and product development. In addition, an Indonesian teacher and 10 class X students at a high school participated as research subjects. In the needs analysis stage, a questionnaire was used to explore the needs of teachers and students, which were used as a consideration in designing and developing learning media. The results of the validation of material experts and media experts as well as the responses of teachers and students show that the learning media applications developed in this study were declared valid with very good qualifications. This implied that the learning media application developed in this research and development is very feasible to be used as a learning medium to describe the values included in folklore.

Emmanuel Chimeh Ezeako, Florence Nkechi Nworah, Dionysius Obinna Osuji

Abstract Background Sida linifolia L. is a weed ubiquitously found in Africa with several folkloric applications. Traditional healers in the Southeastern part of Nigeria employ the alcoholic concoction of S. linifolia leaves as antidepressants, anti-malaria, antihypertensive, anti-abortifacients, and for managing painful whitlow; however, these claims lack scientific validation. The present study was aimed to explore the phytochemical profile of the plant, S. linifolia with special emphasis to its antioxidant and inhibitory actions on enzymes linked to inflammation, diabetes, and neurological disorders. Phytochemical profiling and in vitro antioxidant and enzyme inhibition assays were employed to assess the pharmacological profile of S. linifolia ethanolic leaf fraction (SLELF). Results Preliminary phytochemical screening of SLELF revealed appreciable amounts of total phenolics (91.64 ± 7.61 mg GAE/g), total tannins (62.44 ± 3.86 mg TAE/g), and total flavonoids (27.35 ± 1.48 mg QE/g) present in SLELF. Results of HPLC analysis of SLELF revealed rich composition in bioactive compounds such as ellagic acid, quercetin, ferulic acid, 3,4-dimethoxy benzoic acid, gallic acid, 4-methoxy cinnamic acid, sinapic acid, vanillic acid, and chlorogenic acid. Enzymatic antioxidants (catalase and superoxide dismutase), non-enzymatic antioxidants (reduced glutathione (GSH), Vit A, C, and E), elemental minerals (Cu, Mn, Zn, Cr, Fe, and Ca), and γ-aminobutyric acid (GABA) were present in SLELF in appreciable levels. At various concentrations (0.2–1.0 mg/ml), SLELF exhibited potent and concentration-dependent hydrogen peroxide (H2O2) and 2,2′-azinobis-(3-ethylbenzothiazoline-6-sulfonic) acid (ABTS) radical scavenging activities and exerted moderate inhibitory actions on enzymes associated with inflammation (cyclooxogenase-2 (COX-2) and lipoxygenases (LOXs), diabetes (α-amylase, α-glucosidase), and neurological disorders (butyrylcholinesterase (BChE) and γ-aminobutyric acid transaminase (GABA-T), compared to respective standards (ascorbic acid, acarbose, indomethacin, galanthamine, and vigabatrin). Perhaps, the observed potent pharmacological activities of SLELF could be anchored to its phytoconstituents. Furthermore, the slightly higher ranges of IC50 values (0.57–0.87 mg/ml) of SLELF compared to standards (0.44–0.68 mg/ml) suggest moderation in enzyme inhibition that may preclude adverse side effects. Conclusion This study lends credence to the folklore claims of S. linifolia leaves and revealed its potential as possible source of bioactive compounds for medicinal and pharmaceutical exploration.

Aritra Kundu

Passing from a microscopic discrete lattice system with many degrees of freedom to a mesoscopic continuum system described by a few coarse-grained equations is challenging. The common folklore is to take the thermodynamic limit so that the physics of the discrete lattice describes the continuum results. The analytical procedure to do so relies on defining a small length scale (typically the lattice spacing) to coarse-grain the microscopic evolution equations. Moving from the microscopic scale to the mesoscopic scale then requires careful approximations. In this work, we numerically test the coarsening in a Toda chain, which is an interacting integrable system, i.e. a system with a macroscopic number of conserved charges. Specifically, we study the spreading of fluctuations by computing the spatiotemporal thermal correlations with three different methods: (a) Using microscopic molecular dynamics simulation with a large number of particles; (b) solving the generalized hydrodynamics equation; (c) solving the linear Euler scale equations for each conserved quantities. Surprisingly, the results for the small systems (c) match the thermodynamic results in (a) and (b) for macroscopic systems. This reiterates the importance and validity of integrable hydrodynamics in describing experiments in the laboratory, where we typically have microscopic systems.

Ewa Masłowska

Recenzja: Piotr Braszak, Na rozstajnych drogach, około północy. Doświadczenia graniczne we wschodniosłowiańskich i polskich pieśniach ludowych, Wydawnictwo Naukowe UAM, Poznań 2021.

Ioannis Caragiannis, Stavros Ioannidis

Fair division has emerged as a very hot topic in multiagent systems, and envy-freeness is among the most compelling fairness concepts. An allocation of indivisible items to agents is envy-free if no agent prefers the bundle of any other agent to his own in terms of value. As envy-freeness is rarely a feasible goal, there is a recent focus on relaxations of its definition. An approach in this direction is to complement allocations with payments (or subsidies) to the agents. A feasible goal then is to achieve envy-freeness in terms of the total value an agent gets from the allocation and the subsidies. We consider the natural optimization problem of computing allocations that are {\em envy-freeable} using the minimum amount of subsidies. As the problem is NP-hard, we focus on the design of approximation algorithms. On the positive side, we present an algorithm that, for a constant number of agents, approximates the minimum amount of subsidies within any required accuracy, at the expense of a graceful increase in the running time. On the negative side, we show that, for a super-constant number of agents, the problem of minimizing subsidies for envy-freeness is not only hard to compute exactly (as a folklore argument shows) but also, more importantly, hard to approximate.

Janusz Mierczyński, Lei Niu, Alfonso Ruiz-Herrera

A folklore result due to M.W. Hirsch states that most competitive maps admit a carrying simplex, i.e., an invariant hypersurface which attracts all nontrivial orbits. The common approach in the study of these maps is to focus on the dynamical behavior on the carrying simplex. However, this manifold is normally non-smooth. Therefore, not every tool coming from Differential Geometry can be applied. In particular, the classical Grobman-Hartman theorem can not be used on the carrying simplex. In this paper, we prove that the restriction of the map to the carrying simplex in a neighborhood of an interior fixed point is topologically conjugate to the restriction of the map to its pseudo-unstable manifold by an invariant foliation. This implies that the linearization techniques are applicable for studying the local dynamics of the interior fixed points on the carrying simplex. We further construct the stable and unstable manifolds on the carrying simplex. On the other hand, our results also give partial responses to Hirsch's problem regarding the smoothness of the carrying simplex. We discuss some applications in classical models of population dynamics. Although we focus on monotone maps, many results of the paper can be applied to maps that admit a non-smooth center-manifold.

Maciej Skorski

Kernel Density Estimation is a very popular technique of approximating a density function from samples. The accuracy is generally well-understood and depends, roughly speaking, on the kernel decay and local smoothness of the true density. However concrete statements in the literature are often invoked in very specific settings (simplified or overly conservative assumptions) or miss important but subtle points (e.g. it is common to heuristically apply Taylor's expansion globally without referring to compactness). The contribution of this paper is twofold (a) we demonstrate that, when the bandwidth is an arbitrary invertible matrix going to zero, it is necessary to keep a certain balance between the \emph{kernel decay} and \emph{magnitudes of bandwidth eigenvalues}; in fact, without the sufficient decay the estimates may not be even bounded (b) we give a rigorous derivation of bounds with explicit constants for the bias, under possibly minimal assumptions. This connects the kernel decay, bandwidth norm, bandwidth determinant and density smoothness. It has been folklore that the issue with Taylor's formula can be fixed with more complicated assumptions on the density (for example p. 95 of "Kernel Smoothing" by Wand and Jones); we show that this is actually not necessary and can be handled by the kernel decay alone.

Azam Asanjarani, Yoni Nazarathy

We consider two classes of irreducible Markovian arrival processes specified by the matrices $C$ and $D$. The Markov Modulated Poison Process (MMPP) and the Markovian Switched Poison Process (MSPP). The former exhibits a diagonal $D$ while the latter exhibits a diagonal $C$. For these two classes, we consider the following statements: (I) Overdispersion of the counts process. (II) A non-increasing hazard rate of the stationary inter-event time. (III) The squared coefficient of variation of the event stationary process is greater or equal to unity. (IV) A stochastic order showing that the time stationary inter-arrival time dominates the event-stationary time. For general MSPPs and two-state MMPPs, we show that (I)-(IV) hold. Then for general MMPPs, it is easy to establish (I), while (II) is false due to a counter-example of Miklos Telek and Illes Horvath. For general simple point processes, (III) follows from (IV). For MMPPs we conjecture and numerically test that (IV) and thus (III) hold. Importantly, modeling folklore has often treated MMPPs as ``bursty'' and implicitly assumed that (III) holds. However, this is still an open question.

I Gede Adi Sudi Anggara, Hendra Santosa, A.A. Gde Bagus Udayana

Character is a very important and fundamental matter in a child's development. Character education has the same orientation with moral education, whereas moral education is very important in directing young generation to become good people through good values approach. In the midst of current IT advances, animated films are one of the effective and interesting media in transferring the values of character education and moral messages to children. The 2D animated film entitled Pendeta Bangau (The Priestess of Stork) is an animated film which source of story comes from Balinese folklore entitled Pedanda Baka. The aim of this study is to discuss the values of character education and moral messages/values contained in the animated film entitled “Pendeta Bangau”. This study uses qualitative research methods with qualitative data analysis techniques model of Miles and Huberman. The result of this study shows that the character education values from the animated film entitled Pendeta Bangau contains the values of honesty, tolerate, friendship / communicative, love of peace, and curiosity. While the moral message/value was seen in the final/end of film, namely the Bangau (stork) died due to its immorality. Its Bangau dead is related to the principal of Prarabda Karmaphala, namely Bangau, gets the results of his behavior in the present, and is now available without being there anymore.

Bhaskar Bagchi

An outstanding folklore conjecture asserts that, for any prime $p$, up to isomorphism the projective plane $PG(2,\mathbb{F}_p)$ over the field $\mathbb{F}_p := \mathbb{Z}/p\mathbb{Z}$ is the unique projective plane of order $p$. Let $π$ be any projective plane of order $p$. For any partial linear space ${\cal X}$, define the inclusion number $i({\cal X},π)$ to be the number of isomorphic copies of ${\cal X}$ in $π$. In this paper we prove that if ${\cal X}$ has at most $\log_2 p$ lines, then $i({\cal X},π)$ can be written as an explicit rational linear combination (depending only on ${\cal X}$ and $p$) of the coefficients of the complete weight enumerator (c.w.e.) of the $p$-ary code of $π$. Thus, the c.w.e. of this code carries an enormous amount of structural information about $π$. In consequence, it is shown that if $p > 2^ 9=512$, and $π$ has the same c.w.e. as $PG(2,\mathbb{F}_p)$, then $π$ must be isomorphic to $PG(2,\mathbb{F}_p)$. Thus, the uniqueness conjecture can be approached via a thorough study of the possible c.w.e. of the codes of putative projective planes of prime order.

Xiaobin Gao, Emrah Akyol, Tamer Basar

This paper considers a sequential sensor scheduling and remote estimation problem with multiple communication channels. Departing from the classical remote estimation paradigm, which involves one communication channel (noiseless or noisy), we consider here the more realistic setting of two channels with different characteristics (one is cheap but noisy, the other one is costly but noiseless). We first show, via a counter-example, that the common folklore of applying symmetric threshold-based policy, which is well known to be optimal (for unimodal state densities) in the classical remote estimation problem, can no longer be optimal in our setting. In view of that, and in order to make the problem tractable, we introduce a side channel which signals to the receiver the sign of the underlying state. We show, under some technical assumptions, that a threshold-in-threshold based communication scheduling is optimal. The impact of the results is analyzed numerically based on dynamic programming. This numerical analysis reveals some rather surprising results inheriting known properties from the single channel settings, such as not exhausting all the opportunities available for the noisy channel.