Search results for "Recursion"
showing 10 items of 61 documents
On the impact of forgetting on learning machines
1995
People tend not to have perfect memories when it comes to learning, or to anything else for that matter. Most formal studies of learning, however, assume a perfect memory. Some approaches have restricted the number of items that could be retained. We introduce a complexity theoretic accounting of memory utilization by learning machines. In our new model, memory is measured in bits as a function of the size of the input. There is a hierarchy of learnability based on increasing memory allotment. The lower bound results are proved using an unusual combination of pumping and mutual recursion theorem arguments. For technical reasons, it was necessary to consider two types of memory : long and sh…
Symmetry-assisted adversaries for quantum state generation
2011
We introduce a new quantum adversary method to prove lower bounds on the query complexity of the quantum state generation problem. This problem encompasses both, the computation of partial or total functions and the preparation of target quantum states. There has been hope for quite some time that quantum state generation might be a route to tackle the $backslash$sc Graph Isomorphism problem. We show that for the related problem of $backslash$sc Index Erasure our method leads to a lower bound of $backslash Omega(backslash sqrt N)$ which matches an upper bound obtained via reduction to quantum search on $N$ elements. This closes an open problem first raised by Shi [FOCS'02]. Our approach is …
The relavance of indoor comfort in the process of prisoners’ rehabilitation: a case study
2016
The history of prisons is full of contradictions in every historical period and the evolution of prison buildings expresses many faces in the history of each country. The concept of punishment imposed on the offender has undergone several changes over the centuries, related to culture, politics, and to the evolution of the human thought. For centuries, tiny closed spaces have been adapted for the offenders' detention, without ever thinking to create an ad hoc functional distribution of spaces. The issue of the design of prisons has often been a reason of debate, and it is still an open field of discussion. From a legal point of view, in recent years there has been a rethinking of the proble…
A reduction theorem for perfect locally finite minimal non-FC groups
1999
A group G is said to be a minimal non-FC group, if G contains an infinite conjugacy class, while every proper subgroup of G merely has finite conjugacy classes. The structure of imperfect minimal non-FC groups is quite well-understood. These groups are in particular locally finite. At the other end of the spectrum, a perfect locally finite minimal non-FC group must be a p-group. And it has been an open question for quite a while now, whether such groups exist or not.
A reliable incremental method of computing the limit load in deformation plasticity based on compliance : Continuous and discrete setting
2016
The aim of this paper is to introduce an enhanced incremental procedure that can be used for the numerical evaluation and reliable estimation of the limit load. A conventional incremental method of limit analysis is based on parametrization of the respective variational formulation by the loading parameter ? ? ( 0 , ? l i m ) , where ? l i m is generally unknown. The enhanced incremental procedure is operated in terms of an inverse mapping ? : α ? ? where the parameter α belongs to ( 0 , + ∞ ) and its physical meaning is work of applied forces at the equilibrium state. The function ? is continuous, nondecreasing and its values tend to ? l i m as α ? + ∞ . Reduction of the problem to a finit…
A comparison of efficient methods for the computation of Born gluon amplitudes
2006
We compare four different methods for the numerical computation of the pure gluonic amplitudes in the Born approximation. We are in particular interested in the efficiency of the various methods as the number n of the external particles increases. In addition we investigate the numerical accuracy in critical phase space regions. The methods considered are based on (i) Berends-Giele recurrence relations, (ii) scalar diagrams, (iii) MHV vertices and (iv) BCF recursion relations.
Quasi-Modes in Higher Dimension
2019
Recall that if a(x, ξ) and b(x, ξ) are two C1-functions defined on some domain in \({\mathbf {R}}^{2n}_{x,\xi }\), then we can define the Poisson bracket to be the C0-function on the same domain given by $$\displaystyle \{ a,b\} =a^{\prime }_\xi \cdot b^{\prime }_x-a^{\prime }_x \cdot b^{\prime }_\xi =H_a(b). $$ Here \(H_a=a^{\prime }_\xi \cdot \partial _x-a^{\prime }_x\cdot \partial _\xi \) denotes the Hamilton vector field of a. The following result is due to Zworski, who obtained it via a semi-classical reduction from the above mentioned result of Hormander. A direct proof was given in Dencker et al. and here we give a variant. We will assume some familiarity with symplectic geometry.
Visibly pushdown modular games,
2014
Games on recursive game graphs can be used to reason about the control flow of sequential programs with recursion. In games over recursive game graphs, the most natural notion of strategy is the modular strategy, i.e., a strategy that is local to a module and is oblivious to previous module invocations, and thus does not depend on the context of invocation. In this work, we study for the first time modular strategies with respect to winning conditions that can be expressed by a pushdown automaton. We show that such games are undecidable in general, and become decidable for visibly pushdown automata specifications. Our solution relies on a reduction to modular games with finite-state automat…
Pairs of solutions for Robin problems with an indefinite and unbounded potential, resonant at zero and infinity
2018
We consider a semilinear Robin problem driven by the Laplacian plus an indefinite and unbounded potential and a Caratheodory reaction term which is resonant both at zero and $$\pm \infty $$ . Using the Lyapunov–Schmidt reduction method and critical groups (Morse theory), we show that the problem has at least two nontrivial smooth solutions.
A novel integral representation for the Adler function
2005
New integral representations for the Adler D-function and the R-ratio of the electron-positron annihilation into hadrons are derived in the general framework of the analytic approach to QCD. These representations capture the nonperturbative information encoded in the dispersion relation for the D-function, the effects due to the interrelation between spacelike and timelike domains, and the effects due to the nonvanishing pion mass. The latter plays a crucial role in this analysis, forcing the Adler function to vanish in the infrared limit. Within the developed approach the D-function is calculated by employing its perturbative approximation as the only additional input. The obtained result …