2 Search Results for "MacKie-Mason, Jeffrey"

Document

DOI: 10.4230/LIPIcs.CCC.2024.25

On the Degree of Polynomials Computing Square Roots Mod p

Authors: Kiran S. Kedlaya and Swastik Kopparty

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract

For an odd prime p, we say f(X) ∈ F_p[X] computes square roots in F_p if, for all nonzero perfect squares a ∈ F_p, we have f(a)² = a. When p ≡ 3 mod 4, it is well known that f(X) = X^{(p+1)/4} computes square roots. This degree is surprisingly low (and in fact lowest possible), since we have specified (p-1)/2 evaluations (up to sign) of the polynomial f(X). On the other hand, for p ≡ 1 mod 4 there was previously no nontrivial bound known on the lowest degree of a polynomial computing square roots in F_p. We show that for all p ≡ 1 mod 4, the degree of a polynomial computing square roots has degree at least p/3. Our main new ingredient is a general lemma which may be of independent interest: powers of a low degree polynomial cannot have too many consecutive zero coefficients. The proof method also yields a robust version: any polynomial that computes square roots for 99% of the squares also has degree almost p/3. In the other direction, Agou, Deliglése, and Nicolas [Agou et al., 2003] showed that for infinitely many p ≡ 1 mod 4, the degree of a polynomial computing square roots can be as small as 3p/8.

Cite as

Kiran S. Kedlaya and Swastik Kopparty. On the Degree of Polynomials Computing Square Roots Mod p. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kedlaya_et_al:LIPIcs.CCC.2024.25,
  author =	{Kedlaya, Kiran S. and Kopparty, Swastik},
  title =	{{On the Degree of Polynomials Computing Square Roots Mod p}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{25:1--25:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.25},
  URN =		{urn:nbn:de:0030-drops-204219},
  doi =		{10.4230/LIPIcs.CCC.2024.25},
  annote =	{Keywords: Algebraic Computation, Polynomials, Computing Square roots, Reed-Solomon Codes}
}

Document

DOI: 10.4230/DagSemProc.05011.14

Self-Confirming Price Prediction for Bidding in Simultaneous Ascending Auctions

Authors: Anna Osepayshvili, Michael Wellman, Daniel Reeves, and Jeffrey MacKie-Mason

Published in: Dagstuhl Seminar Proceedings, Volume 5011, Computing and Markets (2005)

Abstract

Simultaneous, separate ascending auctions are ubiquitous, even when agents have preferences over combinations of goods, from which arises the emph{exposure problem}. Little is known about strategies that perform well when the exposure problem is important. We present a new family of bidding strategies for this situation, in which agents form and utilize various amounts of information from predictions of the distribution of final prices. The predictor strategies we define differ in their choice of method for generating the initial (pre-auction) prediction. We explore several methods, but focus on emph{self-confirming} predictions. An agents prediction of characteristics of the distribution of closing prices is self-confirming if, when all agents follow the same predictor bidding strategy, the final price distributions that actually result are consistent with the utilized characteristics of the prediction. We extensively analyze an auction environment with five goods, and five agents who each can choose from 53 different bidding strategies (resulting in over 4.2 million distinct strategy combinations). We find that the self-confirming distribution predictor is a highly stable, pure-strategy Nash equilibrium. We have been unable to find any other Nash strategies in this environment. In limited experiments in other environments the self-confirming distribution predictor consistently performs well, but is not generally a pure-strategy Nash equilibrium.

Cite as

Anna Osepayshvili, Michael Wellman, Daniel Reeves, and Jeffrey MacKie-Mason. Self-Confirming Price Prediction for Bidding in Simultaneous Ascending Auctions. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{osepayshvili_et_al:DagSemProc.05011.14,
  author =	{Osepayshvili, Anna and Wellman, Michael and Reeves, Daniel and MacKie-Mason, Jeffrey},
  title =	{{Self-Confirming Price Prediction for Bidding in Simultaneous Ascending Auctions}},
  booktitle =	{Computing and Markets},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5011},
  editor =	{Daniel Lehmann and Rudolf M\"{u}ller and Tuomas Sandholm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.14},
  URN =		{urn:nbn:de:0030-drops-2020},
  doi =		{10.4230/DagSemProc.05011.14},
  annote =	{Keywords: compact representation of games, congestion games, local-effect games, action-graph gamescomputational markets; auctions; bidding strategies}
}

Refine by Author
1 Kedlaya, Kiran S.
1 Kopparty, Swastik
1 MacKie-Mason, Jeffrey
1 Osepayshvili, Anna
1 Reeves, Daniel
Show More...

Refine by Classification
1 Computing methodologies → Number theory algorithms
1 Computing methodologies → Representation of mathematical functions
1 Mathematics of computing → Coding theory

Refine by Keyword
1 Algebraic Computation
1 Computing Square roots
1 Polynomials
1 Reed-Solomon Codes
1 action-graph gamescomputational markets; auctions; bidding strategies
Show More...

Refine by Type
2 document

Refine by Publication Year
1 2005
1 2024