Research papers
|
János A. Csirik's Web Site
Research papers
|
Most papers are available in Adobe's Portable Document format (PDF) in this section. Many are also available in Knuth's dvi format through the "More details" link. (Note to Mac OS X users.)
| Number theory: |
* On the genera of X0(N), (PDF), (joint work with Michael Zieve and Joe Wetherell), accepted by the Journal of Number Theory, 2001 | More details |
|---|---|---|
| * The old subvariety of J0(NM), submitted for publication, 2001 | More details | |
| * The Kernel of the Eisenstein Ideal, in Journal of Number Theory, Vol. 92, No. 2, pp. 348-375, 2002 | More details | |
| * The kernel of the Eisenstein ideal, (PDF), Ph.D. dissertation, University of California, Berkeley, 1999 | More details | |
| * An alternative approach to Serre duality for projective varieties, (short version in PDF, long version in PDF), (joint work with Matt Baker), manuscript, 1996 | More details | |
| Cryptography: |
* Private Computation Using a PEZ Dispenser, (PDF), (joint work with József Balogh, Yuval Ishai, Eyal Kushilevitz), to appear in Theoretical Computer Science, 2003 | More details |
| * Not a research paper: A guide to cryptography in third generation wireless phones, Web page, 2001 | ||
| * On the Computation of Modular Polynomials for Elliptic Curves, (PDF), (joint work with Ian F. Blake, Michael Rubinstein, Gadiel Serioussi), Hewlett-Packard technical report, 1999 | More details | |
| * Counting the points of an elliptic curve on a low-memory device, (PDF), submitted for publication, 2000 | More details | |
| * An exposition of the SEA algorithm, (PDF), submitted for publication, 2000 | More details | |
| Auctions: |
* Do auction discounts reduce revenues? Evidence from the FCC's Auction No. 35, (PDF), preprint, 2002 | More details |
| * ATTac-2001: A Learning, Autonomous Bidding Agent, (PDF), (joint work with Robert Schapire, Peter Stone, David McAllester, Michael L. Littman), to appear in the proceedings of Workshop on Agent Mediated Electronic Commerce IV: Designing Mechanisms and Systems, 2002 | More details | |
| * Modeling Auction Price Uncertainty Using Boosting-based Conditional Density Estimation, (PDF), (joint work with Robert Schapire, Peter Stone, David McAllester, Michael L. Littman), to appear in the proceedings of International Conference on Machine Learning (ICML), 2002 | More details | |
| * Self-enforcing Strategic Demand Reduction, (PDF), (joint work with Paul S.A. Reitsma, Peter Stone, Michael L. Littman), to appear in the proceedings of Workshop on Agent Mediated Electronic Commerce IV: Designing Mechanisms and Systems, 2002 | More details | |
| * FAucS: An FCC Spectrum Auction Simulator for Autonomous Bidding Agents, (article in PDF, software, some other data files), (joint work with Michael L. Littman, Satinder Singh, Peter Stone), in Fiege, L., Mühl, G., and Wilhelm, U. (eds), Electronic Commerce: Proceedings of the Second International Workshop, pp. 139-151, Springer, 2001 | More details | |
| Other: |
* Index assignment for two-channel quantization, (article in PDF, some supporting data), (joint work with József Balogh), submitted for publication, 2002 | More details |
| * The cost of exactly simulating a Bell pair using classical communication, (PDF), Phys. Review A 66, 014302, 2002 | More details | |
| * Optimal Strategy for the First Player in the Penney Ante Game, in Combinatorics, Probability and Computing (1992), 1, pp. 311-321 | More details |
Are you looking for another paper by János A. Csirik that is not listed here? Please email me at janos (at) pobox.com.
[2000] On the genera of X0(N) (Joint work with Michael Zieve and Joe Wetherell.) This came from attending the Arizona Winter School in Arithmetic Geometry. The modular curves X0(N) have extremely many points over certain fields, in fact they are essentially optimal in their genus. Therefore, one is lead to wonder what the genus of X0(N) might be. "We derive various properties of the genera of modular curves X0(N). For instance, the genus is odd with probability 1; the genus is on average around N/8; a random positive integer has probability zero of being the genus of some X0(N)." This paper has been accepted by the Journal of Number Theory. We are applying some finishing touches to it right now. Here is the most current draft (PDF, dvi).
[1999] The kernel of the Eisenstein ideal (PDF), my Ph.D. thesis. I got my Ph.D. from the University of California, Berkeley, under the direction of Ken Ribet. "Let N be a prime number, and let J0(N) be the Jacobian of the modular curve X0(N). Let T denote the endomorphism ring of J0(N). In a seminal 1977 article, B. Mazur introduced and studied an important ideal I of T, the Eisenstein ideal. In this dissertation we give an explicit construction of the kernel J_0(N)[I] of this ideal (the set of points in J0(N) that are annihilated by all elements of I). We use this construction to determine the action of the absolute Galois group of Q on J_0(N)[I]. Then we apply our results to study the structure of the old subvariety of J0(NM), where M is a prime number distinct from N. Our results were previously known in the special case where N-1 is not divisible by 16." The first part of this is in the Journal of Number Theory, Vol. 92, No. 2, pp. 348-375, 2002, under the title The Kernel of the Eisenstein Ideal. The second half the dissertation has been submitted for publication under the title The old subvariety of J0(NM).
[1996] An alternative approach to Serre duality for projective varieties. (Joint work with Matt Baker.) In 1996, I was a first-year grad student and attended Robin Hartshorne's Algebraic Geometry, in which he explained his own book. My friend Matt Baker and I got excited and produced an alternative approach to Serre duality: "We give a new proof of the isomorphism between the dualizing sheaf and the canonical sheaf of a non-singular projective variety X over a perfect field k. Our proof uses concepts and results from algebraic number theory." You can get the long version (PDF, dvi) with many details spelled out, or the more streamlined short version (PDF, dvi).
[2001] Private Computation Using a PEZ Dispenser (PDF). (Joint work with József Balogh, Yuval Ishai, Eyal Kushilevitz.) "We consider the following 'recreational cryptography' problem. A group of n deterministic players wish to compute some function f of their inputs without revealing their inputs to each other. To their aid is a PEZ dispenser, which may be pre-loaded with some fixed public sequence of colored candies. The colors correspond to the possible values of f, and two distinct candies of the same color are assumed to be indistinguishable. The players take turns, where at each turn one of the players takes the PEZ dispenser and decides, based on its input, how many candies to pop out. At the end of such a protocol, the following requirements should be met: (1) the color of the candy at the top of the dispenser corresponds to the value of f on the inputs; (2) while executing the protocol, no player learns information on the inputs of the other players. Quite surprisingly, we show that every function can be computed in this model, and obtain some bounds on the complexity of such a computation." To appear in Theoretical Computer Science.
[1999] On the Computation of Modular Polynomials for Elliptic Curves (Hewlett-Packard technical report: PDF). (Joint work with Ian F. Blake, Michael Rubinstein and Gadiel Serioussi.) This came out of some applied cryptography work I did at Hewlett-Packard Labs while I was an MSRI-HP postdoc. Michael was the previous year's MSRI-HP postdoc, Ian and Gadiel were at HP Labs. "An essential aspect of the use of elliptic curves over a finite field in public key cryptosystems is to determine the precise order of the additive group of rational points of the curve. All known effective point-counting algorithms for such elliptic curves require the computation of modular polynomials. Several approaches to the computation of modular polynomials and variants of them have been considered in the literature. The purpose of this work is to give a unified treatment of these approaches, and to report on computational experience with their efficient implementations."
[1998] Counting the number of points on an elliptic curve on a low-memory device. This came out of my cryptography summer job with Arjen Lenstra at Citibank. It's now been broken into two parts: a survey on the Schoof-Elkies-Atkin algorithm (PDF, dvi), and a modification of the algorithm to use less memory (PDF, dvi).
[2002] Do auction discounts reduce revenues? Evidence from the FCC's Auction No. 35 (PDF). "In December 2000 and January 2001, the Federal Communications Commission (FCC) of the U.S. government held an auction for wireless spectrum licenses where certain bidders (the designated entitites) were allowed to bid on more licenses than others, and were in some cases given discounts on the final prices achieved in the auction. This paper examines the effects of these discounts and argues that---somewhat surprisingly---they increased the total revenue to the FCC." Preprint, 2002.
[2001] Trading Agent Competition 2001 (Joint work with Peter Stone, Robert Schapire, Michael L. Littman, David McAllester.) The Trading Agent Competition is now an annual event, where simulated auctions involving travel agents jostling for hotel rooms, flight tickets and entertainment tickets are run repeatedly to sort out which of the contestants submitted the computerized agent that can best compete in this setup. This is to promote research in agent-based systems in general, and in auctions in particular. AT&T Labs--Research won the first competition in 2000 with an agent called ATTac. I joined the team in 2001. ATTac-01 managed to place in the top two in a much larger field. The agent is described in ATTac-2001: A Learning, Autonomous Bidding Agent, (PDF), (to appear in the proceedings of Workshop on Agent Mediated Electronic Commerce IV: Designing Mechanisms and Systems, 2002). The learning algorithm used in the agent is described in more detail in Modeling Auction Price Uncertainty Using Boosting-based Conditional Density Estimation, (PDF), (to appear in the proceedings of International Conference on Machine Learning (ICML), 2002).
[2001] Self-enforcing Strategic Demand Reduction (PDF) (Joint work with Paul S.A. Reitsma, Peter Stone, Michael L. Littman.) Another paper that grew out of work on the FCC spectrum auction (see below): "Auctions are an area of great academic and commercial interest, from tiny auctions for toys on eBay to multi-billion-dollar auctions held by governments for resources or contracts. Although there has been a good deal of research on auction theory, especially from the perspective of auction mechanisms, studies of autonomous bidding agents and their interactions are relatively few and recent. This paper examines several autonomous agent bidding strategies in the context of FAucS, a faithful simulation of a complex FCC spectrum auction. We introduce randomized strategic demand reduction (RSDR), a novel bidding strategy by which bidders can fairly partition available goods without explicit inter-agent communication. When all use RSDR, bidders obtain significantly better results than when using a reasonable baseline approach. The effects of non-cooperating bidders are examined, as well as both methods to make the scheme more robust to alternative conditions and methods to make the scheme self-enforcing. The RSDR strategy is fully implemented and we present detailed empirical results. We also suggest how to improve the efficiency of such an auction by a change of rules designed to prevent the deployment of RSDR." This paper will appear in the proceedings of Workshop on Agent Mediated Electronic Commerce IV: Designing Mechanisms and Systems, 2002.
[2001] FAucS: An FCC Spectrum Auction Simulator for Autonomous Bidding Agents (PDF) (Joint work with Michael L. Littman, Satinder Singh, Peter Stone.) At AT&T Labs -- Research, I worked on some applied auction theory: assisting AT&T's bidding team in the FCC spectrum auction, where about $17 billion was raised by selling wireless phone spectrum licences. AT&T and its allies spent about $3 billion. Some of this work we have been able to publish, starting with this paper: "We introduce FAucS, a software testbed for studying automated agent bidding strategies in simulated auctions, specifically the United States FCC wireless frequency spectrum auctions. In addition to the complexity of these auctions, which provides ample opportunities for intelligent approaches to bidding, this type of auction has huge commercial importance, each bringing in billions of dollars to governments around the world. We implement straightforward sample agents in FAucS and use them to replicate known beneficial bidding strategies in this type of auction. We then discuss potential in-depth studies of autonomous bidding agent behaviors using FAucS. The main contribution of this work is the implementation, description, and empirical validation of the FAucS testbed. We present it as a challenging and promising AI research domain." The FAucS software is available here. Some other data files that are of potential interest to researchers are provided here. Published in Fiege, L., Mühl, G., and Wilhelm, U. (eds), Electronic Commerce: Proceedings of the Second International Workshop, pp. 139-151, Springer, 2001.
[2002] Index assignment for two-channel quantization (PDF), (joint work with József Balogh). Back when József and I were both at AT&T Labs--Research, Suhas Diggavi and Vinay Vaishampayan told us about a neat problem that is ultimately combinatorial about spreads in a plane arrangement of integers that they had considered together with Alon Orlitsky. This paper considers (and solves exactly, for even N) that problem, and covers some related stuff. "This paper concerns the design of a multiple description scalar quantization system for two symmetric channels for an unbounded discrete information source. This translates to the combinatorial problem of finding an arrangement of the integers into the infinite plane square grid so that each row and each column contains exactly N numbers, such that the difference between any two numbers in the same row (or column) is at most d, with d to be minimized for a given N. The best previous bounds for the lowest d were N^2/3+O(N) and N^2/2+O(N). We give new lower and upper bounds, both of the form 3N^2/8+O(N). We also consider minimizing the maximal variance in any row or column and show that it must be at least 0.0167N^4, and that it does not have to be more than 0.0188N^4." One of the constructions in the paper relies on a number of small square arrangements (given here) which are not described in the paper. This paper has been submitted for publication.
[2000] The cost of exactly simulating a Bell pair using classical communication (PDF, dvi). At the MSRI Workshop on Quantum Computation I attended a very interesting lecture (available at the workshop Web page!) by Gilles Brassard on Trading entanglement for communication, where among other things, he explained a scheme to replace a quantum phenomenon by a classical phenomenon plus some communication. In this paper, an improved version of this scheme is presented: "The paper [Brassard, Cleve, Tapp, 1999] begins thus: ...Bell's celebrated theorem shows that certain scenarious involving bipartite quantum measurements result in correlations that are impossible to simulate with a classical system if the measurement events are spacelike separated. If the measurement events are timelike separated, then classical simulation is possible, at the expense of some communication. Our goal is to quantify the required amount of communication. ... In this note we tighten the bounds on the amount of communication required to simulate a von Neumann measurement on a Bell pair." This paper appeared in Phys. Review A 66, 014302 (2002).
[1992] Optimal Strategy for the First Player in the Penney Ante Game. In 1992, I was a first-year undergraduate when I attended Frank Kelly's introductory course in Probability. He challenged the audience to consider a certain problem, offering a chocolate orange to the person who gets closest to a solution. My solution is as follows (I got the chocolate orange for this, my most lucrative paper yet): "In the Penney Ante game two players choose one binary string of length k each in turn, and toss a coin repeatedly. If at some stage the last k outcomes match one of their strings, the player with that string wins. The case k<5 is somewhat exceptional and in any case easily done. For k at least 5, Guibas and Odlyzko proved that the second player's optimal strategy is to choose the first k-1 digits of the first player's string prefixed by 0 or 1. They conjectured that these two choices are never equally good. We prove that this conjecture is correct. Then we prove that 01...100 (with k-3 ones) is an optimal strategy for the first player, and find all the strategies that are equally good." Read all about it in Combinatorics, Probability and Computing (1992), 1, pp. 311-321.
This page was last edited on 28th August 2003, but pages linked from here might have been edited more recently. HTML 4.01.