15 Search Results for "Sch�nw�lder, J�rgen"

Document
DOI: 10.4230/LIPIcs.STACS.2024.9
Testing Equivalence to Design Polynomials

Authors: Omkar Baraskar, Agrim Dewan, and Chandan Saha

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
An n-variate polynomial g of degree d is a (n,d,t) design polynomial if the degree of the gcd of every pair of monomials of g is at most t-1. The power symmetric polynomial PSym_{n,d} : = ∑_{i = 1}ⁿ x^d_i and the sum-product polynomial SP_{s,d} : = ∑_{i = 1}^{s}∏_{j = 1}^{d} x_{i,j} are instances of design polynomials for t = 1. Another example is the Nisan-Wigderson design polynomial NW, which has been used extensively to prove various arithmetic circuit lower bounds. Given black-box access to an n-variate, degree-d polynomial f(𝐱) ∈ 𝔽[𝐱], how fast can we check if there exist an A ∈ GL(n, 𝔽) and a 𝐛 ∈ 𝔽ⁿ such that f(A𝐱+𝐛) is a (n,d,t) design polynomial? We call this problem "testing equivalence to design polynomials", or alternatively, "equivalence testing for design polynomials". In this work, we present a randomized algorithm that finds (A, 𝐛) such that f(A𝐱+𝐛) is a (n,d,t) design polynomial, if such A and 𝐛 exist, provided t ≤ d/3. The algorithm runs in (nd)^O(t) time and works over any sufficiently large 𝔽 of characteristic 0 or > d. As applications of this test, we show two results - one is structural and the other is algorithmic. The structural result establishes a polynomial-time equivalence between the graph isomorphism problem and the polynomial equivalence problem for design polynomials. The algorithmic result implies that Patarin’s scheme (EUROCRYPT 1996) can be broken in quasi-polynomial time if a random sparse polynomial is used in the key generation phase. We also give an efficient learning algorithm for n-variate random affine projections of multilinear degree-d design polynomials, provided n ≥ d⁴. If one obtains an analogous result under the weaker assumption "n ≥ d^ε, for any ε > 0", then the NW family is not VNP-complete unless there is a VNP-complete family whose random affine projections are learnable. It is not known if random affine projections of the permanent are learnable. The above algorithms are obtained by using the vector space decomposition framework, introduced by Kayal and Saha (STOC 2019) and Garg, Kayal and Saha (FOCS 2020), for learning non-degenerate arithmetic circuits. A key technical difference between the analysis in the papers by Garg, Kayal and Saha (FOCS 2020) and Bhargava, Garg, Kayal and Saha (RANDOM 2022) and the analysis here is that a certain adjoint algebra, which turned out to be trivial (i.e., diagonalizable) in prior works, is non-trivial in our case. However, we show that the adjoint arising here is triangularizable which then helps in carrying out the vector space decomposition step.
Cite as

Omkar Baraskar, Agrim Dewan, and Chandan Saha. Testing Equivalence to Design Polynomials. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 9:1-9:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{baraskar_et_al:LIPIcs.STACS.2024.9,
  author =	{Baraskar, Omkar and Dewan, Agrim and Saha, Chandan},
  title =	{{Testing Equivalence to Design Polynomials}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{9:1--9:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.9},
  URN =		{urn:nbn:de:0030-drops-197193},
  doi =		{10.4230/LIPIcs.STACS.2024.9},
  annote =	{Keywords: Polynomial equivalence, design polynomials, graph isomorphism, vector space decomposition}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.38
Improved Low-Depth Set-Multilinear Circuit Lower Bounds

Authors: Deepanshu Kush and Shubhangi Saraf

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

Abstract
In this paper, we prove strengthened lower bounds for constant-depth set-multilinear formulas. More precisely, we show that over any field, there is an explicit polynomial f in VNP defined over n² variables, and of degree n, such that any product-depth Δ set-multilinear formula computing f has size at least n^Ω(n^{1/Δ}/Δ). The hard polynomial f comes from the class of Nisan-Wigderson (NW) design-based polynomials. Our lower bounds improve upon the recent work of Limaye, Srinivasan and Tavenas (STOC 2022), where a lower bound of the form (log n)^Ω(Δ n^{1/Δ}) was shown for the size of product-depth Δ set-multilinear formulas computing the iterated matrix multiplication (IMM) polynomial of the same degree and over the same number of variables as f. Moreover, our lower bounds are novel for any Δ ≥ 2. The precise quantitative expression in our lower bound is interesting also because the lower bounds we obtain are "sharp" in the sense that any asymptotic improvement would imply general set-multilinear circuit lower bounds via depth reduction results. In the setting of general set-multilinear formulas, a lower bound of the form n^Ω(log n) was already obtained by Raz (J. ACM 2009) for the more general model of multilinear formulas. The techniques of LST (which extend the techniques of the same authors in (FOCS 2021)) give a different route to set-multilinear formula lower bounds, and allow them to obtain a lower bound of the form (log n)^Ω(log n) for the size of general set-multilinear formulas computing the IMM polynomial. Our proof techniques are another variation on those of LST, and enable us to show an improved lower bound (matching that of Raz) of the form n^Ω(log n), albeit for the same polynomial f in VNP (the NW polynomial). As observed by LST, if the same n^Ω(log n) size lower bounds for unbounded-depth set-multilinear formulas could be obtained for the IMM polynomial, then using the self-reducibility of IMM and using hardness escalation results, this would imply super-polynomial lower bounds for general algebraic formulas.
Cite as

Deepanshu Kush and Shubhangi Saraf. Improved Low-Depth Set-Multilinear Circuit Lower Bounds. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kush_et_al:LIPIcs.CCC.2022.38,
  author =	{Kush, Deepanshu and Saraf, Shubhangi},
  title =	{{Improved Low-Depth Set-Multilinear Circuit Lower Bounds}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{38:1--38:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.38},
  URN =		{urn:nbn:de:0030-drops-166003},
  doi =		{10.4230/LIPIcs.CCC.2022.38},
  annote =	{Keywords: algebraic circuit complexity, complexity measure, set-multilinear formulas}
}
Document
DOI: 10.4230/LIPIcs.CPM.2020.9
Dynamic String Alignment

Authors: Panagiotis Charalampopoulos, Tomasz Kociumaka, and Shay Mozes

Published in: LIPIcs, Volume 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)

Abstract
We consider the problem of dynamically maintaining an optimal alignment of two strings, each of length at most n, as they undergo insertions, deletions, and substitutions of letters. The string alignment problem generalizes the longest common subsequence (LCS) problem and the edit distance problem (also with non-unit costs, as long as insertions and deletions cost the same). The conditional lower bound of Backurs and Indyk [J. Comput. 2018] for computing the LCS in the static case implies that strongly sublinear update time for the dynamic string alignment problem would refute the Strong Exponential Time Hypothesis. We essentially match this lower bound when the alignment weights are constants, by showing how to process each update in 𝒪̃(n) time. When the weights are integers bounded in absolute value by some w=n^{𝒪(1)}, we can maintain the alignment in 𝒪̃(n ⋅ min {√ n,w}) time per update. For the 𝒪̃(nw)-time algorithm, we heavily rely on Tiskin’s work on semi-local LCS, and in particular, in an implicit way, on his algorithm for computing the (min,+)-product of two simple unit-Monge matrices [Algorithmica 2015]. As for the 𝒪̃(n√n)-time algorithm, we employ efficient data structures for computing distances in planar graphs.
Cite as

Panagiotis Charalampopoulos, Tomasz Kociumaka, and Shay Mozes. Dynamic String Alignment. In 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 161, pp. 9:1-9:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{charalampopoulos_et_al:LIPIcs.CPM.2020.9,
  author =	{Charalampopoulos, Panagiotis and Kociumaka, Tomasz and Mozes, Shay},
  title =	{{Dynamic String Alignment}},
  booktitle =	{31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)},
  pages =	{9:1--9:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-149-8},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{161},
  editor =	{G{\o}rtz, Inge Li and Weimann, Oren},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2020.9},
  URN =		{urn:nbn:de:0030-drops-121344},
  doi =		{10.4230/LIPIcs.CPM.2020.9},
  annote =	{Keywords: string alignment, edit distance, longest common subsequence, (unit-)Monge matrices, (min,+)-product}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2019.6
The Trickle-In Effect: Modeling Passenger Behavior in Delay Management

Authors: Anita Schöbel, Julius Pätzold, and Jörg P. Müller

Published in: OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)

Abstract
Delay management is concerned with making decisions if a train should wait for passengers from delayed trains or if it should depart on time. Models for delay management exist and can be adapted to capacities of stations, capacities of tracks, or respect vehicle and driver schedules, passengers' routes and further constraints. Nevertheless, what has been neglected so far, is that a train cannot depart as planned if passengers from another train trickle in one after another such that the doors of the departing train cannot close. This effect is often observed in real-world, but has not yet been taken into account in delay management. We show the impact of this "trickle-in" effect to departure delays of trains under different conditions. We then modify existing delay management models to take the trickle-in effect into account. This can be done by forbidding certain intervals for departure. We present an integer programming formulation with these additional constraints resulting in a generalization of classic delay management models. We analyze the resulting model and identify parameters with which it can be best approximated by the classical delay management problem. Experimentally, we show that the trickle-in effect has a high impact on the overall delay of public transport systems. We discuss the impact of the trickle-in effect on the objective function value and on the computation time of the delay management problem. We also analyze the trickle-in effect for timetables which have been derived without taking this particular behavioral pattern of passengers into account.
Cite as

Anita Schöbel, Julius Pätzold, and Jörg P. Müller. The Trickle-In Effect: Modeling Passenger Behavior in Delay Management. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{schobel_et_al:OASIcs.ATMOS.2019.6,
  author =	{Sch\"{o}bel, Anita and P\"{a}tzold, Julius and M\"{u}ller, J\"{o}rg P.},
  title =	{{The Trickle-In Effect: Modeling Passenger Behavior in Delay Management}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{6:1--6:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Cacchiani, Valentina and Marchetti-Spaccamela, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.6},
  URN =		{urn:nbn:de:0030-drops-114187},
  doi =		{10.4230/OASIcs.ATMOS.2019.6},
  annote =	{Keywords: Public Transport Planning, Delay Management, Integer Programming}
}
Document
DOI: 10.4230/DagRep.7.3.33
Using Networks to Teach About Networks (Dagstuhl Seminar 17112)

Authors: Timur Friedman, Aiko Pras, and Jürgen Schönwälder

Published in: Dagstuhl Reports, Volume 7, Issue 3 (2017)

Abstract
his report documents the program and the outcomes of Dagstuhl Seminar 17112 "Using Networks to Teach About Networks". The seminar brought together people with mixed backgrounds in order to exchange experiences gained with different approaches to teach computer networking. Despite the obvious question of what to teach, special attention was given to the questions of how to teach and which tools and infrastructures can be used effectively today for teaching purposes.
Cite as

Timur Friedman, Aiko Pras, and Jürgen Schönwälder. Using Networks to Teach About Networks (Dagstuhl Seminar 17112). In Dagstuhl Reports, Volume 7, Issue 3, pp. 33-44, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{friedman_et_al:DagRep.7.3.33,
  author =	{Friedman, Timur and Pras, Aiko and Sch\"{o}nw\"{a}lder, J\"{u}rgen},
  title =	{{Using Networks to Teach About Networks (Dagstuhl Seminar 17112)}},
  pages =	{33--44},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{3},
  editor =	{Friedman, Timur and Pras, Aiko and Sch\"{o}nw\"{a}lder, J\"{u}rgen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.7.3.33},
  URN =		{urn:nbn:de:0030-drops-73608},
  doi =		{10.4230/DagRep.7.3.33},
  annote =	{Keywords: computer networks, Internet, education, peer instruction, online learning, educational technologies}
}
Document
DOI: 10.4230/DagRep.6.1.15
Global Measurements: Practice and Experience (Dagstuhl Seminar 16012)

Authors: Vaibhav Bajpai, Arthur W. Berger, Philip Eardley, Jörg Ott, and Jürgen Schönwälder

Published in: Dagstuhl Reports, Volume 6, Issue 1 (2016)

Abstract
This article summarises a 2.5 day long Dagstuhl seminar on Global Measurements: Practice and Experience held in January 2016. This seminar was a followup of the seminar on Global Measurement Frameworks held in 2013, which focused on the development of global Internet measurement platforms and associated metrics. The second seminar aimed at discussing the practical experience gained with building these global Internet measurement platforms. It brought together people who are actively involved in the design and maintenance of global Internet measurement platforms and who do research on the data delivered by such platforms. Researchers in this seminar have used data derived from global Internet measurement platforms in order to manage networks or services or as input for regulatory decisions. The entire set of presentations delivered during the seminar is made publicly available at [1].
Cite as

Vaibhav Bajpai, Arthur W. Berger, Philip Eardley, Jörg Ott, and Jürgen Schönwälder. Global Measurements: Practice and Experience (Dagstuhl Seminar 16012). In Dagstuhl Reports, Volume 6, Issue 1, pp. 15-33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{bajpai_et_al:DagRep.6.1.15,
  author =	{Bajpai, Vaibhav and Berger, Arthur W. and Eardley, Philip and Ott, J\"{o}rg and Sch\"{o}nw\"{a}lder, J\"{u}rgen},
  title =	{{Global Measurements: Practice and Experience (Dagstuhl Seminar 16012)}},
  pages =	{15--33},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{1},
  editor =	{Bajpai, Vaibhav and Berger, Arthur W. and Eardley, Philip and Ott, J\"{o}rg and Sch\"{o}nw\"{a}lder, J\"{u}rgen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.6.1.15},
  URN =		{urn:nbn:de:0030-drops-58079},
  doi =		{10.4230/DagRep.6.1.15},
  annote =	{Keywords: Internet measurements, Quality of experience, Traffic engineering}
}
Document
DOI: 10.4230/DagRep.3.11.144
Global Measurement Framework (Dagstuhl Seminar 13472)

Authors: Philip Eardley, Marco Mellia, Jörg Ott, Jürgen Schönwälder, and Henning Schulzrinne

Published in: Dagstuhl Reports, Volume 3, Issue 11 (2014)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 13472 "Global Measurement Framework".
Cite as

Philip Eardley, Marco Mellia, Jörg Ott, Jürgen Schönwälder, and Henning Schulzrinne. Global Measurement Framework (Dagstuhl Seminar 13472). In Dagstuhl Reports, Volume 3, Issue 11, pp. 144-153, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{eardley_et_al:DagRep.3.11.144,
  author =	{Eardley, Philip and Mellia, Marco and Ott, J\"{o}rg and Sch\"{o}nw\"{a}lder, J\"{u}rgen and Schulzrinne, Henning},
  title =	{{Global Measurement Framework (Dagstuhl Seminar 13472)}},
  pages =	{144--153},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{3},
  number =	{11},
  editor =	{Eardley, Philip and Mellia, Marco and Ott, J\"{o}rg and Sch\"{o}nw\"{a}lder, J\"{u}rgen and Schulzrinne, Henning},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.3.11.144},
  URN =		{urn:nbn:de:0030-drops-44401},
  doi =		{10.4230/DagRep.3.11.144},
  annote =	{Keywords: Internet measurements, Quality of experience, Network management, Traffic engineering}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2013.475
On the Pseudoperiodic Extension of u^l = v^m w^n

Authors: Florin Manea, Mike Müller, and Dirk Nowotka

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

Abstract
We investigate the solution set of the pseudoperiodic extension of the classical Lyndon and Sch\"utzenberger word equations. Consider u_1 ... u_l = v_1 ... v_m w_1 ... w_n, where u_i is in {u, theta(u)} for all 1 <= i <= l, v_j is in {v, theta(v)} for all 1 <= j <= m, w_k is in {w, theta(w)} for all 1 <= k <= n and u, v and w are variables, and theta is an antimorphic involution. A solution is called pseudoperiodic, if u,v,w are in {t, theta(t)}^+ for a word t. [Czeizler et al./I&C/2011] established that for small values of l, m, and n non-periodic solutions exist, and that for large enough values all solutions are pseudoperiodic. However, they leave a gap between those bounds which we close for a number of cases. Namely, we show that for l = 3 and either m,n >= 12 or m,n >= 5 and either m and n are not both even or not all u_i's are equal, all solutions are pseudoperiodic.
Cite as

Florin Manea, Mike Müller, and Dirk Nowotka. On the Pseudoperiodic Extension of u^l = v^m w^n. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 475-486, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{manea_et_al:LIPIcs.FSTTCS.2013.475,
  author =	{Manea, Florin and M\"{u}ller, Mike and Nowotka, Dirk},
  title =	{{On the Pseudoperiodic Extension of u^l = v^m w^n}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{475--486},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Seth, Anil and Vishnoi, Nisheeth K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.475},
  URN =		{urn:nbn:de:0030-drops-43948},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.475},
  annote =	{Keywords: Word equations, Pseudoperiodicity, Lyndon-Sch\"{u}tzenberger equation}
}
Document
DOI: 10.4230/DagSemProc.09211.1
09211 Abstracts Collection – Visualization and Monitoring of Network Traffic

Authors: Daniel A. Keim, Aiko Pras, Jürgen Schönwälder, and Pak Chung Wong

Published in: Dagstuhl Seminar Proceedings, Volume 9211, Visualization and Monitoring of Network Traffic (2009)

Abstract
From 17.05. to 20.05.2009, the Dagstuhl Seminar 09211 ``Visualization and Monitoring of Network Traffic '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Daniel A. Keim, Aiko Pras, Jürgen Schönwälder, and Pak Chung Wong. 09211 Abstracts Collection – Visualization and Monitoring of Network Traffic. In Visualization and Monitoring of Network Traffic. Dagstuhl Seminar Proceedings, Volume 9211, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{keim_et_al:DagSemProc.09211.1,
  author =	{Keim, Daniel A. and Pras, Aiko and Sch\"{o}nw\"{a}lder, J\"{u}rgen and Wong, Pak Chung},
  title =	{{09211 Abstracts Collection – Visualization and Monitoring of Network Traffic }},
  booktitle =	{Visualization and Monitoring of Network Traffic},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9211},
  editor =	{Daniel A. Keim and Aiko Pras and J\"{u}rgen Sch\"{o}nw\"{a}lder and Pak Chung Wong},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09211.1},
  URN =		{urn:nbn:de:0030-drops-21586},
  doi =		{10.4230/DagSemProc.09211.1},
  annote =	{Keywords: Computer Networks, Internet, Monitoring of Networks and Services, Visualization Animation}
}
Document
DOI: 10.4230/DagSemProc.09211.2
09211 Executive Summary – Visualization and Monitoring of Network Traffic

Authors: Daniel A. Keim, Aiko Pras, Jürgen Schönwälder, Pak Chung Wong, and Florian Mansmann

Published in: Dagstuhl Seminar Proceedings, Volume 9211, Visualization and Monitoring of Network Traffic (2009)

Abstract
The seamless operation of the Internet requires being able to monitor and visualize the actual behaviour of the network. Today, IP network operators usually collect network flow statistics from critical points of their network infrastructure. Flows aggregate packets that share common properties. Flow records are stored and analyzed to extract accounting information and increasingly to identify and isolate network problems or security incidents. While network problems or attacks significantly changing traffic patterns are relatively easy to identify, it tends to be much more challenging to identify creeping changes or attacks and faults that manifest themselves only by very careful analysis of initially seemingly unrelated traffic pattern and their changes. There are currently no deployable good solutions and research in this area is just starting. In addition, the large volume of flow data on high capacity networks and exchange points requires to move to probabilistic sampling techniques, which require new analysis techniques to calculate and also visualize the uncertainty attached to data sets.
Cite as

Daniel A. Keim, Aiko Pras, Jürgen Schönwälder, Pak Chung Wong, and Florian Mansmann. 09211 Executive Summary – Visualization and Monitoring of Network Traffic. In Visualization and Monitoring of Network Traffic. Dagstuhl Seminar Proceedings, Volume 9211, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{keim_et_al:DagSemProc.09211.2,
  author =	{Keim, Daniel A. and Pras, Aiko and Sch\"{o}nw\"{a}lder, J\"{u}rgen and Wong, Pak Chung and Mansmann, Florian},
  title =	{{09211 Executive Summary – Visualization and Monitoring of Network Traffic}},
  booktitle =	{Visualization and Monitoring of Network Traffic},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9211},
  editor =	{Daniel A. Keim and Aiko Pras and J\"{u}rgen Sch\"{o}nw\"{a}lder and Pak Chung Wong},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09211.2},
  URN =		{urn:nbn:de:0030-drops-21574},
  doi =		{10.4230/DagSemProc.09211.2},
  annote =	{Keywords: Computer Networks, Internet, Monitoring of Networks and Services, Visualization Animation}
}
Document
DOI: 10.4230/DagSemProc.09211.3
Accounting system for heterogeneous IP-networks (IPNA) implemented at Kaiserslautern University

Authors: Brian Worden, Claudia Baltes, Inga Scheler, Paul Müller, and Hans Hagen

Published in: Dagstuhl Seminar Proceedings, Volume 9211, Visualization and Monitoring of Network Traffic (2009)

Abstract
This paper describes an accounting system (IPNA) for heterogenous IP-networks with arbitrary topologies implemented at the university of Kaiserslautern. The produced data volume per unit is numerated. The collected data is stored in a database and offers different analysis possibilities. The results can be visualized and adapted to the users requirements. The main effort was to build a data traffic quota system for single units as well as groups of devices that also report exceeded quotas. The system itself only observes the network traffic. Interfaces offer tools to interact with the network. The IPNA consists of a back-end for the data- acquisition and -preparation and a front-end for configuration and visualization tasks including quality control.
Cite as

Brian Worden, Claudia Baltes, Inga Scheler, Paul Müller, and Hans Hagen. Accounting system for heterogeneous IP-networks (IPNA) implemented at Kaiserslautern University. In Visualization and Monitoring of Network Traffic. Dagstuhl Seminar Proceedings, Volume 9211, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{worden_et_al:DagSemProc.09211.3,
  author =	{Worden, Brian and Baltes, Claudia and Scheler, Inga and M\"{u}ller, Paul and Hagen, Hans},
  title =	{{Accounting system for heterogeneous IP-networks (IPNA) implemented at Kaiserslautern University}},
  booktitle =	{Visualization and Monitoring of Network Traffic},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9211},
  editor =	{Daniel A. Keim and Aiko Pras and J\"{u}rgen Sch\"{o}nw\"{a}lder and Pak Chung Wong},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09211.3},
  URN =		{urn:nbn:de:0030-drops-21557},
  doi =		{10.4230/DagSemProc.09211.3},
  annote =	{Keywords: Accounting system, IP-network, Communication, informa- tion visualization, online quality control}
}
Document
DOI: 10.4230/DagSemProc.09211.4
Comparison of Node-Link and Hierarchical Edge Bundling Layouts: A User Study

Authors: Alexandru Telea, Ozan Ersoy, Hessel Hoogendorp, and Dennie Reniers

Published in: Dagstuhl Seminar Proceedings, Volume 9211, Visualization and Monitoring of Network Traffic (2009)

Abstract
Visually investigating large network-like structures is a challenging task. Several approaches have been proposed in the past: node-link diagrams, adjacency matrices, and, more recently, hierarchical edge bundles. We present a recent experiment that compares the effectiveness of the classical node-link diagrams with the more recent hierarchical bundled edges. The users involved several computer science practitioners, the data ranged from graphs of several hundreds to several tens of hundreds of nodes, the tasks involved answering a number of structural overview as well as detailed questions involved system dependencies.
Cite as

Alexandru Telea, Ozan Ersoy, Hessel Hoogendorp, and Dennie Reniers. Comparison of Node-Link and Hierarchical Edge Bundling Layouts: A User Study. In Visualization and Monitoring of Network Traffic. Dagstuhl Seminar Proceedings, Volume 9211, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{telea_et_al:DagSemProc.09211.4,
  author =	{Telea, Alexandru and Ersoy, Ozan and Hoogendorp, Hessel and Reniers, Dennie},
  title =	{{Comparison of Node-Link and Hierarchical Edge Bundling Layouts: A User Study}},
  booktitle =	{Visualization and Monitoring of Network Traffic},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9211},
  editor =	{Daniel A. Keim and Aiko Pras and J\"{u}rgen Sch\"{o}nw\"{a}lder and Pak Chung Wong},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09211.4},
  URN =		{urn:nbn:de:0030-drops-21542},
  doi =		{10.4230/DagSemProc.09211.4},
  annote =	{Keywords: Graph visualization, user studies, software visualization, call graphs}
}
Document
DOI: 10.4230/DagSemProc.09211.5
Interactive Exploration of the Network Behavior of Personal Machines

Authors: Mike Sips, Sascha Simon, and John Gerth

Published in: Dagstuhl Seminar Proceedings, Volume 9211, Visualization and Monitoring of Network Traffic (2009)

Abstract
Personal machines are often the weakest points within a large network. Although they run an ever-increasing number of network services, these machines are often controlled by users who are unaware of security threats. Thus, a well-informed attacker can, with modest effort, identify and gain control over personal machines. However, system administrators need to know the tools and techniques used for attacks while simultaneously needing to invest huge analytical efforts to detect malicious behavior in the vast volumes of network traffic. In our research project we investigate the idea that an understanding of the regular behavior of personal machines can improve the chance of detecting the point in time when a machine shows malicious behavior. We propose a visual exploration system based on a data abstraction layer and temporal visual representations of the network traffic. The data abstraction layer enables an interactive change in the level of detail of the network traffic while temporal visualizations help system administrators to detect unexpected network traffic. In the next phase of this project, we will conduct experiments to get a good feel about the limits of our system in detecting malicious behavior in real-world scenarios.
Cite as

Mike Sips, Sascha Simon, and John Gerth. Interactive Exploration of the Network Behavior of Personal Machines. In Visualization and Monitoring of Network Traffic. Dagstuhl Seminar Proceedings, Volume 9211, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{sips_et_al:DagSemProc.09211.5,
  author =	{Sips, Mike and Simon, Sascha and Gerth, John},
  title =	{{Interactive Exploration of the Network Behavior of Personal Machines}},
  booktitle =	{Visualization and Monitoring of Network Traffic},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9211},
  editor =	{Daniel A. Keim and Aiko Pras and J\"{u}rgen Sch\"{o}nw\"{a}lder and Pak Chung Wong},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09211.5},
  URN =		{urn:nbn:de:0030-drops-21565},
  doi =		{10.4230/DagSemProc.09211.5},
  annote =	{Keywords: Visualization, Communication Patterns, Data Abstraction, Personal Machines}
}
Document
DOI: 10.4230/DagSemProc.05402.1
Dagstuhl-Manifest zur Strategischen Bedeutung des Software Engineering in Deutschland

Authors: Manfred Broy, Matthias Jarke, Manfred Nagl, Hans Dieter Rombach, Armin B. Cremers, Jürgen Ebert, Sabine Glesner, Martin Glinz, Michael Goedicke, Gerhard Goos, Volker Gruhn, Wilhelm Hasselbring, Stefan Jähnichen, Stefan Kowalewski, Bernd J. Krämer, Stefan Leue, Claus Lewerentz, Peter Liggesmeyer, Christoph Lüth, Barbara Paech, Helmut A. Partsch, Ilka Philippow, Lutz Prechelt, Andreas Rausch, Willem-Paul de Roever, Bernhard Rumpe, Gudula Rünger, Wilhelm Schäfer, Kurt Schneider, Andy Schürr, Walter F. Tichy, Bernhard Westfechtel, Wolf Zimmermann, and Albert Zündorf

Published in: Dagstuhl Seminar Proceedings, Volume 5402, Perspectives Workshop (2006)

Abstract
Im Rahmen des Dagstuhl Perspektiven Workshop 05402 "Challenges for Software Engineering Research" haben führende Software Engineering Professoren den derzeitigen Stand der Softwaretechnik in Deutschland charakterisiert und Handlungsempfehlungen für Wirtschaft, Forschung und Politik abgeleitet. Das Manifest fasst die diese Empfehlungen und die Bedeutung und Entwicklung des Fachgebiets prägnant zusammen.
Cite as

Manfred Broy, Matthias Jarke, Manfred Nagl, Hans Dieter Rombach, Armin B. Cremers, Jürgen Ebert, Sabine Glesner, Martin Glinz, Michael Goedicke, Gerhard Goos, Volker Gruhn, Wilhelm Hasselbring, Stefan Jähnichen, Stefan Kowalewski, Bernd J. Krämer, Stefan Leue, Claus Lewerentz, Peter Liggesmeyer, Christoph Lüth, Barbara Paech, Helmut A. Partsch, Ilka Philippow, Lutz Prechelt, Andreas Rausch, Willem-Paul de Roever, Bernhard Rumpe, Gudula Rünger, Wilhelm Schäfer, Kurt Schneider, Andy Schürr, Walter F. Tichy, Bernhard Westfechtel, Wolf Zimmermann, and Albert Zündorf. Dagstuhl-Manifest zur Strategischen Bedeutung des Software Engineering in Deutschland. In Perspectives Workshop. Dagstuhl Seminar Proceedings, Volume 5402, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{broy_et_al:DagSemProc.05402.1,
  author =	{Broy, Manfred and Jarke, Matthias and Nagl, Manfred and Rombach, Hans Dieter and Cremers, Armin B. and Ebert, J\"{u}rgen and Glesner, Sabine and Glinz, Martin and Goedicke, Michael and Goos, Gerhard and Gruhn, Volker and Hasselbring, Wilhelm and J\"{a}hnichen, Stefan and Kowalewski, Stefan and Kr\"{a}mer, Bernd J. and Leue, Stefan and Lewerentz, Claus and Liggesmeyer, Peter and L\"{u}th, Christoph and Paech, Barbara and Partsch, Helmut A. and Philippow, Ilka and Prechelt, Lutz and Rausch, Andreas and de Roever, Willem-Paul and Rumpe, Bernhard and R\"{u}nger, Gudula and Sch\"{a}fer, Wilhelm and Schneider, Kurt and Sch\"{u}rr, Andy and Tichy, Walter F. and Westfechtel, Bernhard and Zimmermann, Wolf and Z\"{u}ndorf, Albert},
  title =	{{Dagstuhl-Manifest zur Strategischen Bedeutung des Software Engineering in Deutschland}},
  booktitle =	{Perspectives Workshop},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5402},
  editor =	{Manfred Broy and Manfred Nagl and Hans Dieter Rombach and Matthias Jarke},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05402.1},
  URN =		{urn:nbn:de:0030-drops-5853},
  doi =		{10.4230/DagSemProc.05402.1},
  annote =	{Keywords: Software Engineering, Software Technik, Strategie}
}
Document
DOI: 10.4230/DagSemProc.04461.16
On Continuation Methods for the Numerical Treatment of Multi-Objective Optimization Problems

Authors: Oliver Schütze, Alessandro Dell'Aere, and Michael Dellnitz

Published in: Dagstuhl Seminar Proceedings, Volume 4461, Practical Approaches to Multi-Objective Optimization (2005)

Abstract
In this report we describe how continuation methods can be used for the numerical treatment of multi-objective optimization problems (MOPs): starting with a given Karush-Kuhn-Tucker point (KKT-point) x of an MOP, these techniques can be applied to detect further KKT-points in the neighborhood of x. In the next step, again further points are computed starting with these new-found KKT-points, and so on. In order to maintain a good spread of these solutions we use boxes for the representation of the computed parts of the solution set. Based on this background, we propose a new predictor-corrector variant, and show some numerical results indicating the strength of the method, in particular in higher dimensions. Further, the data structure allows for an efficient computation of MOPs with more than two objectives, which has not been considered so far in most existing continuation methods.
Cite as

Oliver Schütze, Alessandro Dell'Aere, and Michael Dellnitz. On Continuation Methods for the Numerical Treatment of Multi-Objective Optimization Problems. In Practical Approaches to Multi-Objective Optimization. Dagstuhl Seminar Proceedings, Volume 4461, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{schutze_et_al:DagSemProc.04461.16,
  author =	{Sch\"{u}tze, Oliver and Dell'Aere, Alessandro and Dellnitz, Michael},
  title =	{{On Continuation Methods for the Numerical Treatment of Multi-Objective Optimization Problems}},
  booktitle =	{Practical Approaches to Multi-Objective Optimization},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4461},
  editor =	{J\"{u}rgen Branke and Kalyanmoy Deb and Kaisa Miettinen and Ralph E. Steuer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04461.16},
  URN =		{urn:nbn:de:0030-drops-3497},
  doi =		{10.4230/DagSemProc.04461.16},
  annote =	{Keywords: multi-objective optimization, continuation, k-manifolds}
}
  • Refine by Author
  • 5 Schönwälder, Jürgen
  • 3 Pras, Aiko
  • 2 Eardley, Philip
  • 2 Keim, Daniel A.
  • 2 Ott, Jörg
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Algebraic complexity theory
  • 1 Applied computing → Transportation
  • 1 Theory of computation → Pattern matching

  • Refine by Keyword
  • 3 Internet
  • 2 Computer Networks
  • 2 Internet measurements
  • 2 Monitoring of Networks and Services
  • 2 Quality of experience
  • Show More...

  • Refine by Type
  • 15 document

  • Refine by Publication Year
  • 5 2009
  • 1 2005
  • 1 2006
  • 1 2013
  • 1 2014
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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