Search

In this paper we consider the multidimensional binary vector assignment problem. An input of this problem is defined by m disjoint multisets $$V^1, V^2, \ldots , V^m$$ , each composed of n binary vectors of size p. An output is a set of n disjoint m-tuples of vectors, where each m-tuple is obtained by picking one vector from each multiset $$V^i$$ . To each m-tuple we associate a p dimensional vector by applying the bit-wise AND operation on the m vectors of the tuple. The objective is to minimize the total number of zeros in these n vectors. We denote this problem by , and the restriction of this problem where every vector has at most c zeros by . was only known to be -hard, even for . We show that, assuming the unique games conjecture, it is -hard to -approximate for any fixed and . This result is tight as any solution is a -approximation. We also prove without assuming UGC that is -hard even for . Finally, we show that is polynomial-time solvable for fixed (which cannot be extended to ).

The paper studies compactness properties of the affine Sobolev inequality of Lutwak et al. (J Differ Geom 62:17–38, 2002) and Zhang (J Differ Geom 53:183–202, 1999) in the case $$p=2$$ , and existence and regularity of related minimizers, in particular, solutions to the nonlocal Dirichlet problems $$\begin{aligned} -\sum _{i,j=1}^{N}(A^{-1}[u])_{ij}\frac{\partial ^2u}{\partial x_i\partial x_j}=f \text{ in } \Omega \subset {\mathbb {R}}^N, \end{aligned}$$ and $$\begin{aligned} -\sum _{i,j=1}^{N}(A^{-1}[u])_{ij}\frac{\partial ^2u}{\partial x_i\partial x_j}=u^{q-1},\quad u>0, \text{ in } \Omega \subset {\mathbb {R}}^N, \end{aligned}$$ where $$A_{ij}[u]=\int _\Omega \frac{\partial u}{\partial x_i}\frac{\partial u}{\partial x_j}{\mathrm {d}}{x}$$ and $$q\in (2,\frac{2N}{N-2})$$ .

Let S be a finite set of primes, p in S, and Q_S a maximal algebraic extension of Q unramified outside S and infinity. Assume that |S|>=2. We show that the natural maps Gal(Q_p^bar/Q_p) --> Gal(Q_S/Q) are injective. Much of the paper is devoted to the problem of constructing selfdual automorphic cuspidal representations of GL(2n,A_Q) with prescribed properties at all places, that we study via the twisted trace formula of J. Arthur. The techniques we develop shed also some lights on the orthogonal/symplectic alternative for selfdual representations of GL(2n)., 50 pages, french. Section 4.18 has been extended : let F be a totally real field and \pi a selfdual cuspidal automorphic representation of GL(2n,A_F) which is cohomological at all the archimedean places and discrete at a finite place at least, we show that for each place v the L-parameter of \pi_v preserves a non-degenerate symplectic pairing

International audience; An integer n is called friable when its prime number factorization consists exclusively of (relatively) small factors. Let P(n) be the largest prime factor occurring in this factorization, and let S(x,y) denote the set {n? x,P(n)? y}. This work investigates the asymptotic behaviour of the summatory function Psi_f(x, y):=\sum_{n\in S(x,y)}f(n) when f is a multiplicative arithmetical function satisfying some simple and general conditions concerning its mean behaviour on primes and on powers of primes. One such condition is |\sum_{p? z}f(p)\log p-\kappa z|? Cz/R(z) (z>1), where C is a constant and \kappa>0; requirements on R are technical conditions too long to state here, but satisfied by any "reasonable" positive increasing function. By setting R(z)=(\log z)^\delta in the very general Théorème 2.1, the authors obtain a more general as well as more precise estimate on \Psi_f(x, y) (Corollaire 2.2) than that recently obtained by J. M. Song [Acta Arith. 102 (2002), no. 2, 105--129; MR1889623 (2003a:11123)]. Their next result (Corollaire 2.3) offers a general estimate in the case where f(p) is on average very close to a constant, and contains without loss of precision estimates of the literature for particular functions f, such as the so-called Piltz functions \tau_k, or the function µ^2 where µ is the Möbius function. Then, as a further application of their first result, they establish an Erdös-Wintner theorem on friable integers (Théorème 2.4). They finally mention an application to the case where f(n) is the characteristic function of the integers that can be represented as a sum of two squares of integers (Théorème 2.5); their estimate is uniformly valid for x ? 3, exp((\log x)^{2/5+\epsilon})? y? x. The paper begins with an historical introduction, and is followed by an extensive bibliography on the subject.