Source author record

Thomas Watson

Thomas Watson appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computational Complexity Discrete Mathematics Data Structures and Algorithms cond-mat.mtrl-sci cond-mat.str-el math.CO physics.ao-ph physics.chem-ph

Catalog footprint

What is connected

7works

8topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Erdős-Selfridge Theorem for Nonmonotone CNFs

In an influential paper, Erdős and Selfridge introduced the Maker-Breaker game played on a hypergraph, or equivalently, on a monotone CNF. The players take turns assigning values to variables of their choosing, and Breaker's goal is to satisfy the CNF, while Maker's goal is to falsify it. The Erdős-Selfridge Theorem says that the least number of clauses in any monotone CNF with $k$ literals per clause where Maker has a winning strategy is $Θ(2^k)$. We study the analogous question when the CNF is not necessarily monotone. We prove bounds of $Θ(\sqrt{2}\,^k)$ when Maker plays last, and $Ω(1.5^k)$ and $O(r^k)$ when Breaker plays last, where $r=(1+\sqrt{5})/2\approx 1.618$ is the golden ratio.

preprint2020arXiv

When Is Amplification Necessary for Composition in Randomized Query Complexity?

Suppose we have randomized decision trees for an outer function $f$ and an inner function $g$. The natural approach for obtaining a randomized decision tree for the composed function $(f\circ g^n)(x^1,\ldots,x^n)=f(g(x^1),\ldots,g(x^n))$ involves amplifying the success probability of the decision tree for $g$, so that a union bound can be used to bound the error probability over all the coordinates. The amplification introduces a logarithmic factor cost overhead. We study the question: When is this log factor necessary? We show that when the outer function is parity or majority, the log factor can be necessary, even for models that are more powerful than plain randomized decision trees. Our results are related to, but qualitatively strengthen in various ways, known results about decision trees with noisy inputs.

preprint2016arXiv

Extension Complexity of Independent Set Polytopes

We exhibit an $n$-node graph whose independent set polytope requires extended formulations of size exponential in $Ω(n/\log n)$. Previously, no explicit examples of $n$-dimensional $0/1$-polytopes were known with extension complexity larger than exponential in $Θ(\sqrt{n})$. Our construction is inspired by a relatively little-known connection between extended formulations and (monotone) circuit depth.

preprint2016arXiv

Nonnegative Rank vs. Binary Rank

Motivated by (and using tools from) communication complexity, we investigate the relationship between the following two ranks of a $0$-$1$ matrix: its nonnegative rank and its binary rank (the $\log$ of the latter being the unambiguous nondeterministic communication complexity). We prove that for partial $0$-$1$ matrices, there can be an exponential separation. For total $0$-$1$ matrices, we show that if the nonnegative rank is at most $3$ then the two ranks are equal, and we show a separation by exhibiting a matrix with nonnegative rank $4$ and binary rank $5$, as well as a family of matrices for which the binary rank is $4/3$ times the nonnegative rank.

preprint2015arXiv

Spectral Functions of the Uniform Electron Gas via Coupled-Cluster Theory and Comparison to the $GW$ and Related Approximations

We use, for the first time, ab initio coupled-cluster theory to compute the spectral function of the uniform electron gas at a Wigner-Seitz radius of $r_\mathrm{s}=4$. The coupled-cluster approximations we employ go significantly beyond the diagrammatic content of state-of-the-art $GW$ theory. We compare our calculations extensively to $GW$ and $GW$-plus-cumulant theory, illustrating the strengths and weaknesses of these methods in capturing the quasiparticle and satellite features of the electron gas. Our accurate calculations further allow us to address the long-standing debate over the occupied bandwidth of metallic sodium. Our findings indicate that the future application of coupled-cluster theory to condensed phase material spectra is highly promising.

preprint2013arXiv

Present Velocity and Acceleration in Tide Gauge Records Characterized by a Quasi-60 years Periodic Oscillation

The paper describing sea level rise oscillations at Cape Hatteras, USA by Parker [1] has opened the discussion regarding if the velocity in a tide gauge record characterized by a quasi-60-year multi-decadal oscillation can be computed by linear fitting of 30 years of data in two ad-hoc selected times and if acceleration can then be inferred by comparing these two values as proposed by Sallenger [2], or if this comparison is meaningless in that the 60-year time window is the minimum amount of time needed to evaluate the velocity in a record characterized by a quasi-60-year multi-decadal oscillation and the acceleration has then to be computed as the time derivative of this velocity as suggested by Parker [1,3]. For the specific case of The Battery, NY, it is shown here that the 60-year time window is the minimum time length needed to compute a velocity, and both the 60-year windows and the all data velocities are free of any acceleration at the present time. The 30-year time window velocity of 2009 is not representative of the present sea level rise and the comparison of the 30-year time window velocity of 2009 and 1979 near a peak and a valley, respectively, of the 60-year multidecadal oscillation to claim a present acceleration has no scientific background.

preprint2011arXiv

Lift-and-Project Integrality Gaps for the Traveling Salesperson Problem

We study the lift-and-project procedures of Lov{á}sz-Schrijver and Sherali-Adams applied to the standard linear programming relaxation of the traveling salesperson problem with triangle inequality. For the asymmetric TSP tour problem, Charikar, Goemans, and Karloff (FOCS 2004) proved that the integrality gap of the standard relaxation is at least 2. We prove that after one round of the Lov{á}sz-Schrijver or Sherali-Adams procedures, the integrality gap of the asymmetric TSP tour problem is at least 3/2, with a small caveat on which version of the standard relaxation is used. For the symmetric TSP tour problem, the integrality gap of the standard relaxation is known to be at least 4/3, and Cheung (SIOPT 2005) proved that it remains at least 4/3 after $o(n)$ rounds of the Lov{á}sz-Schrijver procedure, where $n$ is the number of nodes. For the symmetric TSP path problem, the integrality gap of the standard relaxation is known to be at least 3/2, and we prove that it remains at least 3/2 after $o(n)$ rounds of the Lov{á}sz-Schrijver procedure, by a simple reduction to Cheung's result.