Search results for "Combinatorics"

Sigma-fragmentability and the property SLD in C(K) spaces

2009

Abstract We characterize two topological properties in Banach spaces of type C ( K ) , namely, being σ-fragmented by the norm metric and having a countable cover by sets of small local norm-diameter (briefly, the property norm-SLD). We apply our results to deduce that C p ( K ) is σ-fragmented by the norm metric when K belongs to a certain class of Rosenthal compacta as well as to characterize the property norm-SLD in C p ( K ) in case K is scattered.

Remarks on Partially Square Graphs, Hamiltonicity and Circumference

2001

Quantum Query Complexity of Boolean Functions with Small On-Sets

2008

The main objective of this paper is to show that the quantum query complexity Q(f) of an N-bit Boolean function f is bounded by a function of a simple and natural parameter, i.e., M = |{x|f(x) = 1}| or the size of f's on-set. We prove that: (i) For $poly(N)\le M\le 2^{N^d}$ for some constant 0 < d < 1, the upper bound of Q(f) is $O(\sqrt{N\log M / \log N})$. This bound is tight, namely there is a Boolean function f such that $Q(f) = \Omega(\sqrt{N\log M / \log N})$. (ii) For the same range of M, the (also tight) lower bound of Q(f) is $\Omega(\sqrt{N})$. (iii) The average value of Q(f) is bounded from above and below by $Q(f) = O(\log M +\sqrt{N})$ and $Q(f) = \Omega (\log M/\log N+ \sqrt{N…

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.

Circuit Lower Bounds via Ehrenfeucht-Fraisse Games

2006

In this paper we prove that the class of functions expressible by first order formulas with only two variables coincides with the class of functions computable by AC/sup 0/ circuits with a linear number of gates. We then investigate the feasibility of using Ehrenfeucht-Fraisse games to prove lower bounds for that class of circuits, as well as for general AC/sup 0/ circuits.

Hamming, Permutations and Automata

2007

Quantum finite automata with mixed states are proved to be super-exponentially more concise rather than quantum finite automata with pure states. It was proved earlier by A.Ambainis and R.Freivalds that quantum finite automata with pure states can have exponentially smaller number of states than deterministic finite automata recognizing the same language. There was a never published "folk theorem" proving that quantum finite automata with mixed states are no more than superexponentially more concise than deterministic finite automata. It was not known whether the super-exponential advantage of quantum automata is really achievable. We prove that there is an infinite sequence of distinct int…

Super-Exponential Size Advantage of Quantum Finite Automata with Mixed States

2008

Quantum finite automata with mixed states are proved to be super-exponentially more concise rather than quantum finite automata with pure states. It was proved earlier by A.Ambainis and R.Freivalds that quantum finite automata with pure states can have exponentially smaller number of states than deterministic finite automata recognizing the same language. There was a never published "folk theorem" proving that quantum finite automata with mixed states are no more than super-exponentially more concise than deterministic finite automata. It was not known whether the super-exponential advantage of quantum automata is really achievable. We use a novel proof technique based on Kolmogorov complex…

The equidistribution of some Mahonian statistics over permutations avoiding a pattern of length three

2022

Abstract We prove the equidistribution of several multistatistics over some classes of permutations avoiding a 3-length pattern. We deduce the equidistribution, on the one hand of inv and foz e ″ statistics, and on the other hand that of maj and makl statistics, over these classes of pattern avoiding permutations. Here inv and maj are the celebrated Mahonian statistics, foz e ″ is one of the statistics defined in terms of generalized patterns in the 2000 pioneering paper of Babson and Steingrimsson, and makl is one of the statistics defined by Clarke, Steingrimsson and Zeng in (1997) [5] . These results solve several conjectures posed by Amini in (2018) [1] .

Saturated formations and products of connected subgroups

2011

Abstract For a non-empty class of groups C , two subgroups A and B of a group G are said to be C -connected if 〈 a , b 〉 ∈ C for all a ∈ A and b ∈ B . Given two sets π and ρ of primes, S π S ρ denotes the class of all finite soluble groups that are extensions of a normal π-subgroup by a ρ-group. It is shown that in a finite group G = A B , with A and B soluble subgroups, then A and B are S π S ρ -connected if and only if O ρ ( B ) centralizes A O π ( G ) / O π ( G ) , O ρ ( A ) centralizes B O π ( G ) / O π ( G ) and G ∈ S π ∪ ρ . Moreover, if in this situation A and B are in S π S ρ , then G is in S π S ρ . This result is then extended to a large family of saturated formations F , the so-c…

On the Quadratic Type of Some Simple Self-Dual Modules over Fields of Characteristic Two

1997

Let G be a finite group and let K be an algebraically closed field of Ž characteristic 2. Let V be a non-trivial simple self-dual KG-module we . say that V is self-dual if it is isomorphic to its dual V * . It is a theorem of w x Fong 4, Lemma 1 that in this case there is a non-degenerate G-invariant alternating bilinear form, F, say, defined on V = V. We say that V is a KG-module of quadratic type if F is the polarization of a non-degenerate w x G-invariant quadratic form defined on V. In a previous paper 6 , the present authors described some methods to decide if such a module V is of w x quadratic type. One of the main results of 6 is the following. Suppose that Ž . G is a group with a s…