We consider the problem of finding a k-vertex (k-edge)
connected spanning subgraph K of a given n-vertex graph G
while minimizing the maximum degree d in K. We give a
polynomial time algorithm for fixed k that achieves an O(\log n)-approximation. The only known previous polynomial algorithms
achieved degree d+1 ...
more >>>
The problem of constructing explicit functions which cannot be approximated by low degree polynomials has been extensively studied in computational complexity, motivated by applications in circuit lower bounds, pseudo-randomness, constructions of Ramsey graphs and locally decodable codes. Still, most of the known lower bounds become trivial for polynomials of ...
more >>>
We study approximation of Boolean functions by low-degree polynomials over the ring \mathbb{Z}/2^k\mathbb{Z}. More precisely, given a Boolean function F:\{0,1\}^n \rightarrow \{0,1\}, define its k-lift to be F_k:\{0,1\}^n \rightarrow \{0,2^{k-1}\} by F_k(x) = 2^{k-F(x)} (mod 2^k). We consider the fractional agreement (which we refer to as \gamma_{d,k}(F)) of F_k with ... more >>>
Time efficient decoding algorithms for error correcting codes often require linear space. However, locally decodable codes yield more efficient randomized decoders that run in time n^{1+o(1)} and space n^{o(1)}. In this work we focus on deterministic decoding.
Gronemeier showed that any non-adaptive deterministic decoder for a good code running ...
more >>>