Meena Mahajan, V Vinay

In this paper we approach the problem of computing the characteristic

polynomial of a matrix from the combinatorial viewpoint. We present

several combinatorial characterizations of the coefficients of the

characteristic polynomial, in terms of walks and closed walks of

different kinds in the underlying graph. We develop algorithms based

more >>>

Amitabha Roy, Christopher Wilson

A {\em supermodel} is a satisfying assignment of a boolean formula

for which any small alteration, such as a single bit flip, can be

repaired by another small alteration, yielding a nearby

satisfying assignment. We study computational problems associated

with super models and some generalizations thereof. For general

formulas, ...
more >>>

Parikshit Gopalan

Explicit construction of Ramsey graphs or graphs with no large clique or independent set has remained a challenging open problem for a long time. While Erdos's probabilistic argument shows the existence of graphs on 2^n vertices with no clique or independent set of size 2n, the best known explicit constructions ... more >>>

Dave Buchfuhrer, Chris Umans

Many commonly-used auction mechanisms are ``maximal-in-range''. We show that any maximal-in-range mechanism for $n$ bidders and $m$ items cannot both approximate the social welfare with a ratio better than $\min(n, m^\eta)$ for any constant $\eta < 1/2$ and run in polynomial time, unless $NP \subseteq P/poly$. This significantly improves upon ... more >>>

Christoph Behle, Andreas Krebs, Stephanie Reifferscheid

We consider the regular languages recognized by weighted threshold circuits with a linear number of wires.

We present a simple proof to show that parity cannot be computed by such circuits.

Our proofs are based on an explicit construction to restrict the input of the circuit such that the value ...
more >>>

Boris Bukh, Venkatesan Guruswami

We consider codes over fixed alphabets against worst-case symbol deletions. For any fixed $k \ge 2$, we construct a family of codes over alphabet of size $k$ with positive rate, which allow efficient recovery from a worst-case deletion fraction approaching $1-\frac{2}{k+1}$. In particular, for binary codes, we are able to ... more >>>

Joshua Brakensiek, Venkatesan Guruswami

Finding a proper coloring of a $t$-colorable graph $G$ with $t$ colors is a classic NP-hard problem when $t\ge 3$. In this work, we investigate the approximate coloring problem in which the objective is to find a proper $c$-coloring of $G$ where $c \ge t$. We show that for all ... more >>>

Venkatesan Guruswami, Andrii Riazanov

We say a subset $C \subseteq \{1,2,\dots,k\}^n$ is a $k$-hash code (also called $k$-separated) if for every subset of $k$ codewords from $C$, there exists a coordinate where all these codewords have distinct values. Understanding the largest possible rate (in bits), defined as $(\log_2 |C|)/n$, of a $k$-hash code is ... more >>>

Venkatesan Guruswami, Sai Sandeep

A $k$-uniform hypergraph is said to be $r$-rainbow colorable if there is an $r$-coloring of its vertices such that every hyperedge intersects all $r$ color classes. Given as input such a hypergraph, finding a $r$-rainbow coloring of it is NP-hard for all $k \ge 3$ and $r \ge 2$. ... more >>>