Zobrazeno 1 - 10
of 70
pro vyhledávání: '"LACHISH, ODED"'
A tournament is an orientation of a complete graph. We say that a vertex $x$ in a tournament $\vec T$ controls another vertex $y$ if there exists a directed path of length at most two from $x$ to $y$. A vertex is called a king if it controls every ve
Externí odkaz:
http://arxiv.org/abs/2209.12082
Answering connectivity queries is fundamental to fully dynamic graphs where edges and vertices are inserted and deleted frequently. Existing work proposes data structures and algorithms with worst-case guarantees. We propose a new data structure, the
Externí odkaz:
http://arxiv.org/abs/2207.06887
Publikováno v:
SIAM J. Comput., 52 (2023), pp. 1413-1463
We prove a general structural theorem for a wide family of local algorithms, which includes property testers, local decoders, and PCPs of proximity. Namely, we show that the structure of every algorithm that makes $q$ adaptive queries and satisfies a
Externí odkaz:
http://arxiv.org/abs/2010.04985
Autor:
Gur, Tom, Lachish, Oded
A locally decodable code (LDC) C:{0,1}^k -> {0,1}^n is an error correcting code wherein individual bits of the message can be recovered by only querying a few bits of a noisy codeword. LDCs found a myriad of applications both in theory and in practic
Externí odkaz:
http://arxiv.org/abs/1904.08112
We prove almost tight bounds on the length of paths in $2$-edge-connected cubic graphs. Concretely, we show that (i) every $2$-edge-connected cubic graph of size $n$ has a path of length $\Omega\left(\frac{\log^2{n}}{\log{\log{n}}}\right)$, and (ii)
Externí odkaz:
http://arxiv.org/abs/1903.02508
We present ongoing work on a tool that consists of two parts: (i) A raw micro-level abstract world simulator with an interface to (ii) a 3D game engine, translator of raw abstract simulator data to photorealistic graphics. Part (i) implements a dedic
Externí odkaz:
http://arxiv.org/abs/1711.07951
Distribution testing deals with what information can be deduced about an unknown distribution over $\{1,\ldots,n\}$, where the algorithm is only allowed to obtain a relatively small number of independent samples from the distribution. In the extended
Externí odkaz:
http://arxiv.org/abs/1609.06736
Autor:
Lachish, Oded, Razgon, Igor
In this paper we establish an exponential lower bound on the size of syntactic non-deterministic read $d$-times branching programs for $d \leq \log n /10^5$ computing a class of monotone CNFs with a linear number of clauses. This result provides the
Externí odkaz:
http://arxiv.org/abs/1604.01560
We show here that every non-adaptive property testing algorithm making a constant number of queries, over a fixed alphabet, can be converted to a sample-based (as per [Goldreich and Ron, 2015]) testing algorithm whose average number of queries is a f
Externí odkaz:
http://arxiv.org/abs/1504.00695
Autor:
Lachish, Oded
In the \textit{Matroid Secretary Problem} (MSP), the elements of the ground set of a Matroid are revealed on-line one by one, each together with its value. An algorithm for the MSP is \textit{Matroid-Unknown} if, at every stage of its execution: (i)
Externí odkaz:
http://arxiv.org/abs/1403.7343