16 Search Results for "Wang, Carol"

Document
DOI: 10.4230/DagMan.11.1.19
Conversational Agents: A Framework for Evaluation (CAFE) (Dagstuhl Perspectives Workshop 24352)

Authors: Christine Bauer, Li Chen, Nicola Ferro, Norbert Fuhr, Avishek Anand, Timo Breuer, Guglielmo Faggioli, Ophir Frieder, Hideo Joho, Jussi Karlgren, Johannes Kiesel, Bart P. Knijnenburg, Aldo Lipani, Lien Michiels, Andrea Papenmeier, Maria Soledad Pera, Mark Sanderson, Scott Sanner, Benno Stein, Johanne R. Trippas, Karin Verspoor, and Martijn C. Willemsen

Published in: Dagstuhl Manifestos, Volume 11, Issue 1 (2025)

Abstract
During the workshop, we deeply discussed what CONversational Information ACcess (CONIAC) is and its unique features, proposing a world model abstracting it, and defined the Conversational Agents Framework for Evaluation (CAFE) for the evaluation of CONIAC systems, consisting of six major components: 1) goals of the system’s stakeholders, 2) user tasks to be studied in the evaluation, 3) aspects of the users carrying out the tasks, 4) evaluation criteria to be considered, 5) evaluation methodology to be applied, and 6) measures for the quantitative criteria chosen.
Cite as

Christine Bauer, Li Chen, Nicola Ferro, Norbert Fuhr, Avishek Anand, Timo Breuer, Guglielmo Faggioli, Ophir Frieder, Hideo Joho, Jussi Karlgren, Johannes Kiesel, Bart P. Knijnenburg, Aldo Lipani, Lien Michiels, Andrea Papenmeier, Maria Soledad Pera, Mark Sanderson, Scott Sanner, Benno Stein, Johanne R. Trippas, Karin Verspoor, and Martijn C. Willemsen. Conversational Agents: A Framework for Evaluation (CAFE) (Dagstuhl Perspectives Workshop 24352). In Dagstuhl Manifestos, Volume 11, Issue 1, pp. 19-67, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{bauer_et_al:DagMan.11.1.19,
  author =	{Bauer, Christine and Chen, Li and Ferro, Nicola and Fuhr, Norbert and Anand, Avishek and Breuer, Timo and Faggioli, Guglielmo and Frieder, Ophir and Joho, Hideo and Karlgren, Jussi and Kiesel, Johannes and Knijnenburg, Bart P. and Lipani, Aldo and Michiels, Lien and Papenmeier, Andrea and Pera, Maria Soledad and Sanderson, Mark and Sanner, Scott and Stein, Benno and Trippas, Johanne R. and Verspoor, Karin and Willemsen, Martijn C.},
  title =	{{Conversational Agents: A Framework for Evaluation (CAFE) (Dagstuhl Perspectives Workshop 24352)}},
  pages =	{19--67},
  journal =	{Dagstuhl Manifestos},
  ISSN =	{2193-2433},
  year =	{2025},
  volume =	{11},
  number =	{1},
  editor =	{Bauer, Christine and Chen, Li and Ferro, Nicola and Fuhr, Norbert and Anand, Avishek and Breuer, Timo and Faggioli, Guglielmo and Frieder, Ophir and Joho, Hideo and Karlgren, Jussi and Kiesel, Johannes and Knijnenburg, Bart P. and Lipani, Aldo and Michiels, Lien and Papenmeier, Andrea and Pera, Maria Soledad and Sanderson, Mark and Sanner, Scott and Stein, Benno and Trippas, Johanne R. and Verspoor, Karin and Willemsen, Martijn C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagMan.11.1.19},
  URN =		{urn:nbn:de:0030-drops-252722},
  doi =		{10.4230/DagMan.11.1.19},
  annote =	{Keywords: Conversational Agents, Evaluation, Information Access}
}
Document
DOI: 10.4230/LIPIcs.AFT.2025.34
PvpAMM: A Perpetual Market for Unbalanced Long-Short Positions

Authors: Zhenhang Shang, Zhenyu Zhao, and Kani Chen

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

Abstract
Perpetual futures - swap contracts without expiration dates - are the most widely traded derivatives in cryptocurrency markets. Traditional perpetual trading relies on order books, which require substantial bilateral liquidity and face challenges in high-volatility environments. In this paper, we introduce pvpAMM, a peer-to-peer perpetual trading protocol based on automated market maker (AMM) principles. The protocol enables efficient settlement of long-short mismatched markets and drives positions toward equilibrium: when the minority leveraged side wins, their returns are amplified compared to conventional perpetual contracts, while the opposite occurs when the majority side prevails. We also propose arbitrage mechanisms to maintain economic equilibrium within the pvpAMM system. By incorporating liquidity providers (LPs), the protocol aligns more closely with traditional order book trading. Numerical experiments validate our theoretical findings.
Cite as

Zhenhang Shang, Zhenyu Zhao, and Kani Chen. PvpAMM: A Perpetual Market for Unbalanced Long-Short Positions. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 34:1-34:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{shang_et_al:LIPIcs.AFT.2025.34,
  author =	{Shang, Zhenhang and Zhao, Zhenyu and Chen, Kani},
  title =	{{PvpAMM: A Perpetual Market for Unbalanced Long-Short Positions}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{34:1--34: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.34},
  URN =		{urn:nbn:de:0030-drops-247534},
  doi =		{10.4230/LIPIcs.AFT.2025.34},
  annote =	{Keywords: Perpetuals, Decentralized Finance, Auto Market Making, Blockchain}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.43
Gabidulin Codes Achieve List Decoding Capacity with an Order-Optimal Column-To-Row Ratio

Authors: Zeyu Guo, Chaoping Xing, Chen Yuan, and Zihan Zhang

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
In this paper, we show that random Gabidulin codes of block length n and rate R achieve the (average-radius) list decoding capacity of radius 1-R-ε in the rank metric with an order-optimal column-to-row ratio of O(ε). This extends the recent work of Guo, Xing, Yuan, and Zhang (FOCS 2024), improving their column-to-row ratio from O(ε/n) to O(ε). For completeness, we also establish a matching lower bound on the column-to-row ratio for capacity-achieving Gabidulin codes in the rank metric. Our proof techniques build on the work of Guo and Zhang (FOCS 2023), who showed that randomly punctured Reed-Solomon codes over fields of quadratic size attain the generalized Singleton bound of Shangguan and Tamo (STOC 2020) in the Hamming metric. The proof of our lower bound follows the method of Alrabiah, Guruswami, and Li (SODA 2024) for codes in the Hamming metric.
Cite as

Zeyu Guo, Chaoping Xing, Chen Yuan, and Zihan Zhang. Gabidulin Codes Achieve List Decoding Capacity with an Order-Optimal Column-To-Row Ratio. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 43:1-43:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{guo_et_al:LIPIcs.APPROX/RANDOM.2025.43,
  author =	{Guo, Zeyu and Xing, Chaoping and Yuan, Chen and Zhang, Zihan},
  title =	{{Gabidulin Codes Achieve List Decoding Capacity with an Order-Optimal Column-To-Row Ratio}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{43:1--43:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.43},
  URN =		{urn:nbn:de:0030-drops-244095},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.43},
  annote =	{Keywords: coding theory, error-correcting codes, Gabidulin codes, rank-metric codes}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.53
Near-Optimal List-Recovery of Linear Code Families

Authors: Ray Li and Nikhil Shagrithaya

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We prove several results on linear codes achieving list-recovery capacity. We show that random linear codes achieve list-recovery capacity with constant output list size (independent of the alphabet size and length). That is, over alphabets of size at least 𝓁^Ω(1/ε), random linear codes of rate R are (1-R-ε, 𝓁, (𝓁/ε)^O(𝓁/ε))-list-recoverable for all R ∈ (0,1) and 𝓁. Together with a result of Levi, Mosheiff, and Shagrithaya, this implies that randomly punctured Reed-Solomon codes also achieve list-recovery capacity. We also prove that our output list size is near-optimal among all linear codes: all (1-R-ε, 𝓁, L)-list-recoverable linear codes must have L ≥ 𝓁^{Ω(R/ε)}. Our simple upper bound combines the Zyablov-Pinsker argument with recent bounds from Kopparty, Ron-Zewi, Saraf, Wootters, and Tamo on the maximum intersection of a "list-recovery ball" and a low-dimensional subspace with large distance. Our lower bound is inspired by a recent lower bound of Chen and Zhang.
Cite as

Ray Li and Nikhil Shagrithaya. Near-Optimal List-Recovery of Linear Code Families. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 53:1-53:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.APPROX/RANDOM.2025.53,
  author =	{Li, Ray and Shagrithaya, Nikhil},
  title =	{{Near-Optimal List-Recovery of Linear Code Families}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{53:1--53:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.53},
  URN =		{urn:nbn:de:0030-drops-244199},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.53},
  annote =	{Keywords: Error-Correcting Codes, Randomness, List-Recovery, Reed-Solomon Codes, Random Linear Codes}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.9
Optimal Competitive Ratio for Optimization Problems with Congestion Effects

Authors: Miriam Fischer, Dario Paccagnan, and Cosimo Vinci

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
In this work we study online optimization problems with congestion effects. These are problems where tasks arrive online and a decision maker is required to allocate them on the fly to available resources in order to minimize the cost suffered, which grows with the amount of resources used. This class of problems corresponds to the online counterpart of well-known studied problems, including optimization problems with diseconomies of scale [Konstantin Makarychev and Maxim Sviridenko, 2018], minimum cost in congestion games [Gairing and Paccagnan, 2023], and load balancing problems [Baruch Awerbuch et al., 1995]. Within this setting, our work settles the problem of designing online algorithms with optimal competitive ratio, i.e., algorithms whose incurred cost is as close as possible to that of an oracle with complete knowledge of the future instance ahead of time. We provide three contributions underpinning this result. First, we show that no online algorithm can achieve a competitive ratio below a given factor depending solely on the resource costs. Second, we show that, when guided by carefully modified cost functions, the greedy algorithm achieves a competitive ratio matching this lower bound and thus is optimal. Finally, we show how to compute such modified cost functions in polynomial time.
Cite as

Miriam Fischer, Dario Paccagnan, and Cosimo Vinci. Optimal Competitive Ratio for Optimization Problems with Congestion Effects. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 9:1-9:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.APPROX/RANDOM.2025.9,
  author =	{Fischer, Miriam and Paccagnan, Dario and Vinci, Cosimo},
  title =	{{Optimal Competitive Ratio for Optimization Problems with Congestion Effects}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{9:1--9:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.9},
  URN =		{urn:nbn:de:0030-drops-243754},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.9},
  annote =	{Keywords: Online Algorithms, Competitive Ratio, Algorithmic Game Theory, Greedy Algorithms, Congestion Games}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2025.14
Guiding Geospatial Analysis Processes in Dealing with Modifiable Areal Unit Problems

Authors: Guoray Cai and Yue Hao

Published in: LIPIcs, Volume 346, 13th International Conference on Geographic Information Science (GIScience 2025)

Abstract
Geospatial analysis has been widely applied in different domains for critical decision making. However, the results of spatial analysis are often plagued with uncertainties due to measurement errors, choice of data representations, and unintended transformation artifacts. A well known example of such problems is the Modifiable Areal Unit Problem (MAUP) which has well documented effects on the outcome of spatial analysis on area-aggregated data. Existing methods for addressing the effects of MAUP are limited, are technically complex, and are often inaccessible to practitioners. As a result, analysts tend to ignore the effects of MAUP in practice due to lack of expertise, high cognitive loads, and resource limitations. To address these challenges, this paper proposes a machine-guidance approach to augment the analyst’s capacity in mitigating the effect of MAUP. Based on an analysis of practical challenges faced by human analysts, we identified multiple opportunities for the machine to guide the analysts by alerting to the rise of MAUP, assessing the impact of MAUP, choosing mitigation methods, and generating visual guidance messages using GIS functions and tools. For each of the opportunities, we characterize the behavior patterns and the underlying guidance strategies that generate the behavior. We illustrate the behavior of machine guidance using a hotspot analysis scenario in the context of crime policing, where MAUP has strong effects on the patterns of crime hotspots. Finally, we describe the computational framework used to build a prototype guidance system and identify a number of research questions to be addressed. We conclude by discussing how the machine guidance approach could be an answer to some of the toughest problems in geospatial analysis.
Cite as

Guoray Cai and Yue Hao. Guiding Geospatial Analysis Processes in Dealing with Modifiable Areal Unit Problems. In 13th International Conference on Geographic Information Science (GIScience 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 346, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cai_et_al:LIPIcs.GIScience.2025.14,
  author =	{Cai, Guoray and Hao, Yue},
  title =	{{Guiding Geospatial Analysis Processes in Dealing with Modifiable Areal Unit Problems}},
  booktitle =	{13th International Conference on Geographic Information Science (GIScience 2025)},
  pages =	{14:1--14:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-378-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{346},
  editor =	{Sila-Nowicka, Katarzyna and Moore, Antoni and O'Sullivan, David and Adams, Benjamin and Gahegan, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2025.14},
  URN =		{urn:nbn:de:0030-drops-238433},
  doi =		{10.4230/LIPIcs.GIScience.2025.14},
  annote =	{Keywords: Machine Guidance, Geo-Spatial Analysis, Modifiable Areal Unit Problem (MAUP)}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.60
Random Reed-Solomon Codes Achieve the Half-Singleton Bound for Insertions and Deletions over Linear-Sized Alphabets

Authors: Roni Con, Zeyu Guo, Ray Li, and Zihan Zhang

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
In this paper, we prove that with high probability, random Reed-Solomon codes approach the half-Singleton bound - the optimal rate versus error tradeoff for linear insdel codes - with linear-sized alphabets. More precisely, we prove that, for any ε > 0 and positive integers n and k, with high probability, random Reed-Solomon codes of length n and dimension k can correct (1-ε)n-2k+1 adversarial insdel errors over alphabets of size n+2^{poly(1/ε)}k. This significantly improves upon the alphabet size demonstrated in the work of Con, Shpilka, and Tamo (IEEE TIT, 2023), who showed the existence of Reed-Solomon codes with exponential alphabet size Õ(binom(n,2k-1)²) precisely achieving the half-Singleton bound. Our methods are inspired by recent works on list-decoding Reed-Solomon codes. Brakensiek-Gopi-Makam (STOC 2023) showed that random Reed-Solomon codes are list-decodable up to capacity with exponential-sized alphabets, and Guo-Zhang (FOCS 2023) and Alrabiah-Guruswami-Li (STOC 2024) improved the alphabet-size to linear. We achieve a similar alphabet-size reduction by similarly establishing strong bounds on the probability that certain random rectangular matrices are full rank. To accomplish this in our insdel context, our proof combines the random matrix techniques from list-decoding with structural properties of Longest Common Subsequences.
Cite as

Roni Con, Zeyu Guo, Ray Li, and Zihan Zhang. Random Reed-Solomon Codes Achieve the Half-Singleton Bound for Insertions and Deletions over Linear-Sized Alphabets. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 60:1-60:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{con_et_al:LIPIcs.ICALP.2025.60,
  author =	{Con, Roni and Guo, Zeyu and Li, Ray and Zhang, Zihan},
  title =	{{Random Reed-Solomon Codes Achieve the Half-Singleton Bound for Insertions and Deletions over Linear-Sized Alphabets}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{60:1--60:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.60},
  URN =		{urn:nbn:de:0030-drops-234372},
  doi =		{10.4230/LIPIcs.ICALP.2025.60},
  annote =	{Keywords: coding theory, error-correcting codes, Reed-Solomon codes, insdel, insertion-deletion errors, half-Singleton bound}
}
Document
DOI: 10.4230/LIPIcs.FORC.2025.7
Kernel Multiaccuracy

Authors: Carol Xuan Long, Wael Alghamdi, Alexander Glynn, Yixuan Wu, and Flavio P. Calmon

Published in: LIPIcs, Volume 329, 6th Symposium on Foundations of Responsible Computing (FORC 2025)

Abstract
Predefined demographic groups often overlook the subpopulations most impacted by model errors, leading to a growing emphasis on data-driven methods that pinpoint where models underperform. The emerging field of multi-group fairness addresses this by ensuring models perform well across a wide range of group-defining functions, rather than relying on fixed demographic categories. We demonstrate that recently introduced notions of multi-group fairness can be equivalently formulated as integral probability metrics (IPM). IPMs are the common information-theoretic tool that underlie definitions such as multiaccuracy, multicalibration, and outcome indistinguishably. For multiaccuracy, this connection leads to a simple, yet powerful procedure for achieving multiaccuracy with respect to an infinite-dimensional class of functions defined by a reproducing kernel Hilbert space (RKHS): first perform a kernel regression of a model’s errors, then subtract the resulting function from a model’s predictions. We combine these results to develop a post-processing method that improves multiaccuracy with respect to bounded-norm functions in an RKHS, enjoys provable performance guarantees, and, in binary classification benchmarks, achieves favorable multiaccuracy relative to competing methods.
Cite as

Carol Xuan Long, Wael Alghamdi, Alexander Glynn, Yixuan Wu, and Flavio P. Calmon. Kernel Multiaccuracy. In 6th Symposium on Foundations of Responsible Computing (FORC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 329, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{long_et_al:LIPIcs.FORC.2025.7,
  author =	{Long, Carol Xuan and Alghamdi, Wael and Glynn, Alexander and Wu, Yixuan and Calmon, Flavio P.},
  title =	{{Kernel Multiaccuracy}},
  booktitle =	{6th Symposium on Foundations of Responsible Computing (FORC 2025)},
  pages =	{7:1--7:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-367-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{329},
  editor =	{Bun, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2025.7},
  URN =		{urn:nbn:de:0030-drops-231341},
  doi =		{10.4230/LIPIcs.FORC.2025.7},
  annote =	{Keywords: algorithmic fairness, integral probability metrics, information theory}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.12
Stable Matching with Interviews

Authors: Itai Ashlagi, Jiale Chen, Mohammad Roghani, and Amin Saberi

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
In several two-sided markets, including labor and dating, agents typically have limited information about their preferences prior to mutual interactions. This issue can result in matching frictions, as arising in the labor market for medical residencies, where high application rates are followed by a large number of interviews. Yet, the extensive literature on two-sided matching primarily focuses on models where agents know their preferences, leaving the interactions necessary for preference discovery largely overlooked. This paper studies this problem using an algorithmic approach, extending Gale-Shapley’s deferred acceptance to this context. Two algorithms are proposed. The first is an adaptive algorithm that expands upon Gale-Shapley’s deferred acceptance by incorporating interviews between applicants and positions. Similar to deferred acceptance, one side sequentially proposes to the other. However, the order of proposals is carefully chosen to ensure an interim stable matching is found. Furthermore, with high probability, the number of interviews conducted by each applicant or position is limited to O(log² n). In many seasonal markets, interactions occur more simultaneously, consisting of an initial interview phase followed by a clearing stage. We present a non-adaptive algorithm for generating a single stage set of in tiered random markets. The algorithm finds an interim stable matching in such markets while assigning no more than O(log³ n) interviews to each applicant or position.
Cite as

Itai Ashlagi, Jiale Chen, Mohammad Roghani, and Amin Saberi. Stable Matching with Interviews. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ashlagi_et_al:LIPIcs.ITCS.2025.12,
  author =	{Ashlagi, Itai and Chen, Jiale and Roghani, Mohammad and Saberi, Amin},
  title =	{{Stable Matching with Interviews}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{12:1--12:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.12},
  URN =		{urn:nbn:de:0030-drops-226402},
  doi =		{10.4230/LIPIcs.ITCS.2025.12},
  annote =	{Keywords: Stable Matching, Gale–Shapley Algorithm, Algorithmic Game Theory}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.93
Polynomials, Divided Differences, and Codes

Authors: S. Venkitesh

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
Multiplicity codes (Kopparty et al., J. ACM 2014) are multivariate polynomial codes where the codewords are described by evaluations of polynomials (with a degree bound) and their derivatives up to some order (the multiplicity parameter), on a suitably chosen affine set of points. While efficient decoding algorithms were known in some special cases of point sets, by a reduction to univariate multiplicity codes, a general algorithm for list decoding up to the distance of the code when the point set is an arbitrary finite grid, was obtained only recently (Bhandari et al., IEEE TIT 2023). This required the characteristic of the field to be zero or larger than the degree bound, which is somewhat necessary since list decoding up to distance with small output list size is not possible when the characteristic is significantly smaller than the degree. In this work, we present an alternative construction based on divided differences of polynomials, that conceptually resembles the classical multiplicity codes but has good list decodability "insensitive to the field characteristic". We obtain a simple algorithm that list decodes this code up to distance for arbitrary finite grids over all finite fields. Our construction can also be interpreted as a folded Reed-Muller code, which may be of independent interest.
Cite as

S. Venkitesh. Polynomials, Divided Differences, and Codes. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 93:1-93:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{venkitesh:LIPIcs.ITCS.2025.93,
  author =	{Venkitesh, S.},
  title =	{{Polynomials, Divided Differences, and Codes}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{93:1--93:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.93},
  URN =		{urn:nbn:de:0030-drops-227216},
  doi =		{10.4230/LIPIcs.ITCS.2025.93},
  annote =	{Keywords: Error-correcting code, polynomial code, Reed-Solomon code, Reed-Muller code, folded Reed-Solomon code, folded Reed-Muller code, multiplicity code, divided difference, q-derivative, polynomial method, list decoding, list decoding capacity, linear algebraic list decoding}
}
Document
Resource Paper
DOI: 10.4230/TGDK.2.2.4
FAIR Jupyter: A Knowledge Graph Approach to Semantic Sharing and Granular Exploration of a Computational Notebook Reproducibility Dataset

Authors: Sheeba Samuel and Daniel Mietchen

Published in: TGDK, Volume 2, Issue 2 (2024): Special Issue on Resources for Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 2, Issue 2

Abstract
The way in which data are shared can affect their utility and reusability. Here, we demonstrate how data that we had previously shared in bulk can be mobilized further through a knowledge graph that allows for much more granular exploration and interrogation. The original dataset is about the computational reproducibility of GitHub-hosted Jupyter notebooks associated with biomedical publications. It contains rich metadata about the publications, associated GitHub repositories and Jupyter notebooks, and the notebooks' reproducibility. We took this dataset, converted it into semantic triples and loaded these into a triple store to create a knowledge graph - FAIR Jupyter - that we made accessible via a web service. This enables granular data exploration and analysis through queries that can be tailored to specific use cases. Such queries may provide details about any of the variables from the original dataset, highlight relationships between them or combine some of the graph’s content with materials from corresponding external resources. We provide a collection of example queries addressing a range of use cases in research and education. We also outline how sets of such queries can be used to profile specific content types, either individually or by class. We conclude by discussing how such a semantically enhanced sharing of complex datasets can both enhance their FAIRness - i.e., their findability, accessibility, interoperability, and reusability - and help identify and communicate best practices, particularly with regards to data quality, standardization, automation and reproducibility.
Cite as

Sheeba Samuel and Daniel Mietchen. FAIR Jupyter: A Knowledge Graph Approach to Semantic Sharing and Granular Exploration of a Computational Notebook Reproducibility Dataset. In Special Issue on Resources for Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 2, Issue 2, pp. 4:1-4:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{samuel_et_al:TGDK.2.2.4,
  author =	{Samuel, Sheeba and Mietchen, Daniel},
  title =	{{FAIR Jupyter: A Knowledge Graph Approach to Semantic Sharing and Granular Exploration of a Computational Notebook Reproducibility Dataset}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{4:1--4:24},
  ISSN =	{2942-7517},
  year =	{2024},
  volume =	{2},
  number =	{2},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.2.2.4},
  URN =		{urn:nbn:de:0030-drops-225886},
  doi =		{10.4230/TGDK.2.2.4},
  annote =	{Keywords: Knowledge Graph, Computational reproducibility, Jupyter notebooks, FAIR data, PubMed Central, GitHub, Python, SPARQL}
}
Document
Position
DOI: 10.4230/TGDK.2.1.5
Standardizing Knowledge Engineering Practices with a Reference Architecture

Authors: Bradley P. Allen and Filip Ilievski

Published in: TGDK, Volume 2, Issue 1 (2024): Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge, Volume 2, Issue 1

Abstract
Knowledge engineering is the process of creating and maintaining knowledge-producing systems. Throughout the history of computer science and AI, knowledge engineering workflows have been widely used given the importance of high-quality knowledge for reliable intelligent agents. Meanwhile, the scope of knowledge engineering, as apparent from its target tasks and use cases, has been shifting, together with its paradigms such as expert systems, semantic web, and language modeling. The intended use cases and supported user requirements between these paradigms have not been analyzed globally, as new paradigms often satisfy prior pain points while possibly introducing new ones. The recent abstraction of systemic patterns into a boxology provides an opening for aligning the requirements and use cases of knowledge engineering with the systems, components, and software that can satisfy them best, however, this direction has not been explored to date. This paper proposes a vision of harmonizing the best practices in the field of knowledge engineering by leveraging the software engineering methodology of creating reference architectures. We describe how a reference architecture can be iteratively designed and implemented to associate user needs with recurring systemic patterns, building on top of existing knowledge engineering workflows and boxologies. We provide a six-step roadmap that can enable the development of such an architecture, consisting of scope definition, selection of information sources, architectural analysis, synthesis of an architecture based on the information source analysis, evaluation through instantiation, and, ultimately, instantiation into a concrete software architecture. We provide an initial design and outcome of the definition of architectural scope, selection of information sources, and analysis. As the remaining steps of design, evaluation, and instantiation of the architecture are largely use-case specific, we provide a detailed description of their procedures and point to relevant examples. We expect that following through on this vision will lead to well-grounded reference architectures for knowledge engineering, will advance the ongoing initiatives of organizing the neurosymbolic knowledge engineering space, and will build new links to the software architectures and data science communities.
Cite as

Bradley P. Allen and Filip Ilievski. Standardizing Knowledge Engineering Practices with a Reference Architecture. In Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge (TGDK), Volume 2, Issue 1, pp. 5:1-5:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{allen_et_al:TGDK.2.1.5,
  author =	{Allen, Bradley P. and Ilievski, Filip},
  title =	{{Standardizing Knowledge Engineering Practices with a Reference Architecture}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{5:1--5:23},
  ISSN =	{2942-7517},
  year =	{2024},
  volume =	{2},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.2.1.5},
  URN =		{urn:nbn:de:0030-drops-198623},
  doi =		{10.4230/TGDK.2.1.5},
  annote =	{Keywords: knowledge engineering, knowledge graphs, quality attributes, software architectures, sociotechnical systems}
}
Document
Position
DOI: 10.4230/TGDK.1.1.5
Knowledge Graphs for the Life Sciences: Recent Developments, Challenges and Opportunities

Authors: Jiaoyan Chen, Hang Dong, Janna Hastings, Ernesto Jiménez-Ruiz, Vanessa López, Pierre Monnin, Catia Pesquita, Petr Škoda, and Valentina Tamma

Published in: TGDK, Volume 1, Issue 1 (2023): Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 1, Issue 1

Abstract
The term life sciences refers to the disciplines that study living organisms and life processes, and include chemistry, biology, medicine, and a range of other related disciplines. Research efforts in life sciences are heavily data-driven, as they produce and consume vast amounts of scientific data, much of which is intrinsically relational and graph-structured. The volume of data and the complexity of scientific concepts and relations referred to therein promote the application of advanced knowledge-driven technologies for managing and interpreting data, with the ultimate aim to advance scientific discovery. In this survey and position paper, we discuss recent developments and advances in the use of graph-based technologies in life sciences and set out a vision for how these technologies will impact these fields into the future. We focus on three broad topics: the construction and management of Knowledge Graphs (KGs), the use of KGs and associated technologies in the discovery of new knowledge, and the use of KGs in artificial intelligence applications to support explanations (explainable AI). We select a few exemplary use cases for each topic, discuss the challenges and open research questions within these topics, and conclude with a perspective and outlook that summarizes the overarching challenges and their potential solutions as a guide for future research.
Cite as

Jiaoyan Chen, Hang Dong, Janna Hastings, Ernesto Jiménez-Ruiz, Vanessa López, Pierre Monnin, Catia Pesquita, Petr Škoda, and Valentina Tamma. Knowledge Graphs for the Life Sciences: Recent Developments, Challenges and Opportunities. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 5:1-5:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{chen_et_al:TGDK.1.1.5,
  author =	{Chen, Jiaoyan and Dong, Hang and Hastings, Janna and Jim\'{e}nez-Ruiz, Ernesto and L\'{o}pez, Vanessa and Monnin, Pierre and Pesquita, Catia and \v{S}koda, Petr and Tamma, Valentina},
  title =	{{Knowledge Graphs for the Life Sciences: Recent Developments, Challenges and Opportunities}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{5:1--5:33},
  year =	{2023},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.1.1.5},
  URN =		{urn:nbn:de:0030-drops-194791},
  doi =		{10.4230/TGDK.1.1.5},
  annote =	{Keywords: Knowledge graphs, Life science, Knowledge discovery, Explainable AI}
}
Document
DOI: 10.4230/LITES.7.1.2
We know what you're doing! Application detection using thermal data

Authors: Philipp Miedl, Rehan Ahmed, and Lothar Thiele

Published in: LITES, Volume 7, Issue 1 (2021): Special Issue on Embedded System Security. Leibniz Transactions on Embedded Systems, Volume 7, Issue 1

Abstract
Modern mobile and embedded devices have high computing power which allows them to be used for multiple purposes. Therefore, applications with low security restrictions may execute on the same device as applications handling highly sensitive information. In such a setup, a security risk occurs if it is possible that an application uses system characteristics to gather information about another application on the same device.In this work, we present a method to leak sensitive runtime information by just using temperature sensor readings of a mobile device. We employ a Convolutional-Neural-Network, Long Short-Term Memory units and subsequent label sequence processing to identify the sequence of executed applications over time. To test our hypothesis we collect data from two state-of-the-art smartphones and real user usage patterns. We show an extensive evaluation using laboratory data, where we achieve labelling accuracies up to 90% and negligible timing error. Based on our analysis we state that the thermal information can be used to compromise sensitive user data and increase the vulnerability of mobile devices. A study based on data collected outside of the laboratory opens up various future directions for research.
Cite as

Philipp Miedl, Rehan Ahmed, and Lothar Thiele. We know what you're doing! Application detection using thermal data. In LITES, Volume 7, Issue 1 (2021): Special Issue on Embedded System Security. Leibniz Transactions on Embedded Systems, Volume 7, Issue 1, pp. 02:1-02:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Article{miedl_et_al:LITES.7.1.2,
  author =	{Miedl, Philipp and Ahmed, Rehan and Thiele, Lothar},
  title =	{{We know what you're doing! Application detection using thermal data}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{02:1--02:28},
  ISSN =	{2199-2002},
  year =	{2021},
  volume =	{7},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.7.1.2},
  URN =		{urn:nbn:de:0030-drops-192850},
  doi =		{10.4230/LITES.7.1.2},
  annote =	{Keywords: Thermal Monitoring, Side Channel, Data Leak, Sequence Labelling}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.867
Deletion Codes in the High-noise and High-rate Regimes

Authors: Venkatesan Guruswami and Carol Wang

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract
The noise model of deletions poses significant challenges in coding theory, with basic questions like the capacity of the binary deletion channel still being open. In this paper, we study the harder model of worst-case deletions, with a focus on constructing efficiently encodable and decodable codes for the two extreme regimes of high-noise and high-rate. Specifically, we construct polynomial-time decodable codes with the following trade-offs (for any epsilon > 0): (1) Codes that can correct a fraction 1-epsilon of deletions with rate poly(eps) over an alphabet of size poly(1/epsilon); (2) Binary codes of rate 1-O~(sqrt(epsilon)) that can correct a fraction eps of deletions; and (3) Binary codes that can be list decoded from a fraction (1/2-epsilon) of deletions with rate poly(epsion) Our work is the first to achieve the qualitative goals of correcting a deletion fraction approaching 1 over bounded alphabets, and correcting a constant fraction of bit deletions with rate aproaching 1. The above results bring our understanding of deletion code constructions in these regimes to a similar level as worst-case errors.
Cite as

Venkatesan Guruswami and Carol Wang. Deletion Codes in the High-noise and High-rate Regimes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 867-880, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{guruswami_et_al:LIPIcs.APPROX-RANDOM.2015.867,
  author =	{Guruswami, Venkatesan and Wang, Carol},
  title =	{{Deletion Codes in the High-noise and High-rate Regimes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{867--880},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.867},
  URN =		{urn:nbn:de:0030-drops-53417},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.867},
  annote =	{Keywords: algorithmic coding theory, deletion codes, list decoding, probabilistic method, explicit constructions}
}
  • Refine by Type
  • 16 Document/PDF
  • 12 Document/HTML

  • Refine by Publication Year
  • 10 2025
  • 2 2024
  • 1 2023
  • 1 2021
  • 1 2015
  • Show More...

  • Refine by Author
  • 2 Guo, Zeyu
  • 2 Guruswami, Venkatesan
  • 2 Li, Ray
  • 2 Wang, Carol
  • 2 Zhang, Zihan
  • Show More...

  • Refine by Series/Journal
  • 11 LIPIcs
  • 1 LITES
  • 3 TGDK
  • 1 DagMan

  • Refine by Classification
  • 4 Mathematics of computing → Coding theory
  • 2 Computing methodologies → Knowledge representation and reasoning
  • 2 Theory of computation → Algorithmic game theory
  • 1 Applied computing → Digital cash
  • 1 Applied computing → Life and medical sciences
  • Show More...

  • Refine by Keyword
  • 2 Algorithmic Game Theory
  • 2 coding theory
  • 2 error-correcting codes
  • 2 explicit constructions
  • 2 list decoding
  • 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