A fixed point approach to stability of a quadratic equation

Using the fixed point alternative theorem we establish the orthogonal stability of the quadratic functional equation of Pexider type f (x+y)+g(x−y) = h(x)+k(y), where f, g, h, k are mappings from a symmetric orthogonality space to a Banach space, by orthogonal additive mappings under a necessary and sufficient condition on f.     

Decomposer and associative functional equations

In the previous researches [2,3] b-integer and b-decimal parts of real numbers were introduced and studied by M.H. Hooshmand. The b-parts real functions have many interesting number theoretic explanations, analytic and algebraic properties, and satisfy the functional equation f (f(x) + y - f(y)) = f(x). These functions have led him to a more general topic in semigroups and groups (even in an arbitrary set with a binary operation [4] and the following functional equations have been introduced: Associative equations:

f(xf(yz))=f(f(xy)z),f(xf(yz))=f(f(xy)z)=f(xyz)

. Decomposer equations:

f(f^*(x)f(y))=f(y),f(f(x)f_*(y))=f(x)

.Strong decomposer equations:

f(f^*(x)y)=f(y),f(xf_*(y))=f(x)

.Canceler equations:

f(f(x)y)=f(xy),f(xf(y))=f(xy),f(xf(y)z)=f(xyz)

, where f^*(x) f(x) = f (x) f_* (x) = x. In this paper we solve them and introduce the general solution of the decomposer and strong decomposer equations in the sets with a binary operation and semigroups respectively and also associative equations in arbitrary groups. Moreover we state some equivalent equations to them and study the relations between the above equations. Finally we prove that the associative equations and the system of strong decomposer and canceler equations do not have any nontrivial solutions in the simple groups.     

Nonvanishing derivatives and normal families

We consider the differential operators Ψ _k , defined by Ψ₁(y) =y and Ψ _k+1(y)=yΨ _k y+d/dz(Ψ _k (y)) fork ∈ ℕ fork∈ ℕ. We show that ifF is meromorphic in ℂ and Ψ _k F has no zeros for somek≥3, and if the residues at the simple poles ofF are not positive integers, thenF has the formF(z)=((k-1)z+a)/(z ²+β z+γ) orF(z)=1/(az+β) where α, β, γ ∈ ℂ. If the residues at the simple poles ofF are bounded away from zero, then this also holds fork=2. We further show that, under suitable additional conditions, a family of meromorphic functionsF is normal if each Ψ _k (F) has no zeros. These conditions are satisfied, in particular, if there exists δ>0 such that Re (Res(F, a)) <−δ for all polea of eachF in the family. Using the fact that Ψ _k (f ^′/f) =f ^(k)/f, we deduce in particular that iff andf ^(k) have no zeros for allf in some familyF of meromorphic functions, wherek≥2, then {f ^′/f :f ∈F} is normal. The first author is supported by the German-Israeli Foundation for Scientific Research and Development G.I.F., G-643-117.6/1999, and INTAS-99-00089. The second author thanks the DAAD for supporting a visit to Kiel in June–July 2002. Both authors thank Günter Frank for helpful discussions.     

Existence and Uniqueness of Strong Solutions for a Class of Quasi‐Linear Hyperbolic Equations with Order Degeneration

Let k(y) > 0, 𝓁(y) > 0 for y > 0, k(0) = 𝓁(0) = 0 and lim_{y → 0}k(y)/𝓁(y) exists; then the equation L(u) ≔ k(y)u_xx – ∂_y(𝓁(y)u_y) + a(x, y)u_x = f(x, y, u) is strictly hyperbolic for y > 0 and its order degenerates on the line y = 0. Consider the boundary value problem Lu = f(x, y, u) in G, u|_AC = 0, where G is a simply connected domain in ℝ² with piecewise smooth boundary ∂G = AB∪AC∪BC; AB = {(x, 0) : 0 ≤ x ≤ 1}, AC : x = F(y) = ∫^y₀(k(t)/𝓁(t))^1/2dt and BC : x = 1 – F(y) are characteristic curves. Existence of generalized solution is obtained by a finite element method, provided f(x, y, u) satisfies Carathéodory condition and |f(x, y, u)| ≤ Q(x, y) + b|u| with Q ∈ L²(G), b = const > 0. It is shown also that each generalized solution is a strong solution, and that fact is used to prove uniqueness under the additional assumption |f(x, y, u₁) – f(x, y, u₂| ≤ C|u₁ – u₂|, where C = const > 0.     

A Generalized Cubic Functional Equation

In this paper, we determine the general solution of the functional equation f1 （2x ＋ y） ＋ f2（2x - y） = f3（x ＋ y） ＋ f4（x - y） ＋ f5（x） without assuming any regularity condition on the unknown functions f1,f2,f3, f4, f5 ： R→R. The general solution of this equation is obtained by finding the general solution of the functional equations f（2x ＋ y） ＋ f（2x - y） = g（x ＋ y） ＋ g（x - y） ＋ h（x） and f（2x ＋ y） - f（2x - y） = g（x ＋ y） - g（x - y）. The method used for solving these functional equations is elementary but exploits an important result due to Hosszfi. The solution of this functional equation can also be determined in certain type of groups using two important results due to Szekelyhidi.     

On the Complexity of Computing Error Bounds

We consider the cost of estimating an error bound for the computed solution of a system of linear equations, i.e., estimating the norm of a matrix inverse. Under some technical assumptions we show that computing even a coarse error bound for the solution of a triangular system of equations costs at least as much as testing whether the product of two matrices is zero. The complexity of the latter problem is in turn conjectured to be the same as matrix multiplication, matrix inversion, etc. Since most error bounds in practical use have much lower complexity, this means they should sometimes exhibit large errors. In particular, it is shown that condition estimators that: (1) perform at least one operation on each matrix entry; and (2) are asymptotically faster than any zero tester, must sometimes over or underestimate the inverse norm by a factor of at least , where n is the dimension of the input matrix, k is the bitsize, and where either or grows faster than any polynomial in n . Our results hold for the RAM model with bit complexity, as well as computations over rational and algebraic numbers, but not real or complex numbers. Our results also extend to estimating error bounds or condition numbers for other linear algebra problems such as computing eigenvectors. September 10, 1999. Final version received: August 23, 2000.     

The Hardness of 3-Uniform Hypergraph Coloring

We prove that coloring a 3-uniform 2-colorable hypergraph with c colors is NP-hard for any constant c. The best known algorithm [20] colors such a graph using O(n^1/5) colors. Our result immediately implies that for any constants k ≥ 3 and c₂ > c₁ > 1, coloring a k-uniform c₁-colorable hypergraph with c₂ colors is NP-hard; the case k = 2, however, remains wide open. This is the first hardness result for approximately-coloring a 3-uniform hypergraph that is colorable with a constant number of colors. For k ≥ 4 such a result has been shown by [14], who also discussed the inherent difference between the k = 3 case and k ≥ 4. Our proof presents a new connection between the Long-Code and the Kneser graph, and relies on the high chromatic numbers of the Kneser graph [19,22] and the Schrijver graph [26]. We prove a certain maximization variant of the Kneser conjecture, namely that any coloring of the Kneser graph by fewer colors than its chromatic number, has ‘many’ non-monochromatic edges. * Research supported by NSF grant CCR-9987845. † Supported by an Alon Fellowship and by NSF grant CCR-9987845. ‡ Work supported in part by NSF grants CCF-9988526 and DMS 9729992, and the State of New Jersery.     

Disjoint bases in a polymatroid

Let f : 2^N → ⁺ be a polymatroid (an integer‐valued non‐decreasing submodular set function with f(??) = 0). We call S ? N a base if f(S) = f(N). We consider the problem of finding a maximum number of disjoint bases; we denote by m* be this base packing number. A simple upper bound on m* is given by k* = max{k : Σ_iεNf_A(i) ≥ kf_A(N),?A ? N} where f_A(S) = f(A ∪ S) ‐ f(A). This upper bound is a natural generalization of the bound for matroids where it is known that m* = k*. For polymatroids, we prove that m* ≥ (1 ? o(1))k*/lnf(N) and give a randomized polynomial time algorithm to find (1 ? o(1))k*/lnf(N) disjoint bases, assuming an oracle for f. We also derandomize the algorithm using minwise independent permutations and give a deterministic algorithm that finds (1 ? ε)k*/lnf(N) disjoint bases. The bound we obtain is almost tight because it is known there are polymatroids for which m* < (1 + o(1))k*/lnf(N). Moreover it is known that unless NP ? DTIME(n^{log log n}), for any ε > 0, there is no polynomial time algorithm to obtain a (1 + ε)/lnf(N)‐approximation to m*. Our result generalizes and unifies two results in the literature. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

On the Knowledge Complexity of

We show that if a language has an interactive proof of logarithmic statistical knowledge-complexity, then it belongs to the class . Thus, if the polynomial time hierarchy does not collapse, then -complete languages do not have logarithmic knowledge complexity. Prior to this work, there was no indication that would contradict languages being proven with even one bit of knowledge. Our result is a common generalization of two previous results: The first asserts that statistical zero knowledge is contained in [11, 2], while the second asserts that the languages recognizable in logarithmic statistical knowledge complexity are in [19]. Next, we consider the relation between the error probability and the knowledge complexity of an interactive proof. Note that reducing the error probability via repetition is not free: it may increase the knowledge complexity. We show that if the negligible error probability is less than (where k(n) is the knowledge complexity) then the language proven is in the third level of the polynomial time hierarchy (specifically, it is in ). In the standard setting of negligible error probability, there exist PSPACE-complete languages which have sub-linear knowledge complexity. However, if we insist, for example, that the error probability is less than , then PSPACE-complete languages do not have sub-quadratic knowledge complexity, unless . In order to prove our main result, we develop an AM protocol for checking that a samplable distribution D has a given entropy h. For any fractions , the verifier runs in time polynomial in and and fails with probability at most to detect an additive error in the entropy. We believe that this protocol is of independent interest. Subsequent to our work Goldreich and Vadhan [16] established that the problem of comparing the entropies of two samplable distributions if they are noticeably different is a natural complete promise problem for the class of statistical zero knowledge (). Received January 6, 2000 RID=" " ID=" " This research was performed while the authors were visiting the Computer Science Department at the University of Toronto, preliminary version of this paper appeared in [27] RID="*" ID="*" Partially supported by Technion V. P. R. Found––N. Haar and R. Zinn Research Fund. RID="†" ID="†" Partially supported by the grants OTKA T-029255, T-030059, FKFP 0607/1999, and AKP 2000-78 2.1.     

Separation of the Monotone NC Hierarchy

, for the monotone depth of functions in monotone-P. As a result we achieve the separation of the following classes. 1. monotone-NC ≠ monotone-P. 2. For every i≥1, monotone-≠ monotone-. 3. More generally: For any integer function D(n), up to (for some ε>0), we give an explicit example of a monotone Boolean function, that can be computed by polynomial size monotone Boolean circuits of depth D(n), but that cannot be computed by any (fan-in 2) monotone Boolean circuits of depth less than Const·D(n) (for some constant Const). Only a separation of monotone- from monotone- was previously known. Our argument is more general: we define a new class of communication complexity search problems, referred to below as DART games, and we prove a tight lower bound for the communication complexity of every member of this class. As a result we get lower bounds for the monotone depth of many functions. In particular, we get the following bounds: 1.  For st-connectivity, we get a tight lower bound of . That is, we get a new proof for Karchmer–Wigderson's theorem, as an immediate corollary of our general result. 2.  For the k-clique function, with , we get a tight lower bound of Ω(k log n). This lower bound was previously known for k≤ log n [1]. For larger k, however, only a bound of Ω(k) was previously known. Received: December 19, 1997     

The unbounded-error communication complexity of symmetric functions

We prove an essentially tight lower bound on the unbounded-error communication complexity of every symmetric function, i.e., f(x,y)=D(|x∧y|), where D: {0,1,…,n}→{0,1} is a given predicate and x,y range over {0,1} ⁿ . Specifically, we show that the communication complexity of f is between Θ(k/log⁵ n) and Θ(k logn), where k is the number of value changes of D in {0,1,…, n}. Prior to this work, the problem was solved only for the parity predicate D (Forster 2001).     

Improved bounds on the max-flow min-cut ratio for multicommodity flows

In this paper we consider the worst case ratio between the capacity of min-cuts and the value of max-flow for multicommodity flow problems. We improve the best known bounds for the min-cut max-flow ratio for multicommodity flows in undirected graphs, by replacing theO(logD) in the bound byO(logk), whereD denotes the sum of all demands, andk demotes the number of commodities. In essence we prove that up to constant factors the worst min-cut max-flow ratios appear in problems where demands are integral and polynomial in the number of commodities.Klein, Rao, Agrawal, and Ravi have previously proved that if the demands and the capacities are integral, then the min-cut max-flow ratio in general undirected graphs is bounded byO(logClogD), whereC denotes the sum of all the capacities. Tragoudas has improved this bound toO(lognlogD), wheren is the number of nodes in the network. Garg, Vazirani and Yannakakis further improved this toO(logklogD). Klein, Plotkin and Rao have proved that for planar networks, the ratio isO(logD).Our result improves the bound for general networks toO(log² k) and the bound for planar networks toO(logk). In both cases our result implies the first non-trivial bound that is independent of the magnitude of the numbers involved. The method presented in this paper can be used to give polynomial time approximation algorithms to the minimum cuts in the network up to the above factors.Preliminary version appeared in Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, 1993, 691-697.Research supported by U.S. Army Research Office Grant DAAL-03-91-G-0102, and by a grant from Mitsubishi Electric Laboratories.Research supported in part by a Packard Fellowship, an NSF PYI award, a Sloan Fellowship, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

Testing Monotonicity

at arguments of its choice, the test always accepts a monotone f, and rejects f with high probability if it is ε-far from being monotone (i.e., every monotone function differs from f on more than an ε fraction of the domain). The complexity of the test is O(n/ε). The analysis of our algorithm relates two natural combinatorial quantities that can be measured with respect to a Boolean function; one being global to the function and the other being local to it. A key ingredient is the use of a switching (or sorting) operator on functions. Received March 29, 1999     

On The Parameterized Intractability Of Motif Search Problems*

We show that Closest Substring, one of the most important problems in the field of consensus string analysis, is W[1]-hard when parameterized by the number k of input strings (and remains so, even over a binary alphabet). This is done by giving a “strongly structure-preserving” reduction from the graph problem Clique to Closest Substring. This problem is therefore unlikely to be solvable in time O(f(k)•n^c) for any function f of k and constant c independent of k, i.e., the combinatorial explosion seemingly inherent to this NP-hard problem cannot be restricted to parameter k. The problem can therefore be expected to be intractable, in any practical sense, for k ≥ 3. Our result supports the intuition that Closest Substring is computationally much harder than the special case of Closest String, althoughb othp roblems are NP-complete. We also prove W[1]-hardness for other parameterizations in the case of unbounded alphabet size. Our W[1]-hardness result for Closest Substring generalizes to Consensus Patterns, a problem arising in computational biology. * An extended abstract of this paper was presented at the 19th International Symposium on Theoretical Aspects of Computer Science (STACS 2002), Springer-Verlag, LNCS 2285, pages 262–273, held in Juan-Les-Pins, France, March 14–16, 2002. † Work was supported by the Deutsche Forschungsgemeinschaft (DFG), research project “OPAL” (optimal solutions for hard problems in computational biology), NI 369/2. ‡ Work was done while the author was with Wilhelm-Schickard-Institut für Informatik, Universit?t Tübingen. Work was partially supported by the Deutsche Forschungsgemeinschaft (DFG), Emmy Noether research group “PIAF” (fixed-parameter algorithms), NI 369/4.     

Applications of matrix methods to the theory of lower bounds in computational complexity

We present some criteria for obtaining lower bounds for the formula size of Boolean functions. In the monotone case we get the boundn ^(logn) for the function MINIMUM COVER using methods considerably simpler than all previously known. In the general case we are only able to prove that the criteria yield an exponential lower bound when applied to almost all functions. Some connections with graph complexity and communication complexity are also given.     

The Cost of the Missing Bit: Communication Complexity with Help

Dedicated to the Memory of Paul Erdős We generalize the multiparty communication model of Chandra, Furst, and Lipton (1983) to functions with b-bit output (b = 1 in the CFL model). We allow the players to receive up to b - 1 bits of information from an all-powerful benevolent Helper who can see all the input. Extending results of Babai, Nisan, and Szegedy (1992) to this model, we construct families of explicit functions for which bits of communication are required to find the "missing bit", where n is the length of each player's input and k is the number of players. As a consequence we settle the problem of separating the one-way vs. multiround communication complexities (in the CFL sense) for players, extending a result of Nisan and Wigderson (1991) who demonstrated this separation for k = 3 players. As a by-product we obtain lower bounds for the multiparty complexity (in the CFL sense) of new families of explicit boolean functions (not derivable from BNS). The proofs exploit the interplay between two concepts of multicolor discrepancy; discrete Fourier analysis is the basic tool. We also include an unpublished lower bound by A. Wigderson regarding the one-way complexity of the 3-party pointer jumping function. Received November 12, 1998 RID="*" ID="*" Supported in part by NSA grant MSPR-96G-184. RID="†" ID="†" Supported in part by an NSF Graduate Fellowship.     

The complexity of computing the tutte polynomial on transversal matroids

The complexity of computing the Tutte polynomialT(M,x,y) is determined for transversal matroidM and algebraic numbersx andy. It is shown that for fixedx andy the problem of computingT(M,x,y) forM a transversal matroid is #P-complete unless the numbersx andy satisfy (x−1)(y−1)=1, in which case it is polynomial-time computable. In particular, the problem of counting bases in a transversal matroid, and of counting various types of “matchable” sets of nodes in a bipartite graph, is #P-complete.     

Non-Separating Paths in 4-Connected Graphs

In 1975, Lovász conjectured that for any positive integer k, there exists a minimum positive integer f(k) such that, for any two vertices x, y in any f(k)-connected graph G, there is a path P from x to y in G such that G–V(P) is k-connected. A result of Tutte implies f(1) = 3. Recently, f(2) = 5 was shown by Chen et al. and, independently, by Kriesell. In this paper, we show that f(2) = 4 except for double wheels.Received October 17, 2003     

New Coins From Old: Computing With Unknown Bias

Suppose that we are given a function f : (0, 1)→(0,1) and, for some unknown p∈(0, 1), a sequence of independent tosses of a p-coin (i.e., a coin with probability p of “heads”). For which functions f is it possible to simulate an f(p)-coin? This question was raised by S. Asmussen and J. Propp. A simple simulation scheme for the constant function f(p)≡1/2 was described by von Neumann (1951); this scheme can be easily implemented using a finite automaton. We prove that in general, an f(p)-coin can be simulated by a finite automaton for all p ∈ (0, 1), if and only if f is a rational function over ℚ. We also show that if an f(p)-coin can be simulated by a pushdown automaton, then f is an algebraic function over ℚ; however, pushdown automata can simulate f(p)-coins for certain nonrational functions such as . These results complement the work of Keane and O’Brien (1994), who determined the functions f for which an f(p)-coin can be simulated when there are no computational restrictions on the simulation scheme. * Supported by a Miller Fellowship. † Supported in part by NSF Grant DMS-0104073 and by a Miller Professorship. ‡ This work is supported under a National Science Foundation Graduate Research Fellowship.     

Solution and stability of generalized mixed type cubic, quadratic and additive functional equation in quasi-Banach spaces

In this paper, we achieve the general solution and the generalized Hyers–Ulam–Rassias stability of the following functional equation

f(x+ky)+f(x−ky)=k²f(x+y)+k²f(x−y)+2(1−k²)f(x)