How to Lose with Least Probability,
Robery Chen, Burton Rosenberg arXiv:1112.2117v2 [math.PR] at http://arxiv.org/abs/1112.2117, 9 December 2011.
Abstract: Two players alternate tossing a biased coin where the probability of getting heads is p. The current player is awarded alpha points for tails and alpha+beta for heads. The first player reaching n points wins. For a completely unfair coin the player going first certainly wins. For other coin biases, the player going first has the advantage, but the advantage depends on the coin bias. We calculate the first player's advantage and the coin bias minimizing this advantage. ArXiv

On the first occurrence of strings,
Robert Chen, Alan Zame, and Burton Rosenberg The Electronic Journal of Combinatorics, 16 (1), Feb 27, 2009. R29.
Abstract: We consider a game in which players select strings over {0,1} and observe a series of fair coin tosses, interpreted as a string over {0,1}. The winner of this game is the player whose string appears first. For two players public knowledge of the opponent's string leads to an advantage. In this paper, results for three players are presented.
It is shown that given the choices of the first two players, a third string can always be chosen with probability of winning greater than 1/3. It is also shown that two players can chose strings such that the third player's probability of winning is strictly less than the greater of the other two player's probability of winning, and that whichever string is chosen, it will always have a disadvantage to one of the two other strings. PDF

Optimal exercise of russian options in the binomial model,
Robert W, Chen, Burton Rosenberg, Computational Finance and its Applications, WIT Press (2006) pp 171-181.
Abstract: The Russian Option is a two-party contract which creates a liability for the option seller to pay the option buyer an amount equal to the maximum price attained by a security over a specific time period, discounted for the option's age. The Russian option was proposed by Shepp and Shiryaev. Kramkov and Shiryaev first examined the option in the binomial model. We improve upon their results and give a near-optimal algorithm for price determination.
Specifically, we prove that the optimal exercising boundary is monotonic and give an O(N) dynamic programming algorithm to construct the boundary, where N is the option expiration time. The algorithm also computes the option's value at time zero in time O(N) and the value at all of the O(N3) nodes in the binomial model in time O(N2). PDF Errata Powerpoint

Inferring model parameters in markets with collars,
Robert Chen, Burton Rosenberg, Yi-Tsung Lee, Computational Finance and its Applications, WIT Press (2004) 167-175.
Abstract: Security prices are set by a continuous auction which can be modeled by a random walk. For many exchanges, there is a general free-flow of price information resulting in stock prices which can be modeled by a random walk following a Weiner-Levy process. However many markets have collars which will not let prices move too rapidly. In this paper we present methods for estimating the volatility of the underlying price data when the true price information is obscured by such collars. Numerical simulations are presented which demonstrate and contrast the methods. PDF Full Paper in PDF

Fast nondeterministic recognition of contex-free languages using two queues,
Burton Rosenberg, Information Processing Letters 67 (1998) 91-93.
Abstract: We show how to accept a context-free language nondeterministically in O(n log n) time on a two-queue machine. PDF PS

A secretary problem with two decision makers,
Robert Chen, Burton Rosenberg and Larry Shepp, Journal of Applied Probability 34 (1997) 1068-1074.
Abstract: Applicants of similar qualifications are on an interview list and their salary demands are from a known and continuous distribution. Two managers will interview them one at a time, deciding to hire or pass. In this paper, we derive the optimal strategies to maximize the probability that the applicant hired demands less salary than the applicant hired by the other manager. PDF PS

Simplex Range Reporting on a Pointer Machine,
Bernard Chazelle and Burton Rosenberg, Computational Geometry: Theory and Applications 5 (1996) 237-247.
Abstract: We give a lower bound on the following problem, known as simple range reporting: Given a collection P of n points in d-space and an arbitrary simplex q, find all points in P intersect q. It is understood that P is fixed and can be preprocessed ahead of time, while q is a query that must be answered on-line. We consider data structures for the problem which can be modeled on a pointer machine and whose query time is bounded by O(n^delta+r), where r is the number of points to be reported and delta is an arbitrary fixed real. We prove that any such data structure of that form must occupy space Omega{n^(d(1-delta)-epsilon)}, for any fixed epsilon>0. This lower bound is tight within a factor of n^epsilon. PDF (missing figures) PS

The Web learning pages,
Burton Rosenberg, unpublished manuscript, April 1995.
Abstract: The Web Learning Pages is a project to reinforce and accelerate classroom learning in the Department of Mathematics and Computer Science at the University of Miami. The doctrine followed by these pages is that Web information is of a new and unusual type: partly static, like a book, and partly real-time, like a conversation. We are trying to exploit this transitional nature of the Web for more effective and efficient teaching. PDF (missing figures) PS (Figure 1) PS (Figure 2)

Two experiments in the stability of stock statistics,
Burton Rosenberg, Third International Conference on Artificial Intelligence Applications on Wall Street (1995), 182-187.
Abstract: This paper announces support in the form of the Spearman rank correlation test for the hypothesis: stock variance is a stable commodity, but the covariance of stocks varies randomly. Among the consequence of this hypothesis are:

  1. Arbitrage equations involving covariances do not constrain the marketplace.
  2. Variance is a stable commodity whose price is set by the arbitrage opportunities it presents.
  3. Portfolio theories depending on estimates of future stock covariances are not at present useful theories.
The result is not unexpected, however the conclusions challenge some of the existing theories. PDF PS

Simulating a stack by queues,
Burton Rosenberg, Proceedings of the XIX Latinamerican Conference on Computer Science 1 (1993), 3-13.
Abstract: We explore the complexity relationships between finite automata endowed with various data structures as auxiliary stores. It is shown that queue automata, finite state machines with one or more queues, are Turing Equivalent. A finite automata with two stacks can simulate a (one) queue automata in constant amortized time per operation simulated. The converse question, simulating a (one) stack machine by a queue machine is not satisfactorily resolved. We give an O(n log n) amortized cost solution using a generalized queue automata. PS

Constraint programming and graph algorithms,
Michel Gangnet and Burton Rosenberg, Annals of Mathematics and Artificial Intelligence, 8:3-4(1993).
Abstract: A constraint system includes a set of variables and a set of relations among these variables, called constraints. The solution of a constraint system is an assignment of values to variables so that all, or many, of the relations are made true. A simple and efficient method for constaint resolution has been proposed in the work of Bjorn N. Freeman-Benson, John Maloney, and Alan Borning. We show how their method is related to the classical problem of graph matching, and from this connection we derive new resolution algorithms. PS

Lower bounds on simplex range reporting on a pointer machine,
Bernard Chazelle and Burton Rosenberg, Nineteenth International Colloquium on Automata, Languages and Programming, LNCS 623 (1992), 439--449.
Abstract: We give a lower bound on the following problem, known as simple range reporting: Given a collection P of n points in d-space and an arbitrary simplex q, find all points in P intersect q. It is understood that P is fixed and can be preprocessed ahead of time, while q is a query that must be answered on-line. We consider data structures for the problem which can be modeled on a pointer machine and whose query time is bounded by O(n^delta+r), where r is the number of points to be reported and delta is an arbitrary fixed real. We prove that any such data structure of that form must occupy space Omega{n^(d(1-delta)-epsilon)}, for any fixed epsilon>0. This lower bound is tight within a factor of n^epsilon. PDF (no figures) PS

The complexity of computing partial sums off-line,
Bernard Chazelle and Burton Rosenberg, International Journal of Computational Geometry and Applications 1:1 33--45 (1991).
Abstract: Given an array A with n entries in an additive semigroup, and m intervlas of the form I=[i,j], where 0 < i < j <= n, we show that the computation A[i]+...+A[j] for all I_i requires Omega(n + m alpha(m,n)) semigroup additions. Here, alpha is the functional inverse of Ackermann's function. A matching upper bound has already been demonstrated. PS

Lower Bounds in Geometric Searching,
Burton Rosenberg, Department of Computer Science, Princeton University CS-TR-343-91 (1991). PhD Thesis. Advisor: Bernard Chazelle.

Computing partial sums in multidimensional arrays,
Bernard Chazelle and Burton Rosenberg, Fifth Annual ACM Symposium on Computational Geometry (1989) 131--139. PS

Survey of NC problems,
Burton Rosenberg, Master of Science Thesis, Columbia University, (1986).
Abstract: An overview of the class of log-depth, polynomial sized circuit complexity. The addition circuit presented in section 3.2 is original work. PDF

Reversibility in computer architecture,
Burton Rosenberg, Bachelor of Science Thesis, M.I.T. (1980).
Abstract: The natural environment of a few generations ago is being replaced with an environment of technology.In that these technologies are mass produced, this constitutes a powerful and unrecognized form of controlled media. Preface.