Tight Bounds for Sorting Under Partial Information.
- ,
- Daniel Rutschmann
- Technical University of Denmark
Research Output:
Conference Article in Proceeding or Book/Report chapter
Article in proceedings
Peer-review
Open access
Publication Information
Output type
Research Output:
Conference Article in Proceeding or Book/Report chapter
Article in proceedings
Peer-reviewOriginal language
EnglishPages from-to (Number of pages)
Pages 2243-2252 (10 pages)Publication milestones
- Published - 2024
Publication status
Published - 2024
Edition
65Publisher
IEEE, United StatesISBN (Print)
979-8-3315-1675-8ISBN (Electronic)
979-8-3315-1674-1Publication IDs
- Scopus: 85206936593
Host publication title
2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)Abstract
Sorting is one of the fundamental algorithmic problems in theoretical computer science. It has a natural generalization, introduced by Fredman in 1976, called sorting under partial information. The input consists of: –a ground set X of size n, –a partial oracle OF (where partial oracle queries for any (xi,xj) output whether xi≺Pxj, for some partial order P), –a linear oracle OL (where linear oracle queries for any (xi,xj) output whether xi
Publication metrics
PlumX, opens in new tab
Citations
4
Captures
3
Access to documents
License:Unspecified
Related Event
Title
Symposium on Foundations of Computer Science
Event type
ConferenceDegree of recognition
International eventDate
27/10/2024 - 30/10/2024Location
ChicagoUnited States