BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

William Maxwell

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

ResearcherUnclaimed source record
Discrete MathematicsComputational GeometryCryptography and SecurityData Structures and Algorithmsmath.ATmath.CO

Catalog footprint

What is connected

4works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

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

4 published item(s)

preprint2020arXiv

Low-stretch spanning trees of graphs with bounded width

We study the problem of low-stretch spanning trees in graphs of bounded width: bandwidth, cutwidth, and treewidth. We show that any simple connected graph $G$ with a linear arrangement of bandwidth $b$ can be embedded into a distribution $\mathcal T$ of spanning trees such that the expected stretch of each edge of $G$ is $O(b^2)$. Our proof implies a linear time algorithm for sampling from $\mathcal T$. Therefore, we have a linear time algorithm that finds a spanning tree of $G$ with average stretch $O(b^2)$ with high probability. We also describe a deterministic linear-time algorithm for computing a spanning tree of $G$ with average stretch $O(b^3)$. For graphs of cutwidth $c$, we construct a spanning tree with stretch $O(c^2)$ in linear time. Finally, when $G$ has treewidth $k$ we provide a dynamic programming algorithm computing a minimum stretch spanning tree of $G$ that runs in polynomial time with respect to the number of vertices of $G$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Minimum bounded chains and minimum homologous chains in embedded simplicial complexes

We study two optimization problems on simplicial complexes with homology over $\mathbb{Z}_2$, the minimum bounded chain problem: given a $d$-dimensional complex $\mathcal{K}$ embedded in $\mathbb{R}^{d+1}$ and a null-homologous $(d-1)$-cycle $C$ in $\mathcal{K}$, find the minimum $d$-chain with boundary $C$, and the minimum homologous chain problem: given a $(d+1)$-manifold $\mathcal{M}$ and a $d$-chain $D$ in $\mathcal{M}$, find the minimum $d$-chain homologous to $D$. We show strong hardness results for both problems even for small values of $d$; $d = 2$ for the former problem, and $d=1$ for the latter problem. We show that both problems are APX-hard, and hard to approximate within any constant factor assuming the unique games conjecture. On the positive side, we show that both problems are fixed parameter tractable with respect to the size of the optimal solution. Moreover, we provide an $O(\sqrt{\log β_d})$-approximation algorithm for the minimum bounded chain problem where $β_d$ is the $d$th Betti number of $\mathcal{K}$. Finally, we provide an $O(\sqrt{\log n_{d+1}})$-approximation algorithm for the minimum homologous chain problem where $n_{d+1}$ is the number of $d$-simplices in $\mathcal{M}$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the treewidth of Hanoi graphs

The objective of the well-known Towers of Hanoi puzzle is to move a set of disks one at a time from one of a set of pegs to another, while keeping the disks sorted on each peg. We propose an adversarial variation in which the first player forbids a set of states in the puzzle, and the second player must then convert one randomly-selected state to another without passing through forbidden states. Analyzing this version raises the question of the treewidth of Hanoi graphs. We find this number exactly for three-peg puzzles and provide nearly-tight asymptotic bounds for larger numbers of pegs.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

A baseline for unsupervised advanced persistent threat detection in system-level provenance

Advanced persistent threats (APT) are stealthy, sophisticated, and unpredictable cyberattacks that can steal intellectual property, damage critical infrastructure, or cause millions of dollars in damage. Detecting APTs by monitoring system-level activity is difficult because manually inspecting the high volume of normal system activity is overwhelming for security analysts. We evaluate the effectiveness of unsupervised batch and streaming anomaly detection algorithms over multiple gigabytes of provenance traces recorded on four different operating systems to determine whether they can detect realistic APT-like attacks reliably and efficiently. This report is the first detailed study of the effectiveness of generic unsupervised anomaly detection techniques in this setting.

0 citations0 reviewsNo code linkedOpen access