ﻻ يوجد ملخص باللغة العربية
We prove new upper bounds on the size of families of vectors in $Z_m^n$ with restricted modular inner products, when $m$ is a large integer. More formally, if $vec{u}_1,ldots,vec{u}_t in Z_m^n$ and $vec{v}_1,ldots,vec{v}_t in Z_m^n$ satisfy $langlevec{u}_i,vec{v}_irangleequiv0pmod m$ and $langlevec{u}_i,vec{v}_jrangle otequiv0pmod m$ for all $i eq jin[t]$, we prove that $t leq O(m^{n/2+8.47})$. This improves a recent bound of $t leq m^{n/2 + O(log(m))}$ by cite{BDL13} and is the best possible up to the constant 8.47 when $m$ is sufficiently larger than $n$. The maximal size of such families, called `Matching-Vector families, shows up in recent constructions of locally decodable error correcting codes (LDCs) and determines the rate of the code. Using our result we are able to show that these codes, called Matching-Vector codes, must have encoding length at least $K^{19/18}$ for $K$-bit messages, regardless of their query complexity. This improves a known super linear bound of $ K2^{Omega({sqrt{log K}})}$ proved in cite{DGY11}.
A path in an(a) edge(vertex)-colored graph is called emph{a conflict-free path} if there exists a color used on only one of its edges(vertices). An(A) edge(vertex)-colored graph is called emph{conflict-free (vertex-)connected} if there is a conflict-
We establish a list of characterizations of bounded twin-width for hereditary, totally ordered binary structures. This has several consequences. First, it allows us to show that a (hereditary) class of matrices over a finite alphabet either contains
The well-known Disjoint Paths problem is to decide if a graph contains k pairwise disjoint paths, each connecting a different terminal pair from a set of k distinct pairs. We determine, with an exception of two cases, the complexity of the Disjoint P
We study the dominating set reconfiguration problem with the token sliding rule. It consists, given a graph G=(V,E) and two dominating sets D_s and D_t of G, in determining if there exists a sequence S=<D_1:=D_s,...,D_l:=D_t> of dominating sets of G
This report documents the program and the outcomes of Dagstuhl Seminar 13082 Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices, held in February 2013 at Dagstuhl Castle.