اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe Grothendieck constant is strictly smaller than Krivines bound
43
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We prove that $K_G<frac{pi}{2log(1+sqrt{2})}$, where $K_G$ is the Grothendieck constant.
قيم البحث
اقرأ أيضاً
This paper proves strong lower bounds for distributed computing in the CONGEST model, by presenting the bit-gadget: a new technique for constructing graphs with small cuts. The contribution of bit-gadgets is twofold. First, developing careful spars
e graph constructions with small cuts extends known techniques to show a near-linear lower bound for computing the diameter, a result previously known only for dense graphs. Moreover, the sparseness of the construction plays a crucial role in applying it to approximations of various distance computation problems, drastically improving over what can be obtained when using dense graphs. Second, small cuts are essential for proving super-linear lower bounds, none of which were known prior to this work. In fact, they allow us to show near-quadratic lower bounds for several problems, such as exact minimum vertex cover or maximum independent set, as well as for coloring a graph with its chromatic number. Such strong lower bounds are not limited to NP-hard problems, as given by two simple graph problems in P which are shown to require a quadratic and near-quadratic number of rounds. All of the above are optimal up to logarithmic factors. In addition, in this context, the complexity of the all-pairs-shortest-paths problem is discussed. Finally, it is shown that graph constructions for CONGEST lower bounds translate to lower bounds for the semi-streaming model, despite being very different in its nature.
We present an algorithm for strongly refuting smoothed instances of all Boolean CSPs. The smoothed model is a hybrid between worst and average-case input models, where the input is an arbitrary instance of the CSP with only the negation patterns of t
he literals re-randomized with some small probability. For an $n$-variable smoothed instance of a $k$-arity CSP, our algorithm runs in $n^{O(ell)}$ time, and succeeds with high probability in bounding the optimum fraction of satisfiable constraints away from $1$, provided that the number of constraints is at least $tilde{O}(n) (frac{n}{ell})^{frac{k}{2} - 1}$. This matches, up to polylogarithmic factors in $n$, the trade-off between running time and the number of constraints of the state-of-the-art algorithms for refuting fully random instances of CSPs [RRS17]. We also make a surprising new connection between our algorithm and even covers in hypergraphs, which we use to positively resolve Feiges 2008 conjecture, an extremal combinatorics conjecture on the existence of even covers in sufficiently dense hypergraphs that generalizes the well-known Moore bound for the girth of graphs. As a corollary, we show that polynomial-size refutation witnesses exist for arbitrary smoothed CSP instances with number of constraints a polynomial factor below the spectral threshold of $n^{k/2}$, extending the celebrated result for random 3-SAT of Feige, Kim and Ofek [FKO06].
The main aim of the present work is to arrive at a mathematical theory close to the historically original conception of generalized functions, i.e. set theoretical functions defined on, and with values in, a suitable ring of scalars and sharing a num
ber of fundamental properties with smooth functions, in particular with respect to composition and nonlinear operations. This is how they are still used in informal calculations in Physics. We introduce a category of generalized functions as smooth set-theoretical maps on (multidimensional) points of a ring of scalars containing infinitesimals and infinities. This category extends Schwartz distributions. The calculus of these generalized functions is closely related to classical analysis, with point values, composition, non-linear operations and the generalization of several classical theorems of calculus. Finally, we extend this category of generalized functions into a Grothendieck topos of sheaves over a concrete site. This topos hence provides a suitable framework for the study of spaces and functions with singularities. In this first paper, we present the basic theory; subsequent ones will be devoted to the resulting theory of ODE and PDE.
The Bloom filter provides fast approximate set membership while using little memory. Engineers often use these filters to avoid slow operations such as disk or network accesses. As an alternative, a cuckoo filter may need less space than a Bloom filt
er and it is faster. Chazelle et al. proposed a generalization of the Bloom filter called the Bloomier filter. Dietzfelbinger and Pagh described a variation on the Bloomier filter that can be used effectively for approximate membership queries. It has never been tested empirically, to our knowledge. We review an efficient implementation of their approach, which we call the xor filter. We find that xor filters can be faster than Bloom and cuckoo filters while using less memory. We further show that a more compact version of xor filters (xor+) can use even less space than highly compact alternatives (e.g., Golomb-compressed sequences) while providing speeds competitive with Bloom filters.
We compute analytically the maximal rates of distillation of quantum coherence under strictly incoherent operations (SIO) and physically incoherent operations (PIO), showing that they coincide for all states, and providing a complete description of t
he phenomenon of bound coherence. In particular, we establish a simple, analytically computable necessary and sufficient criterion for the asymptotic distillability under SIO and PIO. We use this result to show that almost every quantum state is undistillable --- only pure states as well as states whose density matrix contains a rank-one submatrix allow for coherence distillation under SIO or PIO, while every other quantum state exhibits bound coherence. This demonstrates fundamental operational limitations of SIO and PIO in the resource theory of quantum coherence. We show that the fidelity of distillation of a single bit of coherence under SIO can be efficiently computed as a semidefinite program, and investigate the generalization of this result to provide an understanding of asymptotically achievable distillation fidelity.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
