Tomas Feder, Rajeev Motwani, An Zhu

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 >>>

Abhishek Bhowmick, Shachar Lovett

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 >>>

Abhishek Bhrushundi, Prahladh Harsha, Srikanth Srinivasan

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 >>>