Search results for "PROB"
showing 10 items of 8859 documents
Integer Complexity: Experimental and Analytical Results II
2015
We consider representing natural numbers by expressions using only 1’s, addition, multiplication and parentheses. Let \( \left\| n \right\| \) denote the minimum number of 1’s in the expressions representing \(n\). The logarithmic complexity \( \left\| n \right\| _{\log } \) is defined to be \({ \left\| n \right\| }/{\log _3 n}\). The values of \( \left\| n \right\| _{\log } \) are located in the segment \([3, 4.755]\), but almost nothing is known with certainty about the structure of this “spectrum” (are the values dense somewhere in the segment?, etc.). We establish a connection between this problem and another difficult problem: the seemingly “almost random” behaviour of digits in the ba…
Parabolic Equations Minimizing Linear Growth Functionals: L1-Theory
2004
Let Ω be a bounded set in ℝN with boundary of class C1. We are interested in the problem $$ \left\{ \begin{gathered} \frac{{\partial u}} {{\partial t}} = diva\left( {x,Du} \right)in Q = \left( {0,\infty } \right) \times \Omega , \hfill \\ u\left( {t,x} \right) = \phi \left( x \right)on S = \left( {0,\infty } \right) \times \partial \Omega , \hfill \\ u\left( {0,x} \right) = u_0 \left( x \right)in x \in \Omega \hfill \\ \end{gathered} \right. $$ (1) where ϕ ∈ L1(∂Ω), u0 ∈ L2(Ω) and a(x, ξ) = ∇ξ f(x, ξ, f being a function with linear growth in ‖ξ‖ as ‖ξ‖ → ∞. One of the classical examples is the nonparametric area integrand for which \( f(x,\xi ) = \sqrt {1 + \left\| \xi \right\|^2 } \). Prob…
On Some Properties of the Dirichlet Problem at Resonance
2008
Abstract The boundary value problem at resonance 𝑥″ + 𝑥 = 𝑞 sin 𝑡 + 𝑓(𝑡,𝑥,𝑥′), 𝑥(0) = 0, 𝑥(π) = 0, is considered, where 𝑓 : [0,π] × 𝑹2 → 𝑹 is a bounded Carathéodory function, 𝑞 is a parameter. We state the multiplicity results without assuming that 𝑓 has limits.
Estimating norms inC*-algebras of discrete groups
1976
LetG be a discrete group, letK be a finite subset ofG and let χ K be the characteristic function ofK. Then χ K acts by convolution as a bounded operator onL2(G). We will prove that the norm |||χ K ||| of this operator always satisfies the following estimate: $$|||\chi _{\rm K} |||^2 \leqq k + 2\sqrt {w\left( {k - 1} \right)\left( {k - w} \right)} + \left( {k - 2} \right)\left( {k - w} \right)$$ . Here .
Almost Tight Bound for the Union of Fat Tetrahedra in Three Dimensions
2007
For any AND-OR formula of size N, there exists a bounded-error N1/2+o(1)-time quantum algorithm, based on a discrete-time quantum walk, that evaluates this formula on a black-box input. Balanced, or "approximately balanced," formulas can be evaluated in O(radicN) queries, which is optimal. It follows that the (2-o(1))th power of the quantum query complexity is a lower bound on the formula size, almost solving in the positive an open problem posed by Laplante, Lee and Szegedy.
Improved Constructions of Quantum Automata
2008
We present a simple construction of quantum automata which achieve an exponential advantage over classical finite automata. Our automata use $\frac{4}{\epsilon} \log 2p + O(1)$ states to recognize a language that requires p states classically. The construction is both substantially simpler and achieves a better constant in the front of logp than the previously known construction of [2]. Similarly to [2], our construction is by a probabilistic argument. We consider the possibility to derandomize it and present some preliminary results in this direction.
Span programs for functions with constant-sized 1-certificates
2012
Besides the Hidden Subgroup Problem, the second large class of quantum speed-ups is for functions with constant-sized 1-certificates. This includes the OR function, solvable by the Grover algorithm, the element distinctness, the triangle and other problems. The usual way to solve them is by quantum walk on the Johnson graph. We propose a solution for the same problems using span programs. The span program is a computational model equivalent to the quantum query algorithm in its strength, and yet very different in its outfit. We prove the power of our approach by designing a quantum algorithm for the triangle problem with query complexity O(n35/27) that is better than O(n13/10) of the best p…
Enlarging the gap between quantum and classical query complexity of multifunctions
2013
Quantum computing aims to use quantum mechanical effects for the efficient performance of computational tasks. A popular research direction is enlarging the gap between classical and quantum algorithm complexity of the same computational problem. We present new results in quantum query algorithm design for multivalued functions that allow to achieve a large quantum versus classical complexity separation. To compute a basic finite multifunction in a quantum model only one query is enough while classically three queries are required. Then, we present two generalizations and a modification of the original algorithm, and obtain the following complexity gaps: Q UD (M′) ≤ N versus C UD (M′) ≥ 3N,…
Pattern Matching and Pattern Discovery Algorithms for Protein Topologies
2001
We describe algorithms for pattern-matching and pattern-learning in TOPS diagrams (formal descriptions of protein topologies). These problems can be reduced to checking for subgraph isomorphism and finding maximal common subgraphs in a restricted class of ordered graphs. We have developed a subgraph isomorphism algorithm for ordered graphs, which performs well on the given set of data. The maximal common subgraph problem then is solved by repeated subgraph extension and checking for isomorphisms. Despite its apparent inefficiency, this approach yields an algorithm with time complexity proportional to the number of graphs in the input set and is still practical on the given set of data. As a…
On the decision problem for the guarded fragment with transitivity
2002
The guarded fragment with transitive guards, [GF+TG], is an extension of GF in which certain relations are required to be transitive, transitive predicate letters appear only in guards of the quantifiers and the equality symbol may appear everywhere. We prove that the decision problem for [GF+TG] is decidable. This answers the question posed in (Ganzinger et al., 1999). Moreover, we show that the problem is 2EXPTIME-complete. This result is optimal since the satisfiability problem for GF is 2EXPTIME-complete (Gradel, 1999). We also show that the satisfiability problem for two-variable [GF+TG] is NEXPTIME-hard in contrast to GF with bounded number of variables for which the satisfiability pr…