Memoryhard functions (MHFs) are a key cryptographic primitive underlying the design of moderately expensive password hashing algorithms and egalitarian proofs of work. Over the past few years several increasingly stringent goals for an MHF have been proposed including the requirement that the MHF have high sequential spacetime (ST) complexity, parallel spacetime complexity, amortized areatime (aAT) complexity and sustained space complexity. DataIndependent Memory Hard Functions (iMHFs) are of special interest in the context of password hashing as they naturally resist sidechannel attacks. iMHFs can be specified using a directed acyclic graph (DAG) $G$ with $N=2^n$ nodes and low indegree and the complexity of the iMHF can be analyzed using a pebbling game. Recently, Alwen et al. [CCS'17] constructed an DAG called DRSample which has aAT complexity at least $\Omega\left( N^2/\log N\right)$. Asymptotically DRSample outperformed all prior iMHF constructions including Argon2i, winner of the password hashing competition (aAT cost $\mathcal{O}\left(N^{1.767}\right)$), though the constants in these bounds are poorly understood. We show that the the greedy pebbling strategy of Boneh et al. [ASIACRYPT'16] is particularly effective against DRSample e.g., the aAT cost is $\mathcal{O}\left( N^2/\log N\right)$. In fact, our empirical analysis {\em reverses} the prior conclusion of Alwen et al. that DRSample providesmore »
PREEMPT: Scalable Epidemic Interventions Using Submodular Optimization on MultiGPU Systems
Preventing and slowing the spread of epidemics
is achieved through techniques such as vaccination and social
distancing. Given practical limitations on the number of vaccines
and cost of administration, optimization becomes a necessity.
Previous approaches using mathematical programming methods
have shown to be effective but are limited by computational
costs. In this work, we present PREEMPT, a new approach for
intervention via maximizing the influence of vaccinated nodes on
the network.We prove submodular properties associated with the
objective function of our method so that it aids in construction
of an efficient greedy approximation strategy. Consequently, we
present a new parallel algorithm based on greedy hill climbing
for PREEMPT, and present an efficient parallel implementation
for distributed CPUGPU heterogeneous platforms. Our results
demonstrate that PREEMPT is able to achieve a significant
reduction (up to 6:75) in the percentage of people infected
and up to 98% reduction in the peak of the infection on a cityscale
network. We also show strong scaling results of PREEMPT
on up to 128 nodes of the Summit supercomputer. Our parallel
implementation is able to significantly reduce time to solution,
from hours to minutes on large networks. This work represents
a firstofitskind effort in parallelizing greedy hill climbing and
applying it toward devising effective interventions for epidemics.
 Publication Date:
 NSFPAR ID:
 10213737
 Journal Name:
 International Conference for High Performance Computing Networking Storage and Analysis
 Page Range or eLocationID:
 765799
 ISSN:
 21674337
 Sponsoring Org:
 National Science Foundation
More Like this


One of the major challenges in parallelization is the difficulty of improving application scalability with conventional techniques. HPX provides efficient scalable parallelism by significantly reducing node starvation and effective latencies while controlling the overheads. In this paper, we present a new highly scalable parallel distributed NBody application using a futurebased algorithm, which is implemented with HPX. The main difference between this algorithm and prior art is that a futurebased request buffer is used between different nodes and along each spatial direction to send/receive data to/from the remote nodes, which helps removing synchronization barriers. HPX provides an asynchronous programming model which results in improving the parallel performance. The results of using HPX for parallelizing Octree construction on one node and the force computation on the distributed nodes show the scalability improvement on an average by about 45% compared to an equivalent OpenMP implementation and 28% compared to a hybrid implementation (MPI+OpenMP) [1] respectively for one billion particles running on up to 128 nodes with 20 cores per each.

Evaluating AMR parsing accuracy involves comparing pairs of AMR graphs. The major evaluation metric, SMATCH (Cai and Knight,2013), searches for onetoone mappings between the nodes of two AMRs with a greedy hillclimbing algorithm, which leads to search errors. We propose SEMBLEU, a robust metric that extends BLEU (Papineni et al., 2002) to AMRs. It does not suffer from search errors and considers nonlocal correspondences in addition to local ones. SEMBLEU is fully contentdriven and punishes situations where a systemâ€™s output does not preserve most information from the input. Preliminary experiments on both sentence and corpus levels show that SEMBLEU has slightly higher consistency with human judgments than SMATCH. Our code is available athttp://github.com/freesunshine0316/sembleu.

Efficient contact tracing and isolation is an effective strategy to control epidemics. It was used effectively during the Ebola epidemic and successfully implemented in several parts of the world during the ongoing COVID19 pandemic. An important consideration in contact tracing is the budget on the number of individuals asked to quarantine  the budget is limited for socioeconomic reasons. In this paper, we present a Markov Decision Process (MDP) framework to formulate the problem of using contact tracing to reduce the size of an outbreak while asking a limited number of people to quarantine. We formulate each step of the MDP as a combinatorial problem, MinExposed, which we demonstrate is NPHard; as a result, we develop an LPbased approximation algorithm. Though this algorithm directly solves MinExposed, it is often impractical in the real world due to information constraints. To this end, we develop a greedy approach based on insights from the analysis of the previous algorithm, which we show is more interpretable. A key feature of the greedy algorithm is that it does not need complete information of the underlying social contact network. This makes the heuristic implementable in practice and is an important consideration. Finally, we carry out experimentsmore »

In this paper, we consider a temporal logic planning problem in which the objective is to find an infinite trajectory that satisfies an optimal selection from a set of soft specifications expressed in linear temporal logic (LTL) while nevertheless satisfying a hard specification expressed in LTL. Our previous work considered a similar problem in which linear dynamic logic for finite traces (LDL_f), rather than LTL, was used to express the soft constraints. In that work, LDL_f was used to impose constraints on finite prefixes of the infinite trajectory. By using LTL, one is able not only to impose constraints on the finite prefixes of the trajectory, but also to set `soft' goals across the entirety of the infinite trajectory. Our algorithm first constructs a product automaton, on which the planning problem is reduced to computing a lasso with minimum cost. Among all such lassos, it is desirable to compute a shortest one. Though we prove that computing such a shortest lasso is computationally hard, we also introduce an efficient greedy approach to synthesize short lassos nonetheless. We present two case studies describing an implementation of this approach, and report results of our experiment comparing our greedy algorithm with an optimalmore »