Source author record

Joshua Brakensiek

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

ResearcherUnclaimed source record

Catalog footprint

What is connected

6works
8topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

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.

Published work

6 published item(s)

preprint2020arXiv

A Simple Sublinear Algorithm for Gap Edit Distance

We study the problem of estimating the edit distance between two $n$-character strings. While exact computation in the worst case is believed to require near-quadratic time, previous work showed that in certain regimes it is possible to solve the following {\em gap edit distance} problem in sub-linear time: distinguish between inputs of distance $\le k$ and $>k^2$. Our main result is a very simple algorithm for this benchmark that runs in time $\tilde O(n/\sqrt{k})$, and in particular settles the open problem of obtaining a truly sublinear time for the entire range of relevant $k$. Building on the same framework, we also obtain a $k$-vs-$k^2$ algorithm for the one-sided preprocessing model with $\tilde O(n)$ preprocessing time and $\tilde O(n/k)$ query time (improving over a recent $\tilde O(n/k+k^2)$-query time algorithm for the same problem [GRS'20].

preprint2020arXiv

Coded trace reconstruction in a constant number of traces

The coded trace reconstruction problem asks to construct a code $C\subset \{0,1\}^n$ such that any $x\in C$ is recoverable from independent outputs ("traces") of $x$ from a binary deletion channel (BDC). We present binary codes of rate $1-\varepsilon$ that are efficiently recoverable from ${\exp(O_q(\log^{1/3}(\frac{1}{\varepsilon})))}$ (a constant independent of $n$) traces of a $\operatorname{BDC}_q$ for any constant deletion probability $q\in(0,1)$. We also show that, for rate $1-\varepsilon$ binary codes, $\tilde Ω(\log^{5/2}(1/\varepsilon))$ traces are required. The results follow from a pair of black-box reductions that show that average-case trace reconstruction is essentially equivalent to coded trace reconstruction. We also show that there exist codes of rate $1-\varepsilon$ over an $O_{\varepsilon}(1)$-sized alphabet that are recoverable from $O(\log(1/\varepsilon))$ traces, and that this is tight.

preprint2020arXiv

Smoothed Complexity of 2-player Nash Equilibria

We prove that computing a Nash equilibrium of a two-player ($n \times n$) game with payoffs in $[-1,1]$ is PPAD-hard (under randomized reductions) even in the smoothed analysis setting, smoothing with noise of constant magnitude. This gives a strong negative answer to conjectures of Spielman and Teng [ST06] and Cheng, Deng, and Teng [CDT09]. In contrast to prior work proving PPAD-hardness after smoothing by noise of magnitude $1/\operatorname{poly}(n)$ [CDT09], our smoothed complexity result is not proved via hardness of approximation for Nash equilibria. This is by necessity, since Nash equilibria can be approximated to constant error in quasi-polynomial time [LMM03]. Our results therefore separate smoothed complexity and hardness of approximation for Nash equilibria in two-player games. The key ingredient in our reduction is the use of a random zero-sum game as a gadget to produce two-player games which remain hard even after smoothing. Our analysis crucially shows that all Nash equilibria of random zero-sum games are far from pure (with high probability), and that this remains true even after smoothing.

preprint2016arXiv

Efficient Geometric Probabilities of Multi-Transiting Exoplanetary Systems from CORBITS

NASA's Kepler Space Telescope has successfully discovered thousands of exoplanet candidates using the transit method, including hundreds of stars with multiple transiting planets. In order to estimate the frequency of these valuable systems, it is essential to account for the unique geometric probabilities of detecting multiple transiting extrasolar planets around the same parent star. In order to improve on previous studies that used numerical methods, we have constructed an efficient, semi-analytical algorithm called CORBITS which, given a collection of conjectured exoplanets orbiting a star, computes the probability that any particular group of exoplanets can be observed to transit. The algorithm applies theorems of elementary differential geometry to compute the areas bounded by circular curves on the surface of a sphere (see Ragozzine & Holman 2010). The implemented algorithm is more accurate and orders of magnitude faster than previous algorithms, based on comparisons with Monte Carlo simulations. We use CORBITS to show that the present solar system would only show a maximum of 3 transiting planets, but that this varies over time due to dynamical evolution. We also used CORBITS to geometrically debias the period ratio and mutual Hill sphere distributions of Kepler's multi-transiting planet candidates, which results in shifting these distributions towards slightly larger values. In an Appendix, we present additional semi-analytical methods for determining the frequency of exoplanet mutual events, i.e., the geometric probability that two planets will transit each other (Planet-Planet Occultation, relevant to transiting circumbinary planets) and the probability that this transit occurs simultaneously as they transit their star. The CORBITS algorithms and several worked examples are publicly available at https://github.com/jbrakensiek/CORBITS

preprint2013arXiv

Bounds on the Size of Sound Monotone Switching Networks Accepting Permutation Sets of Directed Trees

In this paper, we prove almost tight bounds on the size of sound monotone switching networks accepting permutations sets of directed trees. This roughly corresponds to proving almost tight bounds bounds on the monotone memory efficiency of the directed ST-connectivity problem for the special case in which the input graph is guaranteed to have no path from s to t or be isomorphic to a specific directed tree.