3 Search Results for "Sezgin, Ali"

Document
DOI: 10.4230/LIPIcs.SoCG.2026.26
Finding a Fair Scoring Function for Top-k Selection: From Hardness to Practice

Authors: Guangya Cai

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
We study the problem of finding a fair linear scoring function over (numerical) attributes for top-k selection, ensuring fairness through a proportional representation constraint on the protected group. Existing algorithms do not scale efficiently, particularly in higher dimensions. Our hardness analysis shows that in more than two dimensions, no algorithm is likely to scale efficiently with respect to dataset size, and the computational complexity is likely to grow rapidly with dimensionality. However, the hardness results also provide key insights guiding algorithm design, leading to our two-pronged solution: (1) For small k, our analysis reveals a gap in the hardness barrier. By addressing various engineering challenges, including achieving efficient parallelism, we turn this potential of efficiency into an optimized geometry-based algorithm delivering substantial performance gains. (2) For large k, where the hardness is robust, we employ a practically efficient optimization-based algorithm which, despite being theoretically worse, achieves superior real-world performance. Experimental evaluations on real-world datasets then explore scenarios where worst-case behavior does not manifest, identifying areas critical to practical performance. Our solution achieves speedups of up to several orders of magnitude compared to the state of the art, an efficiency made possible through a tight integration of hardness analysis, algorithm design, practical engineering, and empirical evaluation.
Cite as

Guangya Cai. Finding a Fair Scoring Function for Top-k Selection: From Hardness to Practice. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cai:LIPIcs.SoCG.2026.26,
  author =	{Cai, Guangya},
  title =	{{Finding a Fair Scoring Function for Top-k Selection: From Hardness to Practice}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{26:1--26:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.26},
  URN =		{urn:nbn:de:0030-drops-258320},
  doi =		{10.4230/LIPIcs.SoCG.2026.26},
  annote =	{Keywords: Fairness, Top-k, Integration}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2016.6
Local Linearizability for Concurrent Container-Type Data Structures

Authors: Andreas Haas, Thomas A. Henzinger, Andreas Holzer, Christoph M. Kirsch, Michael Lippautz, Hannes Payer, Ali Sezgin, Ana Sokolova, and Helmut Veith

Published in: LIPIcs, Volume 59, 27th International Conference on Concurrency Theory (CONCUR 2016)

Abstract
The semantics of concurrent data structures is usually given by a sequential specification and a consistency condition. Linearizability is the most popular consistency condition due to its simplicity and general applicability. Nevertheless, for applications that do not require all guarantees offered by linearizability, recent research has focused on improving performance and scalability of concurrent data structures by relaxing their semantics. In this paper, we present local linearizability, a relaxed consistency condition that is applicable to container-type concurrent data structures like pools, queues, and stacks. While linearizability requires that the effect of each operation is observed by all threads at the same time, local linearizability only requires that for each thread T, the effects of its local insertion operations and the effects of those removal operations that remove values inserted by T are observed by all threads at the same time. We investigate theoretical and practical properties of local linearizability and its relationship to many existing consistency conditions. We present a generic implementation method for locally linearizable data structures that uses existing linearizable data structures as building blocks. Our implementations show performance and scalability improvements over the original building blocks and outperform the fastest existing container-type implementations.
Cite as

Andreas Haas, Thomas A. Henzinger, Andreas Holzer, Christoph M. Kirsch, Michael Lippautz, Hannes Payer, Ali Sezgin, Ana Sokolova, and Helmut Veith. Local Linearizability for Concurrent Container-Type Data Structures. In 27th International Conference on Concurrency Theory (CONCUR 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 59, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{haas_et_al:LIPIcs.CONCUR.2016.6,
  author =	{Haas, Andreas and Henzinger, Thomas A. and Holzer, Andreas and Kirsch, Christoph M. and Lippautz, Michael and Payer, Hannes and Sezgin, Ali and Sokolova, Ana and Veith, Helmut},
  title =	{{Local Linearizability for Concurrent Container-Type Data Structures}},
  booktitle =	{27th International Conference on Concurrency Theory (CONCUR 2016)},
  pages =	{6:1--6:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-017-0},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{59},
  editor =	{Desharnais, Jos\'{e}e and Jagadeesan, Radha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2016.6},
  URN =		{urn:nbn:de:0030-drops-61809},
  doi =		{10.4230/LIPIcs.CONCUR.2016.6},
  annote =	{Keywords: (concurrent) data structures, relaxed semantics, linearizability}
}
Document
DOI: 10.4230/DagSemProc.09361.2
Verifying Optimistic Concurrency: Prophecy Variables and Backward Reasoning

Authors: Serdar Tasiran, Ali Sezgin, and Shaz Quadeer

Published in: Dagstuhl Seminar Proceedings, Volume 9361, Design and Validation of Concurrent Systems (2010)

Abstract
Several static proof systems have been developed over the years for verifying shared-memory multithreaded programs. These proof systems make use of auxiliary variables to express mutual exclusion or non-interference among shared variable accesses. Typically, the values of these variables summarize the past of the program execution; consequently, they are known as history variables. Prophecy variables, on the other hand, are the temporal dual of history variables and their values summarize the future of the program execution. In this paper, we show that prophecy variables are useful for locally constructing proofs of systems with optimistic concurrency. To enable the fullest use of prophecy variables in proof construction, we introduce tressa annotations, as the dual of the well-known assert annotations. A tressa claim states a condition for reverse reachability from an end state of the program, much like an assert claim states a condition for forward reachability from the initial state of the program. We present the proof rules and the notion of correctness of a program for two-way reasoning in a static setting: forward in time for assert claims, backward in time for tressa claims. Even though the interaction between the two is non-trivial, the formalization is intuitive and accessible. We demonstrate how to verify implementations based on optimistic concurrency which is a programming paradigm that allows conflicts to be handled after they occur. We have incorporated our proof rules into the QED verifier and have used our implementation to verify a handful of small but sophisticated algorithms. Our experience shows that the proof steps and annotations follow closely the intuition of the programmer, making the proof itself a natural extension of implementation.
Cite as

Serdar Tasiran, Ali Sezgin, and Shaz Quadeer. Verifying Optimistic Concurrency: Prophecy Variables and Backward Reasoning. In Design and Validation of Concurrent Systems. Dagstuhl Seminar Proceedings, Volume 9361, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{tasiran_et_al:DagSemProc.09361.2,
  author =	{Tasiran, Serdar and Sezgin, Ali and Quadeer, Shaz},
  title =	{{Verifying Optimistic Concurrency: Prophecy Variables and Backward Reasoning}},
  booktitle =	{Design and Validation of Concurrent Systems},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9361},
  editor =	{Cormac Flanagan and Madhusan Parthasarathy and Shaz Quadeer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09361.2},
  URN =		{urn:nbn:de:0030-drops-24306},
  doi =		{10.4230/DagSemProc.09361.2},
  annote =	{Keywords: Concurrency, Program Verification, Static Analysis}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2016
  • 1 2010

  • Refine by Author
  • 2 Sezgin, Ali
  • 1 Cai, Guangya
  • 1 Haas, Andreas
  • 1 Henzinger, Thomas A.
  • 1 Holzer, Andreas
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs
  • 1 DagSemProc

  • Refine by Classification
  • 1 Information systems → Top-k retrieval in databases

  • Refine by Keyword
  • 1 (concurrent) data structures
  • 1 Concurrency
  • 1 Fairness
  • 1 Integration
  • 1 Program Verification
  • 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