31,084 research outputs found
The Composition Complexity of Majority
Get PDFWe study the complexity of computing majority as a composition of local functions: Maj_n = h(g_1,…,g_m), where each g_j: {0,1}ⁿ → {0,1} is an arbitrary function that queries only k ≪ n variables and h: {0,1}^m → {0,1} is an arbitrary combining function. We prove an optimal lower bound of m ≥ Ω(n/k log k) on the number of functions needed, which is a factor Ω(log k) larger than the ideal m = n/k. We call this factor the composition overhead; previously, no superconstant lower bounds on it were known for majority.
Our lower bound recovers, as a corollary and via an entirely different proof, the best known lower bound for bounded-width branching programs for majority (Alon and Maass '86, Babai et al. '90). It is also the first step in a plan that we propose for breaking a longstanding barrier in lower bounds for small-depth boolean circuits.
Novel aspects of our proof include sharp bounds on the information lost as computation flows through the inner functions g_j, and the bootstrapping of lower bounds for a multi-output function (Hamming weight) into lower bounds for a single-output one (majority)
Mapping hypercube computations onto partitioned optical passive star networks
No full textThis paper shows that an n=2^k processor Partitioned Optical Passive Stars (POPS) network with g groups and d processors per group can simulate either a mono-directional move of an n processor hypercube or a bi-directional move of an n/2 processor hypercube using one slot when d=1 and ⌈d/g ⌉ slots when d>1. Moreover, as a direct application of the simulation, it is shown how a POPS(d, g) network, n=dg and d ≤ q, can compute the prefix sums of n data values in log_2 n + O(1) slots, faster than the best previously known ad-hoc algorithm for this problem
The shannon capacity on C(n,k)
No full textThis thesis focuses on a problem formulated by Claude Shannon named the Shannon capacity. This problem is about information rate per time unit over a noisy channel. The noisy channel is here represented by a graph. We specifically focus on a class of circulant graphs that are denoted by C(n,k) with vertex set z/nz, where all vertices are connected with the k-1 vertices before and after it. We will discuss upper bounds that were found for the Shannon capacity and how C(n,k) behaves with these upper bounds. After that we will focus on multiple ways to calculate lower bounds for the Shannon capacity of . For these three search methods will be used. These are exhaustive searching for optimal values, optimal ways to make packagings and solutions created by using a special form. As last the answers will be discussed by combining the upper and lower bounds for C(n,k). From this conclusions are drawn after which some possibilities will be given for further research. Applied Mathematic
Measurement of the ratio of branching fractions B(B0→K∗0γ )/B(B0s→φγ ) and the directCP asymmetry inB 0→K∗0γ
Get PDFThe ratio of branching fractions of the radiative B decays B0→K⁎0γ and B0s→ϕγ has been measured using an integrated luminosity of 1.0 fb−1 of pp collision data collected by the LHCb experiment at a centre-of-mass energy of s√=7TeV. The value obtained is
B(B0→K⁎0γ)B(B0s→ϕγ)=1.23±0.06(stat.)±0.04(syst.)±0.10(fs/fd),
where the first uncertainty is statistical, the second is the experimental systematic uncertainty and the third is associated with the ratio of fragmentation fractions fs/fd. Using the world average value for B(B0→K⁎0γ), the branching fraction B(B0s→ϕγ) is measured to be (3.5±0.4)×10−5.
The direct CP asymmetry in B0→K⁎0γ decays has also been measured with the same data and found to be
ACP(B0→K⁎0γ)=(0.8±1.7(stat.)±0.9(syst.))%.
Both measurements are the most precise to date and are in agreement with the previous experimental results and theoretical expectations
The Diophantine equation revisited
No full textLet k,l >= 2 be fixed integers, and C be an effectively computable constant depending only on k and l. In this paper, we prove that all solutions of the equation (x + 1)(k) + (x + 2)(k) + ... + (lx)(k) = y(n) in integers x, y,n with x, y >= 1, n >= 2, k not equal 3 and l 1 (mod 2) satisfy max{x, y, n} < C. The case when is even has already been completed by the second author (see [24])
Appropriate Similarity Measures for Author Cocitation Analysis
Get PDFWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
K-theory for group C*-algebras
No full textThese notes are based on a lecture course given by the first author in the Sedano Winter School on K-theory held in Sedano, Spain, on January 22-27th of 2007. They aim at introducing K-theory of C*-algebras, equivariant K-homology and KK-theory in the context of the Baum-Connes conjectur
Poetic Formula “I see” in K. N. Batyushkov’s Work: Creative Assimila-tion of the Derzhavin Tradition
Get PDFThe author analyses the visual metaphors of K. N. Batyushkov’s poetry, in which he acts as the creative heir to the artistic style of G. R. Derzhavin. The urgency of the problem is connected with the need to clarify the features of the creative method of K. N. Batyushkov in the aspect of his assimilation of the Derzhavin tradition. The novelty of the research is connected with the expansion of ideas about the poetics of the visual in Russian poetry of the early 19th century, in particular, in the work of K. N. Batyushkov. It is proved that K. N. Batyushkov represents vision as a process of cognition of the world. The mechanisms of K. N. Batyushkov’s transformation of visually perceived world in an artistic image are considered, the artistic thinking of the poet is reconstructed. It is revealed that the model of creating a visual verbal image in K. N. Batyushkov’s work is based on the poetic formula “I see.” It is shown that K. N. Batyushkov emphasizes the position of the observer, reflecting at the same time on the diversity and greatness of God’s world, on the cause-and-effect relationship of reality phenomena. It is established that a special place is given to the representation of historical events in the work of the poet: through the poetic formula “I see” K. N. Batyushkov places himself inside the picture, which corresponds to the emerging aesthetics of romanticism with its cult of personal perception of reality
Permutations fixing a k-set
Get PDFLet i(n,k) be the proportion of permutations π∈Sn having an invariant set of size k. In this note, we adapt arguments of the second author to prove that i(n,k)≍k−δ(1+logk)−3/2 uniformly for 1≤k≤n/2, where δ=1−1+loglog2log2. As an application, we show that the proportion of π∈Sn contained in a transitive subgroup not containing An is at least n−δ+o(1) if n is even
Efficacy and safety of selegiline across different psychiatric disorders: A systematic review and meta-analysis of oral and transdermal formulations
No full textSelegiline is an irreversible, selective type-B monoamine oxidase inhibitor (MAOI) approved for Parkison's disease—oral and major depressive disorder—transdermal formulation) resulting in non-selective MAOI activity at oral doses≥20 mg/day. The present systematic review and meta-analysis appraises the evidence of different formulations/dosages of selegiline across different psychiatric conditions. We inquired PubMed/MEDLINE/Cochrane-Central/WHO-ICTRP/Clarivate-WebOfScience and the Chinese-Electronic-Journal Database from inception to 10/26/2022 for selegiline trials involving psychiatric patients. Random-effects meta-analyses assessed heterogeneity, publication/risk biases, and confidence in the evidence, followed by sensitivity, subgroup, and meta-regression analyses. Co-primary outcomes were: changes in symptom score (standardized mean difference=SMD) and author-defined response (risk ratios=RRs). RRs of adverse events and all-cause discontinuation were secondary and acceptability outcomes, respectively. Systematic-review included 42 studies; meta-analysis, 23. Selegiline outperformed placebo in depressive symptom reduction (SMD=-0.96, 95%C.I.=-1.78, -0.14, k = 10, n = 1,308), depression (RR=1.61, 95%C.I.=1.20, 2.15, k = 9, n = 1,238) and atypical-depression response (RR=2.23, 95%C.I.=1.35, 3.68, k = 3, n = 136). Selegiline failed to outperform the placebo in negative (k = 4) or positive symptoms of schizophrenia (k = 4), attention-deficit-hyperactivity disorder (ADHD) symptoms reduction (k = 2), and smoking abstinence rate (k = 4). Selegiline did not differ from methylphenidate and ADHD scores (k = 2). No significant difference emerged in acceptability, incident diarrhea, headache, dizziness, and nausea RRs, in contrast to xerostomia (RR=1.58, 95%C.I. =1.03, 2.43, k = 6, n = 1,134), insomnia (RR=1.61, 95%C.I.=1.19, 2.17, k = 10, n = 1,768), and application-site reaction for transdermal formulation (RR=1.81, 95%C.I.=1.40, 2.33, k = 6, n = 1,662). Confidence in findings was low/very-low for most outcomes; moderate for depressive symptoms reduction (transdermal). Selegiline proved effective, safe, and well-tolerated for depressive disorders, yet further evidence is warranted about specific psychiatric disorders
- …
