Journal of the ACM

We study the problem of obtaining lower bounds for polynomial calculus (PC) and polynomial calculus resolution (PCR) on proof degree, and hence by [Impagliazzo et al.  ’99] also on proof size. [Alekhnovich and Razborov’03] established that if the clause-...

The main results of this paper provide an Efficient Polynomial-Time Approximation Scheme (EPTAS) for approximating the genus (and non-orientable genus) of dense graphs. By dense we mean that \(|E(G)|\ge \alpha \, |V(G)|^2\) for some fixed \(\(\alpha \gt ...\)

We provide a complete characterization of both uniform and non-uniform deterministic consensus solvability in distributed systems with benign process and communication faults using point-set topology. More specifically, we non-trivially extend the ...

Type soundness, which asserts that “well-typed programs cannot go wrong,” is widely viewed as the canonical theorem one must prove to establish that a type system is doing its job. It is commonly proved using the so-called syntactic approach (also known ...

We show that any memory-constrained, first-order algorithm which minimizes d-dimensional, 1-Lipschitz convex functions over the unit ball to 1/poly(d) accuracy using at most d^{1.25 - δ} bits of memory must make at least \(\(\tilde{\Omega }(d^{1 + (4/3)\delta ...\)

We consider the following well-studied problem of metric distortion in social choice. Suppose that we have an election with n voters and m candidates located in a shared metric space. We would like to design a voting rule that chooses a candidate whose ...