Michael A. Bender - Stony Brook University

Michael A. Bender
Are you Michael A. Bender?

Claim your profile, edit publications, add additional information:

Contact Details

Michael A. Bender
Stony Brook University
Stony Brook
United States

Pubs By Year

External Links

Pub Categories

Computer Science - Data Structures and Algorithms (15)
Nuclear Theory (8)
Computer Science - Computational Geometry (2)
Computer Science - Robotics (2)
Computer Science - Distributed; Parallel; and Cluster Computing (2)
Computer Science - Discrete Mathematics (2)
Computer Science - Numerical Analysis (1)
Mathematical Physics (1)
Computer Science - Computational Complexity (1)
Computer Science - Mathematical Software (1)
Mathematics - Mathematical Physics (1)
Physics - Superconductivity (1)
Computer Science - Networking and Internet Architecture (1)
High Energy Physics - Experiment (1)
Computer Science - Databases (1)
Nuclear Experiment (1)
Physics - Instrumentation and Detectors (1)
Physics - Strongly Correlated Electrons (1)
Computer Science - Computational Engineering; Finance; and Science (1)

Publications Authored By Michael A. Bender

We report on the optimization of discharge insensitive floating strip Micromegas (MICRO-MEsh GASeous) detectors, fit for use in high-energy muon spectrometers. The suitability of these detectors for particle tracking is shown in high-background environments and at very high particle fluxes up to 60MHz/cm$^2$. Measurement and simulation of the microscopic discharge behavior have demonstrated the excellent discharge tolerance. Read More

Affiliations: 1Stony Brook University, 2Stony Brook University, 3University of Massachusetts, Amherst, 4Stony Brook University, 5University of Massachusetts, Amherst

In this paper, we revisit the classic problem of run generation. Run generation is the first phase of external-memory sorting, where the objective is to scan through the data, reorder elements using a small buffer of size M , and output runs (contiguously sorted chunks of elements) that are as long as possible. We develop algorithms for minimizing the total number of runs (or equivalently, maximizing the average run length) when the runs are allowed to be sorted or reverse sorted. Read More

Databases need to allocate and free blocks of storage on disk. Freed blocks introduce holes where no data is stored. Allocation systems attempt to reuse such deallocated regions in order to minimize the footprint on disk. Read More

Randomized exponential backoff is a widely deployed technique for coordinating access to a shared resource. A good backoff protocol should, arguably, satisfy three natural properties: (i) it should provide constant throughput, wasting as little time as possible; (ii) it should require few failed access attempts, minimizing the amount of wasted effort; and (iii) it should be robust, continuing to work efficiently even if some of the access attempts fail for spurious reasons. Unfortunately, exponential backoff has some well-known limitations in two of these areas: it provides poor (sub-constant) throughput (in the worst case), and is not robust (to resource acquisition failures). Read More

In traditional on-line problems, such as scheduling, requests arrive over time, demanding available resources. As each request arrives, some resources may have to be irrevocably committed to servicing that request. In many situations, however, it may be possible or even necessary to reallocate previously allocated resources in order to satisfy a new request. Read More

This paper presents new alternatives to the well-known Bloom filter data structure. The Bloom filter, a compact data structure supporting set insertion and membership queries, has found wide application in databases, storage systems, and networks. Because the Bloom filter performs frequent random reads and writes, it is used almost exclusively in RAM, limiting the size of the sets it can represent. Read More

Recent self-consistent mean-field calculations predict a substantial depletion of the proton density in the interior of 34Si. In the present study, we investigate how correlations beyond the mean field modify this finding. The framework of the calculation is a particle-number and angular-momentum projected Generator Coordinate Method based on Hartree-Fock-Bogoliubov+Lipkin-Nogami states with axial quadrupole deformation. Read More

We consider the problem of detecting a cycle in a directed graph that grows by arc insertions, and the related problems of maintaining a topological order and the strong components of such a graph. For these problems, we give two algorithms, one suited to sparse graphs, and the other to dense graphs. The former takes the minimum of O(m^{3/2}) and O(mn^{2/3}) time to insert m arcs into an n-vertex graph; the latter takes O(n^2 log(n)) time. Read More

We derive an expression that allows for the unambiguous evaluation of the overlap between two arbitrary quasiparticle vacua, including its sign. Our expression is based on the Pfaffian of a skew-symmetric matrix, extending the formula recently proposed by [L. M. Read More

The Multi-Reference Energy Density Functional (MR-EDF) approach (also called configuration mixing or Generator Coordinate Method), that is commonly used to treat pairing in finite nuclei and project onto particle number, is re-analyzed. It is shown that, under certain conditions, the MR-EDF energy can be interpreted as a functional of the one-body density matrix of the projected state with good particle number. Based on this observation, we propose a new approach, called Symmetry-Conserving EDF (SC-EDF), where the breaking and restoration of symmetry are accounted for simultaneously. Read More

The restoration of particle number within Energy Density Functional theory is analyzed. It is shown that the standard method based on configuration mixing leads to a functional of both the projected and non-projected densities. As an alternative that might be advantageous for mass models, nuclear dynamics and thermodynamics, we propose to formulate the functional in terms directly of the one-body and two-body density matrices of the state with good particle number. Read More

We perform an analysis of a binding energy difference called delta V_{pn}(N,Z) =- 1/4(E(Z,N)-E(Z,N-2)-E(Z-2,N)+ E(Z-2,N-2) in the framework of a realistic nuclear model. Using the angular-momentum and particle-number projected generator coordinate method and the Skyrme interaction SLy4, we analyze the contribution brought to delta V_{pn} by static deformation and dynamic fluctuations around the mean-field ground state. Our method gives a good overall description of delta V_{pn} throughout the chart of nuclei with the exception of the anomaly related to the Wigner energy along the N=Z line. Read More

In this paper we consider methods for dynamically storing a set of different objects ("modules") in a physical array. Each module requires one free contiguous subinterval in order to be placed. Items are inserted or removed, resulting in a fragmented layout that makes it harder to insert further modules. Read More

Configuration mixing calculations performed in terms of the Skyrme/Gogny Energy Density Functional (EDF) rely on extending the Single-Reference energy functional into non-diagonal EDF kernels. The standard way to do so, based on an analogy with the pure Hamiltonian case and the use of the generalized Wick theorem, is responsible for the recently observed divergences and steps in Multi-Reference calculations. We summarize here the minimal solution to this problem recently proposed [Lacroix et al, arXiv:0809. Read More

Affiliations: 1IPNL, 2SPhN, CENBG, 3IPNL, SPhN, 4NSCL, MSU, 5IPNL
Category: Nuclear Theory

We systematically study the effect of the J^2 tensor terms in the Skyrme energy functional on properties of spherical nuclei. We build a set of 36 parameterizations covering a wide range of the corresponding parameter space. We analyze the impact of the tensor terms on the evolution of single-particle-level splittings along chains of semi-magic nuclei in spherical calculations. Read More

This paper presents the solution to the following optimization problem: What is the shape of the two-dimensional region that minimizes the average L_p distance between all pairs of points if the area of this region is held fixed? [The L_p distance between two points ${\bf x}=(x_1,x_2)$ and ${\bf y}=(y_1,y_2)$ in $\Re^2$ is $(|x_1-y_1|^p+|x_2-y_2|^p)^{1/p}$.] Variational techniques are used to show that the boundary curve of the optimal region satisfies a nonlinear integral equation. The special case p=2 is elementary and for this case the integral equation reduces to a differential equation whose solution is a circle. Read More

This paper presents scheduling algorithms for procrastinators, where the speed that a procrastinator executes a job increases as the due date approaches. We give optimal off-line scheduling policies for linearly increasing speed functions. We then explain the computational/numerical issues involved in implementing this policy. Read More

Affiliations: 1SPhN, NSCL, MSU, 2SPhN, NSCL, MSU, 3GANIL, 4NSCL, MSU, 5GANIL
Category: Nuclear Theory

We investigate the role of deformation on the fusion probability around the barrier using the Time-Dependent Hartree-Fock theory with a full Skyrme force. We obtain a distribution of fusion probabilities around the nominal barrier due to the different contributions of the various orientations of the deformed nucleus at the touching point. It is also shown that the long range Coulomb reorientation reduces the fusion probability around the barrier. Read More

Affiliations: 1Department of Applied Mathematics and Statistics, Stony Brook University, 2Department of Computer Science, Stony Brook University, 3Department of Applied Mathematics and Statistics, Stony Brook University, 4Department of Applied Mathematics and Statistics, Stony Brook University

We introduce the snowblower problem (SBP), a new optimization problem that is closely related to milling problems and to some material-handling problems. The objective in the SBP is to compute a short tour for the snowblower to follow to remove all the snow from a domain (driveway, sidewalk, etc.). Read More

This paper gives processor-allocation algorithms for minimizing the average number of communication hops between the assigned processors for grid architectures, in the presence of occupied cells. The simpler problem of assigning processors on a free grid has been studied by Karp, McKellar, and Wong who show that the solutions have nontrivial structure; they left open the complexity of the problem. The associated clustering problem is as follows: Given n points in Re^d, find k points that minimize their average pairwise L1 distance. Read More

Traditional Insertion Sort runs in O(n^2) time because each insertion takes O(n) time. When people run Insertion Sort in the physical world, they leave gaps between items to accelerate insertions. Gaps help in computers as well. Read More

An optimization problem that naturally arises in the study of swarm robotics is the Freeze-Tag Problem (FTP) of how to awaken a set of ``asleep'' robots, by having an awakened robot move to their locations. Once a robot is awake, it can assist in awakening other slumbering robots.The objective is to have all robots awake as early as possible. Read More

We give the first algorithmic study of a class of ``covering tour'' problems related to the geometric Traveling Salesman Problem: Find a polygonal tour for a cutter so that it sweeps out a specified region (``pocket''), in order to minimize a cost that depends mainly on the number of em turns. These problems arise naturally in manufacturing applications of computational geometry to automatic tool path generation and automatic inspection systems, as well as arc routing (``postman'') problems with turn penalties. We prove the NP-completeness of minimum-turn milling and give efficient approximation algorithms for several natural versions of the problem, including a polynomial-time approximation scheme based on a novel adaptation of the m-guillotine method. Read More

We develop and analyze algorithms for dispersing a swarm of primitive robots in an unknown environment, R. The primary objective is to minimize the makespan, that is, the time to fill the entire region. An environment is composed of pixels that form a connected subset of the integer grid. Read More

We consider the problem of laying out a tree with fixed parent/child structure in hierarchical memory. The goal is to minimize the expected number of block transfers performed during a search along a root-to-leaf path, subject to a given probability distribution on the leaves. This problem was previously considered by Gil and Itai, who developed optimal but slow algorithms when the block-transfer size B is known. Read More

We introduce a new class of scheduling problems in which the optimization is performed by the worker (single ``machine'') who performs the tasks. A typical worker's objective is to minimize the amount of work he does (he is ``lazy''), or more generally, to schedule as inefficiently (in some sense) as possible. The worker is subject to the constraint that he must be busy when there is work that he can do; we make this notion precise both in the preemptive and nonpreemptive settings. Read More

We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a flat folding by a sequence of simple folds? There are several models of simple folds; the simplest one-layer simple fold rotates a portion of paper about a crease in the paper by +-180 degrees. We first consider the analogous questions in one dimension lower -- bending a segment into a flat object -- which lead to interesting problems on strings. We develop efficient algorithms for the recognition of simply foldable 1D crease patterns, and reconstruction of a sequence of simple folds. Read More