2 Search Results for "Natarajan, Raja"

Document
DOI: 10.4230/LIPIcs.AFT.2025.25
The Exchange Problem

Authors: Mohit Garg and Suneel Sarswat

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract
Auctions are widely used in exchanges to match buy and sell requests. Once the buyers and sellers place their requests, the exchange determines how these requests are to be matched. The two most popular objectives used while determining the matching are maximizing volume with dynamic pricing and maximizing volume at a uniform price. In this work, we study the algorithmic complexity of the problems arising from these matching tasks. For dynamic-price matching, we establish a lower bound of Ω(n log n) on the running time, thereby proving that the currently best-known O(n log n) algorithm is time-optimal. In contrast, for uniform-price matching, we present a linear-time algorithm, improving upon previous methods that require O(n log n) time to match n requests.
Cite as

Mohit Garg and Suneel Sarswat. The Exchange Problem. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 25:1-25:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.AFT.2025.25,
  author =	{Garg, Mohit and Sarswat, Suneel},
  title =	{{The Exchange Problem}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{25:1--25:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.25},
  URN =		{urn:nbn:de:0030-drops-247449},
  doi =		{10.4230/LIPIcs.AFT.2025.25},
  annote =	{Keywords: Exchanges, Double Auctions, Matching Algorithms, Element Distinctness, Time Complexity}
}
Document
DOI: 10.4230/LIPIcs.ITP.2021.28
Verified Double Sided Auctions for Financial Markets

Authors: Raja Natarajan, Suneel Sarswat, and Abhishek Kr Singh

Published in: LIPIcs, Volume 193, 12th International Conference on Interactive Theorem Proving (ITP 2021)

Abstract
Double sided auctions are widely used in financial markets to match demand and supply. Prior works on double sided auctions have focused primarily on single quantity trade requests. We extend various notions of double sided auctions to incorporate multiple quantity trade requests and provide fully formalized matching algorithms for double sided auctions with their correctness proofs. We establish new uniqueness theorems that enable automatic detection of violations in an exchange program by comparing its output with that of a verified program. All proofs are formalized in the Coq proof assistant without adding any axiom to the system. We extract verified OCaml and Haskell programs that can be used by the exchanges and the regulators of the financial markets. We demonstrate the practical applicability of our work by running the verified program on real market data from an exchange to automatically check for violations in the exchange algorithm.
Cite as

Raja Natarajan, Suneel Sarswat, and Abhishek Kr Singh. Verified Double Sided Auctions for Financial Markets. In 12th International Conference on Interactive Theorem Proving (ITP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 193, pp. 28:1-28:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{natarajan_et_al:LIPIcs.ITP.2021.28,
  author =	{Natarajan, Raja and Sarswat, Suneel and Singh, Abhishek Kr},
  title =	{{Verified Double Sided Auctions for Financial Markets}},
  booktitle =	{12th International Conference on Interactive Theorem Proving (ITP 2021)},
  pages =	{28:1--28:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-188-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{193},
  editor =	{Cohen, Liron and Kaliszyk, Cezary},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2021.28},
  URN =		{urn:nbn:de:0030-drops-139230},
  doi =		{10.4230/LIPIcs.ITP.2021.28},
  annote =	{Keywords: Double Sided Auction, Formal Verification, Financial Markets, Proof Assistant}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2021

  • Refine by Author
  • 2 Sarswat, Suneel
  • 1 Garg, Mohit
  • 1 Natarajan, Raja
  • 1 Singh, Abhishek Kr

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 1 Applied computing → Electronic commerce
  • 1 Information systems → Online auctions
  • 1 Software and its engineering → Formal software verification
  • 1 Theory of computation → Algorithmic mechanism design
  • 1 Theory of computation → Automated reasoning
  • Show More...

  • Refine by Keyword
  • 1 Double Auctions
  • 1 Double Sided Auction
  • 1 Element Distinctness
  • 1 Exchanges
  • 1 Financial Markets
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact