7 Search Results for "Steger, Christian"

Document
DOI: 10.4230/LIPIcs.SEA.2026.27
Cycle Basis Algorithms for Reducing Maximum Edge Participation

Authors: Fan Wang and Sandy Irani

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
A cycle basis of a graph is a minimal set of cycles from which every cycle in the graph can be generated by symmetric difference. We study the problem of constructing cycle bases of graphs with low maximum edge participation, defined as the maximum number of cycles in the basis that share any single edge. This quantity, though less studied than total weight or length, plays a critical role in quantum fault tolerance, as it directly impacts the overhead of lattice surgery procedures used to implement an almost universal quantum gate set. Building on a recursive algorithm by Freedman and Hastings, we introduce a family of load-aware heuristics that adaptively select vertices and edges to minimize edge participation throughout the cycle basis construction. Our approach improves empirical performance on random regular graphs and on graphs derived from small quantum codes. We further analyze a simplified balls-into-bins process to establish lower bounds on edge participation. While the model differs from the cycle basis algorithm on real graphs, it captures what can be proven for our heuristics without using more complex graph theoretic properties related to the distribution of cycles in the graph. Our analysis suggests that the maximum load of all of our heuristics will be Ω(log² n). Our results indicate that careful cycle basis construction can yield significant practical benefits in the design of fault-tolerant quantum systems. Maximum edge participation has been studied in the graph theory literature under the name basis number, which is the minimum possible maximum edge participation over all cycle bases in a graph.
Cite as

Fan Wang and Sandy Irani. Cycle Basis Algorithms for Reducing Maximum Edge Participation. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 27:1-27:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.SEA.2026.27,
  author =	{Wang, Fan and Irani, Sandy},
  title =	{{Cycle Basis Algorithms for Reducing Maximum Edge Participation}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{27:1--27:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.27},
  URN =		{urn:nbn:de:0030-drops-260311},
  doi =		{10.4230/LIPIcs.SEA.2026.27},
  annote =	{Keywords: Graph algorithms, Cycle Basis, Quantum fault tolerance}
}
Document
DOI: 10.4230/LIPIcs.FUN.2026.39
Price of Locality in Permutation Mastermind: Are TikTok Influencers Chaotic Enough?

Authors: Bernardo Subercaseaux

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
In the permutation Mastermind game, the goal is to uncover a secret permutation σ^⋆ : [n] → [n] by making a series of guesses π₁, …, π_T which must also be permutations of [n], and receiving as feedback after guess π_t the number of positions i for which σ^⋆(i) = π_t(i). While the existing literature on permutation Mastermind suggests strategies in which π_t and π_{t+1} might be widely different permutations, a resurgence in popularity of this game as a TikTok trend shows that humans (or at least TikTok influencers) use strategies in which consecutive guesses are very similar. For example, it is common to see players attempt one transposition at a time and slowly see their score increase. Motivated by these observations, we study the theoretical impact of two forms of locality in permutation Mastermind strategies: 𝓁_k-local strategies, in which any two consecutive guesses differ in at most k positions, and the even more restrictive class of w_k-local strategies, in which consecutive guesses differ in a window of length at most k. We show that, in broad terms, the optimal number of guesses for local strategies is quadratic, and thus much worse than the O(n lg n) guesses that suffice for non-local strategies. We also show NP-hardness of the satisfiability version for 𝓁₃-local strategies, whereas in the 𝓁₂-local variant the problem admits a randomized polynomial-time algorithm.
Cite as

Bernardo Subercaseaux. Price of Locality in Permutation Mastermind: Are TikTok Influencers Chaotic Enough?. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 39:1-39:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{subercaseaux:LIPIcs.FUN.2026.39,
  author =	{Subercaseaux, Bernardo},
  title =	{{Price of Locality in Permutation Mastermind: Are TikTok Influencers Chaotic Enough?}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{39:1--39:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.39},
  URN =		{urn:nbn:de:0030-drops-257585},
  doi =		{10.4230/LIPIcs.FUN.2026.39},
  annote =	{Keywords: Permutation Mastermind, Locality, NP-hard}
}
Document
DOI: 10.4230/DagSemProc.07041.3
07041 Working Group – Towards Interfaces for Integrated Performance and Power Analysis and Simulation

Authors: Chris Bleakley, Tom Clerckx, Harald Devos, Matthias Grumer, Alex Janek, Ulrich Kremer, Christian W. Probst, Phillip Stanley-Marbell, Christian Steger, Vasanth Venkatachalam, and Manuel Wendt

Published in: Dagstuhl Seminar Proceedings, Volume 7041, Power-aware Computing Systems (2007)

Abstract
In the design and optimization of power-aware computing systems, it is often desired to estimate power consumption at various levels of abstraction, e.g., at the transistor, gate, RTL, behavioral or transaction levels. Tools for power estimation at these different levels of abstraction require specialized expertise, e.g., understanding of device physics for circuit-level power estimation, and as such are necessarily developed by different research communities. In the optimization of complete platforms however, it is desired to be able to obtain aggregate power and performance estimates for the different components of a system, and this requires the ability to model the system at a mixture of levels of abstraction. One approach to enabling such cross-abstraction modeling, is to define a mechanism for interchange of data between tools at different layers of abstraction, for both static analysis and simulation-based studies. This document presents preliminary discussions on the requirements of such an interface.
Cite as

Chris Bleakley, Tom Clerckx, Harald Devos, Matthias Grumer, Alex Janek, Ulrich Kremer, Christian W. Probst, Phillip Stanley-Marbell, Christian Steger, Vasanth Venkatachalam, and Manuel Wendt. 07041 Working Group – Towards Interfaces for Integrated Performance and Power Analysis and Simulation. In Power-aware Computing Systems. Dagstuhl Seminar Proceedings, Volume 7041, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{bleakley_et_al:DagSemProc.07041.3,
  author =	{Bleakley, Chris and Clerckx, Tom and Devos, Harald and Grumer, Matthias and Janek, Alex and Kremer, Ulrich and Probst, Christian W. and Stanley-Marbell, Phillip and Steger, Christian and Venkatachalam, Vasanth and Wendt, Manuel},
  title =	{{07041 Working Group – Towards Interfaces for Integrated Performance and Power Analysis and Simulation}},
  booktitle =	{Power-aware Computing Systems},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7041},
  editor =	{Luca Benini and Naehyuck Chang and Ulrich Kremer and Christian W. Probst},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07041.3},
  URN =		{urn:nbn:de:0030-drops-11072},
  doi =		{10.4230/DagSemProc.07041.3},
  annote =	{Keywords: Power Estimation Tools, Simulation, Tool Interfaces}
}
Document
DOI: 10.4230/DagSemProc.07041.4
Automist - A Tool for Automated Instruction Set Characterization of Embedded Processors

Authors: Manuel Wendt, Matthias Grumer, Christian Steger, and Ulrich Neffe

Published in: Dagstuhl Seminar Proceedings, Volume 7041, Power-aware Computing Systems (2007)

Abstract
The steadily increasing performance of mobile devices also implies a rise in power consumption. To counteract this trend it is mandatory to accomplish software power optimizations based on accurate power consumption models characterized for the processor. This paper presents an environment for automated instruction set characterization based on physical power measurements. Based on a detailed instruction set description a testbench generator creates all needed test programs for a complete characterization. Afterwards those programs are executed by the processor and the energy consumption is measured. For an accurate energy measurement a high performance sampling technique has been established, which can be either clock or energy driven.
Cite as

Manuel Wendt, Matthias Grumer, Christian Steger, and Ulrich Neffe. Automist - A Tool for Automated Instruction Set Characterization of Embedded Processors. In Power-aware Computing Systems. Dagstuhl Seminar Proceedings, Volume 7041, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{wendt_et_al:DagSemProc.07041.4,
  author =	{Wendt, Manuel and Grumer, Matthias and Steger, Christian and Neffe, Ulrich},
  title =	{{Automist - A Tool for Automated Instruction Set Characterization of Embedded Processors}},
  booktitle =	{Power-aware Computing Systems},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7041},
  editor =	{Luca Benini and Naehyuck Chang and Ulrich Kremer and Christian W. Probst},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07041.4},
  URN =		{urn:nbn:de:0030-drops-11097},
  doi =		{10.4230/DagSemProc.07041.4},
  annote =	{Keywords: Software energy estimation, automated processor characterization, testbench generator, current measurement, clock driven sampling, energy driven sampl}
}
Document
DOI: 10.4230/DagSemProc.07041.5
Compiler-based Software Power Peak Elimination on Smart Card Systems

Authors: Matthias Grumer, Manuel Wendt, Christian Steger, Reinhold Weiss, Ulrich Neffe, and Andreas Muehlberger

Published in: Dagstuhl Seminar Proceedings, Volume 7041, Power-aware Computing Systems (2007)

Abstract
RF-powered smart cards are widely used in different application areas today. For smart cards not only performance is an important attribute, but also the power consumed by a given application. The power consumed is heavily depending on the software executed on the system. The power profile, especially the power peaks, of an executed application influence the system stability and security. Flattening the power profile can thus increase the stability and security of a system. In this paper we present an optimization system that allows a reduction of power peaks based on a compiler optimization. The optimizations are done on different levels of the compiler. In the backend of the compiler we present new instruction scheduling algorithms. On the intermediate language level we propose the use of iterative compiling for reducing critical peaks.
Cite as

Matthias Grumer, Manuel Wendt, Christian Steger, Reinhold Weiss, Ulrich Neffe, and Andreas Muehlberger. Compiler-based Software Power Peak Elimination on Smart Card Systems. In Power-aware Computing Systems. Dagstuhl Seminar Proceedings, Volume 7041, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{grumer_et_al:DagSemProc.07041.5,
  author =	{Grumer, Matthias and Wendt, Manuel and Steger, Christian and Weiss, Reinhold and Neffe, Ulrich and Muehlberger, Andreas},
  title =	{{Compiler-based Software Power Peak Elimination on Smart Card Systems}},
  booktitle =	{Power-aware Computing Systems},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7041},
  editor =	{Luca Benini and Naehyuck Chang and Ulrich Kremer and Christian W. Probst},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07041.5},
  URN =		{urn:nbn:de:0030-drops-11030},
  doi =		{10.4230/DagSemProc.07041.5},
  annote =	{Keywords: Software power optimization, compiler optimization, peak reduction}
}
Document
DOI: 10.4230/DagSemProc.07041.9
Lifetime Extension of Higher Class UHF RFID Tags using special Power Management Techniques and Energy Harvesting Devices

Authors: Alex Janek, Christian Steger, Josef Preishuber-Pfluegl, and Markus Pistauer

Published in: Dagstuhl Seminar Proceedings, Volume 7041, Power-aware Computing Systems (2007)

Abstract
Enhanced RFID tag technology especially in the UHF frequency range provides extended functionality like high operating range and sensing and monitoring capabilities. Such functionality requiring extended system structures including data acquisition units, real time clocks and active transmitters causes a high energy consumption of the tag and requires an on board energy store (battery). As a key parameter of the reliability of an RFID system is the lifetime, the energy budget of the higher class tag has to be as balanced as possible. This can be achieved by using energy harvesting devices as additional power supply. The PowerTag project and thus this paper proposes special power management mechanisms in combination with special energy storage structures interfacing energy harvesting devices and dealing with their special requirements. First various power management and power saving techniques are simulated and their performance is evaluated. In a second step different implementation variants of energy storage structures are compared by using accurate simulation models of the various parts of the system. The results are compared to manufacturer given and guaranteed system performance parameters of a state-of-the-art higher class UHF RFID system. The presented approach combines two simulations for the design and the evaluation of different tag architectures and power saving techniques. Simulation results are showing an improvement of over 44\% of achievable lifetime applying the power saving techniques and power subsystem architectures presented in this paper, compared to a state-of-the-art higher class system.
Cite as

Alex Janek, Christian Steger, Josef Preishuber-Pfluegl, and Markus Pistauer. Lifetime Extension of Higher Class UHF RFID Tags using special Power Management Techniques and Energy Harvesting Devices. In Power-aware Computing Systems. Dagstuhl Seminar Proceedings, Volume 7041, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{janek_et_al:DagSemProc.07041.9,
  author =	{Janek, Alex and Steger, Christian and Preishuber-Pfluegl, Josef and Pistauer, Markus},
  title =	{{Lifetime Extension of Higher Class UHF RFID Tags using special Power Management Techniques and Energy Harvesting Devices}},
  booktitle =	{Power-aware Computing Systems},
  pages =	{1--20},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7041},
  editor =	{Luca Benini and Naehyuck Chang and Ulrich Kremer and Christian W. Probst},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07041.9},
  URN =		{urn:nbn:de:0030-drops-11041},
  doi =		{10.4230/DagSemProc.07041.9},
  annote =	{Keywords: Higher Class UHF RFID, Energy harvesting, Energy storage architectures, Lifetime extension}
}
Document
DOI: 10.4230/DagSemProc.05141.7
Methodologies for Designing Power-Aware Smart Card Systems

Authors: Christian Steger, Ulrich Neffe, Klaus Rothbart, Andreas Mühlberger, Edgar Rieger, and Reinhold Weiss

Published in: Dagstuhl Seminar Proceedings, Volume 5141, Power-aware Computing Systems (2005)

Abstract
Smart cards are some of the smallest computing platforms in use today. They have limited resources, but a huge number of functional requirements. The requirement for multi-application cards increases the demand for high performance and security even more, whereas the limits given by size and energy consumption remain constant. We describe new methodologies for designing and implementing entire systems with regard to power awareness and required performance. To make use of this power-saving potential, also the higher layers of the system - the operating system layer and the application domain layer - are required to be designed together with the rest of the system. HW/SW co-design methodologies enable the gain of system-level optimization. The first part presents the abstraction of smart cards to optimize system architecture and memory system. Both functional and transactional-level models are presented and discussed. The proposed design flow and preliminary results of the evaluation are depicted. Another central part of this methodology is a cycle-accurate instruction-set simulator for secure software development. The underlaying energy model is designed to decouple instruction and data dependent energy dissipation, which leads to an independent characterization process and allows stepwise model refinement to increase estimation accuracy. The model has been evaluated for a high-performance smart card CPU and an use-case for secure software is given.
Cite as

Christian Steger, Ulrich Neffe, Klaus Rothbart, Andreas Mühlberger, Edgar Rieger, and Reinhold Weiss. Methodologies for Designing Power-Aware Smart Card Systems. In Power-aware Computing Systems. Dagstuhl Seminar Proceedings, Volume 5141, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{steger_et_al:DagSemProc.05141.7,
  author =	{Steger, Christian and Neffe, Ulrich and Rothbart, Klaus and M\"{u}hlberger, Andreas and Rieger, Edgar and Weiss, Reinhold},
  title =	{{Methodologies for Designing Power-Aware Smart Card Systems}},
  booktitle =	{Power-aware Computing Systems},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5141},
  editor =	{Luca Benini and Ulrich Kremer and Christian W. Probst and Peter Schelkens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05141.7},
  URN =		{urn:nbn:de:0030-drops-3067},
  doi =		{10.4230/DagSemProc.05141.7},
  annote =	{Keywords: Smart cards, power awareness, HW/SW codesign, cycle-accurate instruction-set simulator}
}
  • Refine by Type
  • 7 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 4 2007
  • 1 2005

  • Refine by Author
  • 5 Steger, Christian
  • 3 Grumer, Matthias
  • 3 Neffe, Ulrich
  • 3 Wendt, Manuel
  • 2 Janek, Alex
  • Show More...

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

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorics
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 Cycle Basis
  • 1 Energy harvesting
  • 1 Energy storage architectures
  • 1 Graph algorithms
  • 1 HW/SW codesign
  • 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