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

Joshua Cooper

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

ResearcherUnclaimed source record
math.CODiscrete Mathematicsmath.NTmath.SPComputational Engineering, Finance, and ScienceLogic in Computer ScienceMachine Learningmath.ACmath.CAmath.HOmath.PRmath.RAMolecular NetworksQuantitative Methods

Catalog footprint

What is connected

20works
14topics
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

20 published item(s)

preprint2022arXiv

BioSimulators: a central registry of simulation engines and services for recommending specific tools

Computational models have great potential to accelerate bioscience, bioengineering, and medicine. However, it remains challenging to reproduce and reuse simulations, in part, because the numerous formats and methods for simulating various subsystems and scales remain siloed by different software tools. For example, each tool must be executed through a distinct interface. To help investigators find and use simulation tools, we developed BioSimulators (https://biosimulators.org), a central registry of the capabilities of simulation tools and consistent Python, command-line, and containerized interfaces to each version of each tool. The foundation of BioSimulators is standards, such as CellML, SBML, SED-ML, and the COMBINE archive format, and validation tools for simulation projects and simulation tools that ensure these standards are used consistently. To help modelers find tools for particular projects, we have also used the registry to develop recommendation services. We anticipate that BioSimulators will help modelers exchange, reproduce, and combine simulations.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Geometric vs Algebraic Nullity for Hyperpaths

We consider the question of how the eigenvarieties of a hypergraph relate to the algebraic multiplicities of their corresponding eigenvalues. Specifically, we (1) fully describe the irreducible components of the zero-eigenvariety of a loose $3$-hyperpath (its "nullvariety"), (2) use recent results of Bao-Fan-Wang-Zhu to compute the corresponding algebraic multiplicity of zero (its "nullity"), and then (3) for this special class of hypergraphs, verify a conjecture of Hu-Ye about the relationship between the geometric (multi-)dimension of the nullvariety and the nullity.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Positive-Definite Matrices over Finite Fields

The study of positive-definite matrices has focused on Hermitian matrices, that is, square matrices with complex (or real) entries that are equal to their own conjugate transposes. In the classical setting, positive-definite matrices enjoy a multitude of equivalent definitions and properties. In this paper, we investigate when a square, symmetric matrix with entries coming from a finite field can be called "positive-definite" and discuss which of the classical equivalences and implications carry over.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Sampling Permutations for Shapley Value Estimation

Game-theoretic attribution techniques based on Shapley values are used to interpret black-box machine learning models, but their exact calculation is generally NP-hard, requiring approximation methods for non-trivial models. As the computation of Shapley values can be expressed as a summation over a set of permutations, a common approach is to sample a subset of these permutations for approximation. Unfortunately, standard Monte Carlo sampling methods can exhibit slow convergence, and more sophisticated quasi-Monte Carlo methods have not yet been applied to the space of permutations. To address this, we investigate new approaches based on two classes of approximation methods and compare them empirically. First, we demonstrate quadrature techniques in a RKHS containing functions of permutations, using the Mallows kernel in combination with kernel herding and sequential Bayesian quadrature. The RKHS perspective also leads to quasi-Monte Carlo type error bounds, with a tractable discrepancy measure defined on permutations. Second, we exploit connections between the hypersphere $\mathbb{S}^{d-2}$ and permutations to create practical algorithms for generating permutation samples with good properties. Experiments show the above techniques provide significant improvements for Shapley value estimates over existing methods, converging to a smaller RMSE in the same number of model evaluations.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Recurrence Ranks and Moment Sequences

We introduce the "moment rank" and "unitary rank" of numerical sequences, close relatives of linear-recursive order. We show that both parameters can be characterized by a broad set of criteria involving moments of measures, types of recurrence relations, Hankel matrix factorizations, Waring rank, analytic properties of generating functions, and algebraic properties of polynomial ideals. In the process, we solve the "complex finite-atomic" and "integral finite-atomic" moment problems: which sequences arise as the moments of a finite-atomic complex-/integer-valued measures on $\mathbb{C}$?

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Spectral Extremal Results for Hypergraphs

Let $F$ be a graph. A hypergraph is called Berge $F$ if it can be obtained by replacing each edge in $F$ by a hyperedge containing it. Given a family of graphs $\mathcal{F}$, we say that a hypergraph $H$ is Berge $\mathcal{F}$-free if for every $F \in \mathcal{F}$, the hypergraph $H$ does not contain a Berge $F$ as a subhypergraph. In this paper we investigate the connections between spectral radius of the adjacency tensor and structural properties of a linear hypergraph. In particular, we obtain a spectral version of Turán-type problems over linear $k$-uniform hypergraphs by using spectral methods, including a tight result on Berge $C_4$-free linear $3$-uniform hypergraphs.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Density dichotomy in random words

Word $W$ is said to encounter word $V$ provided there is a homomorphism $ϕ$ mapping letters to nonempty words so that $ϕ(V)$ is a substring of $W$. For example, taking $ϕ$ such that $ϕ(h)=c$ and $ϕ(u)=ien$, we see that "science" encounters "huh" since $cienc=ϕ(huh)$. The density of $V$ in $W$, $δ(V,W)$, is the proportion of substrings of $W$ that are homomorphic images of $V$. So the density of "huh" in "science" is $2/{8 \choose 2}$. A word is doubled if every letter that appears in the word appears at least twice. The dichotomy: Let $V$ be a word over any alphabet, $Σ$ a finite alphabet with at least 2 letters, and $W_n \in Σ^n$ chosen uniformly at random. Word $V$ is doubled if and only if $\mathbb{E}(δ(V,W_n)) \rightarrow 0$ as $n \rightarrow \infty$. We further explore convergence for nondoubled words and concentration of the limit distribution for doubled words around its mean.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Throwing a Ball as Far as Possible, Revisited

What initial trajectory angle maximizes the arc length of an ideal projectile? We show the optimal angle, which depends neither on the initial speed nor on the acceleration of gravity, is the solution x to a surprising transcendental equation: csc(x) = coth(csc(x)), i.e., x = arccsc(y) where y is the unique positive fixed point of coth. Numerically, $x \approx 0.9855 \approx 56.47^\circ$. The derivation involves a nice application of differentiation under the integral sign.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Coloring so that no Pythagorean Triple is Monochromatic

We address the question of the "partition regularity" of the Pythagorean equation a^2+b^2=c^2; in particular, can the natural numbers be assigned a 2-coloring, so that no Pythagorean triple (i.e., a solution to the equation) is monochromatic? We prove that the hypergraph of Pythagorean triples can contain no Steiner triple systems, a natural obstruction to 2-colorability. Then, after transforming the question into one about 3-CNF satisfiability and applying some reductions, a SAT solver is used to find a 2-coloring for {1,...,7664}. Work continues as we seek to improve the reductions and extend the computation.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Computing the Size of Intervals in the Weak Bruhat Order

The weak Bruhat order on $ { \mathcal S }_n $ is the partial order $\prec$ so that $σ\prec τ$ whenever the set of inversions of $σ$ is a subset of the set of inversions of $τ$. We investigate the time complexity of computing the size of intervals with respect to $\prec$. Using relationships between two-dimensional posets and the weak Bruhat order, we show that the size of the interval $ [ σ_1, σ_2 ]$ can be computed in polynomial time whenever $σ_1^{-1} σ_2$ has bounded width (length of its longest decreasing subsequence) or bounded intrinsic width (maximum width of any non-monotone permutation in its block decomposition). Since permutations of intrinsic width $1$ are precisely the separable permutations, this greatly extends a result of Wei. Additionally, we show that, for large $n$, all but a vanishing fraction of permutations $ σ$ in $ { \mathcal S }_n$ give rise to intervals $ [ id , σ]$ whose sizes can be computed with a sub-exponential time algorithm. The general question of the difficulty of computing the size of arbitrary intervals remains open.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Successful Pressing Sequences for a Bicolored Graph and Binary Matrices

We apply matrix theory over $\mathbb{F}_2$ to understand the nature of so-called "successful pressing sequences" of black-and-white vertex-colored graphs. These sequences arise in computational phylogenetics, where, by a celebrated result of Hannenhalli and Pevzner, the space of sortings-by-reversal of a signed permutation can be described by pressing sequences. In particular, we offer several alternative linear-algebraic and graph-theoretic characterizations of successful pressing sequences, describe the relation between such sequences, and provide bounds on the number of them. We also offer several open problems that arose as a result of the present work.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Bounds on Zimin Word Avoidance

How long can a word be that avoids the unavoidable? Word $W$ encounters word $V$ provided there is a homomorphism $ϕ$ defined by mapping letters to nonempty words such that $ϕ(V)$ is a subword of $W$. Otherwise, $W$ is said to avoid $V$. If, on any arbitrary finite alphabet, there are finitely many words that avoid $V$, then we say $V$ is unavoidable. Zimin (1982) proved that every unavoidable word is encountered by some word $Z_n$, defined by: $Z_1 = x_1$ and $Z_{n+1} = Z_n x_{n+1} Z_n$. Here we explore bounds on how long words can be and still avoid the unavoidable Zimin words.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On the Reciprocal of the Binary Generating Function for the Sum of Divisors

If \(A \) is a set of natural numbers containing \(0 \), then there is a unique nonempty "reciprocal" set \(B \) of natural numbers (containing \(0 \)) such that every positive integer can be written in the form \(a + b \), where \(a \in A \) and \(b \in B \), in an even number of ways. Furthermore, the generating functions for \(A \) and \(B \) over \(\FF_2 \) are reciprocals in \(\FF_2 [[q]] \). We consider the reciprocal set \(B \) for the set \(A \) containing \(0 \) and all integers such that \(σ(n) \) is odd, where \(σ(n) \) is the sum of all the positive divisors of \(n \). This problem is motivated by Euler's "Pentagonal Number Theorem", a corollary of which is that the set of natural numbers \(n \) so that the number \(p(n) \) of partitions of an integer \(n \) is odd is the reciprocal of the set of generalized pentagonal numbers (integers of the form \(k(3k\pm1)/2 \), where \(k \) is a natural number). An old (1967) conjecture of Parkin and Shanks is that the density of integers \(n \) so that \(p(n) \) is odd (equivalently, even) is \(1/2 \). Euler also found that \(σ(n) \) satisfies an almost identical recurrence as that given by the Pentagonal Number Theorem, so we hope to shed light on the Parkin-Shanks conjecture by computing the density of the reciprocal of the set containing the natural numbers with \(σ(n) \) odd (\(σ(0)=1 \) by convention). We conjecture this particular density is \(1/32 \) and prove that it lies between \(0 \) and \(1/16 \). We finish with a few surprising connections between certain Beatty sequences and the sequence of integers \(n \) for which \(σ(n) \) is odd.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The complexity of counting poset and permutation patterns

We introduce a notion of pattern occurrence that generalizes both classical permutation patterns as well as poset containment. Many questions about pattern statistics and avoidance generalize naturally to this setting, and we focus on functional complexity problems -- particularly those that arise by constraining the order dimensions of the pattern and text posets. We show that counting the number of induced, injective occurrences among dimension 2 posets is #P-hard; enumerating the linear extensions that occur in realizers of dimension 2 posets can be done in polynomial time, while for unconstrained dimension it is GI-complete; counting not necessarily induced, injective occurrences among dimension 2 posets is #P-hard; counting injective or not necessarily injective occurrences of an arbitrary pattern in a dimension 1 text is #P-hard, although it is in FP if the pattern poset is constrained to have bounded intrinsic width; and counting injective occurrences of a dimension 1 pattern in an arbitrary text is #P-hard, while it is in FP for bounded dimension texts. This framework easily leads to a number of open questions, chief among which are (1) is it #P-hard to count the number of occurrences of a dimension 2 pattern in a dimension 1 text, and (2) is it #P-hard to count the number of texts which avoid a given pattern?

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Computing Hypermatrix Spectra with the Poisson Product Formula

We compute the spectrum of the "all ones" hypermatrix using the Poisson product formula. This computation includes a complete description of the eigenvalues' multiplicities, a seemingly elusive aspect of the spectral theory of tensors. We also give a general distributional picture of the spectrum as a point-set in the complex plane, and use our techniques to analyze the spectrum of "sunflower hypergraphs", a class that has played a prominent role in extremal hypergraph theory.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Critical Sets for Sudoku and General Graphs

We discuss the problem of finding critical sets in graphs, a concept which has appeared in a number of guises in the combinatorics and graph theory literature. The case of the Sudoku graph receives particular attention, because critical sets correspond to minimal fair puzzles. We define four parameters associated with the sizes of extremal critical sets and (a) prove several general results about these parameters' properties, including their computational intractability, (b) compute their values exactly for some classes of graphs, (c) obtain bounds for generalized Sudoku graphs, and (d) offer a number of open questions regarding critical sets and the aforementioned parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Spectra of Uniform Hypergraphs

We present a spectral theory of hypergraphs that closely parallels Spectral Graph Theory. A number of recent developments building upon classical work has led to a rich understanding of "hyperdeterminants" of hypermatrices, a.k.a. multidimensional arrays. Hyperdeterminants share many properties with determinants, but the context of multilinear algebra is substantially more complicated than the linear algebra required to address Spectral Graph Theory (i.e., ordinary matrices). Nonetheless, it is possible to define eigenvalues of a hypermatrix via its characteristic polynomial as well as variationally. We apply this notion to the "adjacency hypermatrix" of a uniform hypergraph, and prove a number of natural analogues of basic results in Spectral Graph Theory. Open problems abound, and we present a number of directions for further study.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Deterministic Random Walks on Regular Trees

Jim Propp's rotor router model is a deterministic analogue of a random walk on a graph. Instead of distributing chips randomly, each vertex serves its neighbors in a fixed order. Cooper and Spencer (Comb. Probab. Comput. (2006)) show a remarkable similarity of both models. If an (almost) arbitrary population of chips is placed on the vertices of a grid $\Z^d$ and does a simultaneous walk in the Propp model, then at all times and on each vertex, the number of chips on this vertex deviates from the expected number the random walk would have gotten there by at most a constant. This constant is independent of the starting configuration and the order in which each vertex serves its neighbors. This result raises the question if all graphs do have this property. With quite some effort, we are now able to answer this question negatively. For the graph being an infinite $k$-ary tree ($k \ge 3$), we show that for any deviation $D$ there is an initial configuration of chips such that after running the Propp model for a certain time there is a vertex with at least $D$ more chips than expected in the random walk model. However, to achieve a deviation of $D$ it is necessary that at least $\exp(Ω(D^2))$ vertices contribute by being occupied by a number of chips not divisible by $k$ at a certain time.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Generalized Fibonacci recurrences and the lex-least De Bruijn sequence

The skew of a binary string is the difference between the number of zeroes and the number of ones, while the length of the string is the sum of these two numbers. We consider certain suffixes of the lexicographically-least de Bruijn sequence at natural breakpoints of the binary string. We show that the skew and length of these suffixes are enumerated by sequences generalizing the Fibonacci and Lucas numbers, respectively.

0 citations0 reviewsNo code linkedOpen access