---
_id: '3298'
abstract:
- lang: eng
text: We present a new algorithm for enforcing incompressibility for Smoothed Particle
Hydrodynamics (SPH) by preserving uniform density across the domain. We propose
a hybrid method that uses a Poisson solve on a coarse grid to enforce a divergence
free velocity field, followed by a local density correction of the particles. This
avoids typical grid artifacts and maintains the Lagrangian nature of SPH by directly
transferring pressures onto particles. Our method can be easily integrated with
existing SPH techniques such as the incompressible PCISPH method as well as weakly
compressible SPH by adding an additional force term. We show that this hybrid
method accelerates convergence towards uniform density and permits a significantly
larger time step compared to earlier approaches while producing similar results.
We demonstrate our approach in a variety of scenarios with significant pressure
gradients such as splashing liquids.
author:
- first_name: Karthik
full_name: Raveendran, Karthik
last_name: Raveendran
- first_name: Christopher J
full_name: Wojtan, Christopher J
id: 3C61F1D2-F248-11E8-B48F-1D18A9856A87
last_name: Wojtan
orcid: 0000-0001-6646-5546
- first_name: Greg
full_name: Turk, Greg
last_name: Turk
citation:
ama: 'Raveendran K, Wojtan C, Turk G. Hybrid smoothed particle hydrodynamics. In:
Spencer S, ed. ACM; 2011:33-42. doi:10.1145/2019406.2019411'
apa: 'Raveendran, K., Wojtan, C., & Turk, G. (2011). Hybrid smoothed particle
hydrodynamics. In S. Spencer (Ed.) (pp. 33–42). Presented at the SCA: ACM SIGGRAPH/Eurographics
Symposium on Computer animation, Vancouver, Canada: ACM. https://doi.org/10.1145/2019406.2019411'
chicago: Raveendran, Karthik, Chris Wojtan, and Greg Turk. “Hybrid Smoothed Particle
Hydrodynamics.” edited by Stephen Spencer, 33–42. ACM, 2011. https://doi.org/10.1145/2019406.2019411.
ieee: 'K. Raveendran, C. Wojtan, and G. Turk, “Hybrid smoothed particle hydrodynamics,”
presented at the SCA: ACM SIGGRAPH/Eurographics Symposium on Computer animation,
Vancouver, Canada, 2011, pp. 33–42.'
ista: 'Raveendran K, Wojtan C, Turk G. 2011. Hybrid smoothed particle hydrodynamics.
SCA: ACM SIGGRAPH/Eurographics Symposium on Computer animation, 33–42.'
mla: Raveendran, Karthik, et al. Hybrid Smoothed Particle Hydrodynamics.
Edited by Stephen Spencer, ACM, 2011, pp. 33–42, doi:10.1145/2019406.2019411.
short: K. Raveendran, C. Wojtan, G. Turk, in:, S. Spencer (Ed.), ACM, 2011, pp.
33–42.
conference:
end_date: 2011-08-07
location: Vancouver, Canada
name: 'SCA: ACM SIGGRAPH/Eurographics Symposium on Computer animation'
start_date: 2011-08-05
date_created: 2018-12-11T12:02:32Z
date_published: 2011-08-05T00:00:00Z
date_updated: 2023-02-23T11:21:05Z
day: '05'
ddc:
- '000'
department:
- _id: ChWo
doi: 10.1145/2019406.2019411
editor:
- first_name: Stephen
full_name: Spencer, Stephen
last_name: Spencer
file:
- access_level: open_access
checksum: 6579d27709946e0eefbfa60a456b4913
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:09:44Z
date_updated: 2020-07-14T12:46:06Z
file_id: '4769'
file_name: IST-2016-598-v1+1_HybridSPH_Preprint.pdf
file_size: 2536216
relation: main_file
file_date_updated: 2020-07-14T12:46:06Z
has_accepted_license: '1'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Submitted Version
page: 33 - 42
publication_status: published
publisher: ACM
publist_id: '3343'
pubrep_id: '598'
quality_controlled: '1'
scopus_import: 1
status: public
title: Hybrid smoothed particle hydrodynamics
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3299'
abstract:
- lang: eng
text: 'We introduce propagation models, a formalism designed to support general
and efficient data structures for the transient analysis of biochemical reaction
networks. We give two use cases for propagation abstract data types: the uniformization
method and numerical integration. We also sketch an implementation of a propagation
abstract data type, which uses abstraction to approximate states.'
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Maria
full_name: Mateescu, Maria
last_name: Mateescu
citation:
ama: 'Henzinger TA, Mateescu M. Propagation models for computing biochemical reaction
networks. In: Springer; 2011:1-3. doi:10.1145/2037509.2037510'
apa: 'Henzinger, T. A., & Mateescu, M. (2011). Propagation models for computing
biochemical reaction networks (pp. 1–3). Presented at the CMSB: Computational
Methods in Systems Biology, Paris, France: Springer. https://doi.org/10.1145/2037509.2037510'
chicago: Henzinger, Thomas A, and Maria Mateescu. “Propagation Models for Computing
Biochemical Reaction Networks,” 1–3. Springer, 2011. https://doi.org/10.1145/2037509.2037510.
ieee: 'T. A. Henzinger and M. Mateescu, “Propagation models for computing biochemical
reaction networks,” presented at the CMSB: Computational Methods in Systems Biology,
Paris, France, 2011, pp. 1–3.'
ista: 'Henzinger TA, Mateescu M. 2011. Propagation models for computing biochemical
reaction networks. CMSB: Computational Methods in Systems Biology, 1–3.'
mla: Henzinger, Thomas A., and Maria Mateescu. Propagation Models for Computing
Biochemical Reaction Networks. Springer, 2011, pp. 1–3, doi:10.1145/2037509.2037510.
short: T.A. Henzinger, M. Mateescu, in:, Springer, 2011, pp. 1–3.
conference:
end_date: 2011-09-23
location: Paris, France
name: 'CMSB: Computational Methods in Systems Biology'
start_date: 2011-09-21
date_created: 2018-12-11T12:02:32Z
date_published: 2011-09-21T00:00:00Z
date_updated: 2021-01-12T07:42:29Z
day: '21'
ddc:
- '000'
- '004'
department:
- _id: ToHe
doi: 10.1145/2037509.2037510
file:
- access_level: open_access
checksum: 7f5c65509db1a9fb049abedd9663ed06
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:07:50Z
date_updated: 2020-07-14T12:46:06Z
file_id: '4649'
file_name: IST-2012-92-v1+1_Propagation_models_for_computing_biochemical_reaction_networks.pdf
file_size: 255780
relation: main_file
file_date_updated: 2020-07-14T12:46:06Z
has_accepted_license: '1'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Submitted Version
page: 1 - 3
publication_status: published
publisher: Springer
publist_id: '3341'
pubrep_id: '92'
quality_controlled: '1'
scopus_import: 1
status: public
title: Propagation models for computing biochemical reaction networks
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3301'
abstract:
- lang: eng
text: The chemical master equation is a differential equation describing the time
evolution of the probability distribution over the possible “states” of a biochemical
system. The solution of this equation is of interest within the systems biology
field ever since the importance of the molec- ular noise has been acknowledged.
Unfortunately, most of the systems do not have analytical solutions, and numerical
solutions suffer from the course of dimensionality and therefore need to be approximated.
Here, we introduce the concept of tail approximation, which retrieves an approximation
of the probabilities in the tail of a distribution from the total probability
of the tail and its conditional expectation. This approximation method can then
be used to numerically compute the solution of the chemical master equation on
a subset of the state space, thus fighting the explosion of the state space, for
which this problem is renowned.
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Maria
full_name: Mateescu, Maria
last_name: Mateescu
citation:
ama: 'Henzinger TA, Mateescu M. Tail approximation for the chemical master equation.
In: Tampere International Center for Signal Processing; 2011.'
apa: 'Henzinger, T. A., & Mateescu, M. (2011). Tail approximation for the chemical
master equation. Presented at the WCSB: Workshop on Computational Systems Biology
(TICSP), Tampere International Center for Signal Processing.'
chicago: Henzinger, Thomas A, and Maria Mateescu. “Tail Approximation for the Chemical
Master Equation.” Tampere International Center for Signal Processing, 2011.
ieee: 'T. A. Henzinger and M. Mateescu, “Tail approximation for the chemical master
equation,” presented at the WCSB: Workshop on Computational Systems Biology (TICSP),
2011.'
ista: 'Henzinger TA, Mateescu M. 2011. Tail approximation for the chemical master
equation. WCSB: Workshop on Computational Systems Biology (TICSP).'
mla: Henzinger, Thomas A., and Maria Mateescu. Tail Approximation for the Chemical
Master Equation. Tampere International Center for Signal Processing, 2011.
short: T.A. Henzinger, M. Mateescu, in:, Tampere International Center for Signal
Processing, 2011.
conference:
name: 'WCSB: Workshop on Computational Systems Biology (TICSP)'
date_created: 2018-12-11T12:02:33Z
date_published: 2011-01-01T00:00:00Z
date_updated: 2021-01-12T07:42:30Z
day: '01'
ddc:
- '005'
- '570'
department:
- _id: ToHe
file:
- access_level: open_access
checksum: aa4d7a832a5419e6c0090650ebff2b9a
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:18:12Z
date_updated: 2020-07-14T12:46:06Z
file_id: '5331'
file_name: IST-2012-91-v1+1_Tail_approximation_for_the_chemical_master_equation.pdf
file_size: 240820
relation: main_file
file_date_updated: 2020-07-14T12:46:06Z
has_accepted_license: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
publication_status: published
publisher: Tampere International Center for Signal Processing
publist_id: '3339'
pubrep_id: '91'
quality_controlled: '1'
status: public
title: Tail approximation for the chemical master equation
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3302'
abstract:
- lang: eng
text: Cloud computing aims to give users virtually unlimited pay-per-use computing
resources without the burden of managing the underlying infrastructure. We present
a new job execution environment Flextic that exploits scal- able static scheduling
techniques to provide the user with a flexible pricing model, such as a tradeoff
between dif- ferent degrees of execution speed and execution price, and at the
same time, reduce scheduling overhead for the cloud provider. We have evaluated
a prototype of Flextic on Amazon EC2 and compared it against Hadoop. For various
data parallel jobs from machine learning, im- age processing, and gene sequencing
that we considered, Flextic has low scheduling overhead and reduces job du- ration
by up to 15% compared to Hadoop, a dynamic cloud scheduler.
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Anmol
full_name: Singh, Anmol
id: 72A86902-E99F-11E9-9F62-915534D1B916
last_name: Singh
- first_name: Vasu
full_name: Singh, Vasu
id: 4DAE2708-F248-11E8-B48F-1D18A9856A87
last_name: Singh
- first_name: Thomas
full_name: Wies, Thomas
id: 447BFB88-F248-11E8-B48F-1D18A9856A87
last_name: Wies
- first_name: Damien
full_name: Zufferey, Damien
id: 4397AC76-F248-11E8-B48F-1D18A9856A87
last_name: Zufferey
orcid: 0000-0002-3197-8736
citation:
ama: 'Henzinger TA, Singh A, Singh V, Wies T, Zufferey D. Static scheduling in clouds.
In: USENIX; 2011:1-6.'
apa: 'Henzinger, T. A., Singh, A., Singh, V., Wies, T., & Zufferey, D. (2011).
Static scheduling in clouds (pp. 1–6). Presented at the HotCloud: Workshop on
Hot Topics in Cloud Computing, USENIX.'
chicago: Henzinger, Thomas A, Anmol Singh, Vasu Singh, Thomas Wies, and Damien Zufferey.
“Static Scheduling in Clouds,” 1–6. USENIX, 2011.
ieee: 'T. A. Henzinger, A. Singh, V. Singh, T. Wies, and D. Zufferey, “Static scheduling
in clouds,” presented at the HotCloud: Workshop on Hot Topics in Cloud Computing,
2011, pp. 1–6.'
ista: 'Henzinger TA, Singh A, Singh V, Wies T, Zufferey D. 2011. Static scheduling
in clouds. HotCloud: Workshop on Hot Topics in Cloud Computing, 1–6.'
mla: Henzinger, Thomas A., et al. Static Scheduling in Clouds. USENIX, 2011,
pp. 1–6.
short: T.A. Henzinger, A. Singh, V. Singh, T. Wies, D. Zufferey, in:, USENIX, 2011,
pp. 1–6.
conference:
end_date: 2011-06-15
name: 'HotCloud: Workshop on Hot Topics in Cloud Computing'
start_date: 2011-06-14
date_created: 2018-12-11T12:02:33Z
date_published: 2011-06-14T00:00:00Z
date_updated: 2021-01-12T07:42:31Z
day: '14'
ddc:
- '000'
- '005'
department:
- _id: ToHe
file:
- access_level: open_access
checksum: 21a461ac004bb535c83320fe79b30375
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:18:14Z
date_updated: 2020-07-14T12:46:06Z
file_id: '5333'
file_name: IST-2012-90-v1+1_Static_scheduling_in_clouds.pdf
file_size: 232770
relation: main_file
file_date_updated: 2020-07-14T12:46:06Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Submitted Version
page: 1 - 6
publication_status: published
publisher: USENIX
publist_id: '3338'
pubrep_id: '90'
quality_controlled: '1'
status: public
title: Static scheduling in clouds
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3311'
abstract:
- lang: eng
text: Alpha shapes have been conceived in 1981 as an attempt to define the shape
of a finite set of point in the plane. Since then, connections to diverse areas
in the sciences and engineering have developed, including to pattern recognition,
digital shape sampling and processing, and structural molecular biology. This
survey begins with a historical account and discusses geometric, algorithmic,
topological, and combinatorial aspects of alpha shapes in this sequence.
article_processing_charge: No
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: 'Edelsbrunner H. Alpha shapes - a survey. In: van de Weygaert R, Vegter G,
Ritzerveld J, Icke V, eds. Tessellations in the Sciences: Virtues, Techniques
and Applications of Geometric Tilings. Springer.'
apa: 'Edelsbrunner, H. (n.d.). Alpha shapes - a survey. In R. van de Weygaert, G.
Vegter, J. Ritzerveld, & V. Icke (Eds.), Tessellations in the Sciences:
Virtues, Techniques and Applications of Geometric Tilings. Springer.'
chicago: 'Edelsbrunner, Herbert. “Alpha Shapes - a Survey.” In Tessellations
in the Sciences: Virtues, Techniques and Applications of Geometric Tilings,
edited by R van de Weygaert, G Vegter, J Ritzerveld, and V Icke. Springer, n.d.'
ieee: 'H. Edelsbrunner, “Alpha shapes - a survey,” in Tessellations in the Sciences:
Virtues, Techniques and Applications of Geometric Tilings, R. van de Weygaert,
G. Vegter, J. Ritzerveld, and V. Icke, Eds. Springer.'
ista: 'Edelsbrunner H.Alpha shapes - a survey. In: Tessellations in the Sciences:
Virtues, Techniques and Applications of Geometric Tilings. .'
mla: 'Edelsbrunner, Herbert. “Alpha Shapes - a Survey.” Tessellations in the
Sciences: Virtues, Techniques and Applications of Geometric Tilings, edited
by R van de Weygaert et al., Springer.'
short: 'H. Edelsbrunner, in:, R. van de Weygaert, G. Vegter, J. Ritzerveld, V. Icke
(Eds.), Tessellations in the Sciences: Virtues, Techniques and Applications of
Geometric Tilings, Springer, n.d.'
date_created: 2018-12-11T12:02:36Z
date_published: 2011-12-31T00:00:00Z
date_updated: 2022-05-24T07:56:30Z
day: '31'
ddc:
- '510'
department:
- _id: HeEd
editor:
- first_name: R
full_name: van de Weygaert, R
last_name: van de Weygaert
- first_name: G
full_name: Vegter, G
last_name: Vegter
- first_name: J
full_name: Ritzerveld, J
last_name: Ritzerveld
- first_name: V
full_name: Icke, V
last_name: Icke
file:
- access_level: open_access
checksum: a592ea438351e7280eea993a7713ab8f
content_type: application/pdf
creator: dernst
date_created: 2022-05-24T07:55:05Z
date_updated: 2022-05-24T07:55:05Z
file_id: '11408'
file_name: 2010_AlphaShapes.pdf
file_size: 475254
relation: main_file
success: 1
file_date_updated: 2022-05-24T07:55:05Z
has_accepted_license: '1'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Submitted Version
publication: 'Tessellations in the Sciences: Virtues, Techniques and Applications
of Geometric Tilings'
publication_status: inpress
publisher: Springer
publist_id: '3329'
quality_controlled: '1'
status: public
title: Alpha shapes - a survey
type: book_chapter
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3312'
abstract:
- lang: eng
text: We study the 3D reconstruction of plant roots from multiple 2D images. To
meet the challenge caused by the delicate nature of thin branches, we make three
innovations to cope with the sensitivity to image quality and calibration. First,
we model the background as a harmonic function to improve the segmentation of
the root in each 2D image. Second, we develop the concept of the regularized visual
hull which reduces the effect of jittering and refraction by ensuring consistency
with one 2D image. Third, we guarantee connectedness through adjustments to the
3D reconstruction that minimize global error. Our software is part of a biological
phenotype/genotype study of agricultural root systems. It has been tested on more
than 40 plant roots and results are promising in terms of reconstruction quality
and efficiency.
acknowledgement: This research is supported by the National Science Foundation (NSF)
under grant DBI-0820624.
article_number: '6126475'
article_processing_charge: No
author:
- first_name: Ying
full_name: Zheng, Ying
last_name: Zheng
- first_name: Steve
full_name: Gu, Steve
last_name: Gu
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Carlo
full_name: Tomasi, Carlo
last_name: Tomasi
- first_name: Philip
full_name: Benfey, Philip
last_name: Benfey
citation:
ama: Zheng Y, Gu S, Edelsbrunner H, Tomasi C, Benfey P. Detailed Reconstruction
of 3D Plant Root Shape. IEEE; 2011. doi:10.1109/ICCV.2011.6126475
apa: 'Zheng, Y., Gu, S., Edelsbrunner, H., Tomasi, C., & Benfey, P. (2011).
Detailed reconstruction of 3D plant root shape. Proceedings of the IEEE
International Conference on Computer Vision. Barcelona, Spain: IEEE. https://doi.org/10.1109/ICCV.2011.6126475'
chicago: Zheng, Ying, Steve Gu, Herbert Edelsbrunner, Carlo Tomasi, and Philip Benfey.
Detailed Reconstruction of 3D Plant Root Shape. Proceedings of the IEEE
International Conference on Computer Vision. IEEE, 2011. https://doi.org/10.1109/ICCV.2011.6126475.
ieee: Y. Zheng, S. Gu, H. Edelsbrunner, C. Tomasi, and P. Benfey, Detailed reconstruction
of 3D plant root shape. IEEE, 2011.
ista: Zheng Y, Gu S, Edelsbrunner H, Tomasi C, Benfey P. 2011. Detailed reconstruction
of 3D plant root shape, IEEE,p.
mla: Zheng, Ying, et al. “Detailed Reconstruction of 3D Plant Root Shape.” Proceedings
of the IEEE International Conference on Computer Vision, 6126475, IEEE, 2011,
doi:10.1109/ICCV.2011.6126475.
short: Y. Zheng, S. Gu, H. Edelsbrunner, C. Tomasi, P. Benfey, Detailed Reconstruction
of 3D Plant Root Shape, IEEE, 2011.
conference:
end_date: 2011-11-13
location: Barcelona, Spain
name: 'ICCV: International Conference on Computer Vision'
start_date: 2011-11-06
date_created: 2018-12-11T12:02:36Z
date_published: 2011-12-31T00:00:00Z
date_updated: 2020-07-14T23:03:43Z
day: '31'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1109/ICCV.2011.6126475
file:
- access_level: open_access
checksum: 30a33564b7b45a7ee31610898267fd0e
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:09:04Z
date_updated: 2020-07-14T12:46:07Z
file_id: '4727'
file_name: IST-2016-541-v1+1_2011-P-07-RootReconstruction.pdf
file_size: 5622728
relation: main_file
file_date_updated: 2020-07-14T12:46:07Z
has_accepted_license: '1'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Submitted Version
publication: Proceedings of the IEEE International Conference on Computer Vision
publication_status: published
publisher: IEEE
publist_id: '3328'
pubrep_id: '541'
quality_controlled: '1'
status: public
title: Detailed reconstruction of 3D plant root shape
type: conference_poster
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3313'
abstract:
- lang: eng
text: Interpreting an image as a function on a compact sub- set of the Euclidean
plane, we get its scale-space by diffu- sion, spreading the image over the entire
plane. This gener- ates a 1-parameter family of functions alternatively defined
as convolutions with a progressively wider Gaussian ker- nel. We prove that the
corresponding 1-parameter family of persistence diagrams have norms that go rapidly
to zero as time goes to infinity. This result rationalizes experimental observations
about scale-space. We hope this will lead to targeted improvements of related
computer vision methods.
article_number: '6126271'
author:
- first_name: Chao
full_name: Chen, Chao
id: 3E92416E-F248-11E8-B48F-1D18A9856A87
last_name: Chen
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: 'Chen C, Edelsbrunner H. Diffusion runs low on persistence fast. In: Proceedings
of the IEEE International Conference on Computer Vision. IEEE; 2011. doi:10.1109/ICCV.2011.6126271'
apa: 'Chen, C., & Edelsbrunner, H. (2011). Diffusion runs low on persistence
fast. In Proceedings of the IEEE International Conference on Computer Vision.
Barcelona, Spain: IEEE. https://doi.org/10.1109/ICCV.2011.6126271'
chicago: Chen, Chao, and Herbert Edelsbrunner. “Diffusion Runs Low on Persistence
Fast.” In Proceedings of the IEEE International Conference on Computer Vision.
IEEE, 2011. https://doi.org/10.1109/ICCV.2011.6126271.
ieee: C. Chen and H. Edelsbrunner, “Diffusion runs low on persistence fast,” in
Proceedings of the IEEE International Conference on Computer Vision, Barcelona,
Spain, 2011.
ista: 'Chen C, Edelsbrunner H. 2011. Diffusion runs low on persistence fast. Proceedings
of the IEEE International Conference on Computer Vision. ICCV: International Conference
on Computer Vision, 6126271.'
mla: Chen, Chao, and Herbert Edelsbrunner. “Diffusion Runs Low on Persistence Fast.”
Proceedings of the IEEE International Conference on Computer Vision, 6126271,
IEEE, 2011, doi:10.1109/ICCV.2011.6126271.
short: C. Chen, H. Edelsbrunner, in:, Proceedings of the IEEE International Conference
on Computer Vision, IEEE, 2011.
conference:
end_date: 2011-11-13
location: Barcelona, Spain
name: 'ICCV: International Conference on Computer Vision'
start_date: 2011-11-06
date_created: 2018-12-11T12:02:37Z
date_published: 2011-11-06T00:00:00Z
date_updated: 2021-01-12T07:42:35Z
day: '06'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1109/ICCV.2011.6126271
file:
- access_level: open_access
checksum: 6984684081ba123808b344f9f2e64a8f
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:17:28Z
date_updated: 2020-07-14T12:46:07Z
file_id: '5282'
file_name: IST-2016-540-v1+1_2011-P-08-RunEmpty.pdf
file_size: 614050
relation: main_file
file_date_updated: 2020-07-14T12:46:07Z
has_accepted_license: '1'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Submitted Version
publication: Proceedings of the IEEE International Conference on Computer Vision
publication_status: published
publisher: IEEE
publist_id: '3327'
pubrep_id: '540'
quality_controlled: '1'
scopus_import: 1
status: public
title: Diffusion runs low on persistence fast
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3315'
abstract:
- lang: eng
text: We consider two-player games played in real time on game structures with clocks
where the objectives of players are described using parity conditions. The games
are concurrent in that at each turn, both players independently propose a time
delay and an action, and the action with the shorter delay is chosen. To prevent
a player from winning by blocking time, we restrict each player to play strategies
that ensure that the player cannot be responsible for causing a zeno run. First,
we present an efficient reduction of these games to turn-based (i.e., not concurrent)
finite-state (i.e., untimed) parity games. Our reduction improves the best known
complexity for solving timed parity games. Moreover, the rich class of algorithms
for classical parity games can now be applied to timed parity games. The states
of the resulting game are based on clock regions of the original game, and the
state space of the finite game is linear in the size of the region graph. Second,
we consider two restricted classes of strategies for the player that represents
the controller in a real-time synthesis problem, namely, limit-robust and bounded-robust
winning strategies. Using a limit-robust winning strategy, the controller cannot
choose an exact real-valued time delay but must allow for some nonzero jitter
in each of its actions. If there is a given lower bound on the jitter, then the
strategy is bounded-robust winning. We show that exact strategies are more powerful
than limit-robust strategies, which are more powerful than bounded-robust winning
strategies for any bound. For both kinds of robust strategies, we present efficient
reductions to standard timed automaton games. These reductions provide algorithms
for the synthesis of robust real-time controllers.
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Vinayak
full_name: Prabhu, Vinayak
last_name: Prabhu
citation:
ama: 'Chatterjee K, Henzinger TA, Prabhu V. Timed parity games: Complexity and robustness.
Logical Methods in Computer Science. 2011;7(4). doi:10.2168/LMCS-7(4:8)2011'
apa: 'Chatterjee, K., Henzinger, T. A., & Prabhu, V. (2011). Timed parity games:
Complexity and robustness. Logical Methods in Computer Science. International
Federation of Computational Logic. https://doi.org/10.2168/LMCS-7(4:8)2011'
chicago: 'Chatterjee, Krishnendu, Thomas A Henzinger, and Vinayak Prabhu. “Timed
Parity Games: Complexity and Robustness.” Logical Methods in Computer Science.
International Federation of Computational Logic, 2011. https://doi.org/10.2168/LMCS-7(4:8)2011.'
ieee: 'K. Chatterjee, T. A. Henzinger, and V. Prabhu, “Timed parity games: Complexity
and robustness,” Logical Methods in Computer Science, vol. 7, no. 4. International
Federation of Computational Logic, 2011.'
ista: 'Chatterjee K, Henzinger TA, Prabhu V. 2011. Timed parity games: Complexity
and robustness. Logical Methods in Computer Science. 7(4).'
mla: 'Chatterjee, Krishnendu, et al. “Timed Parity Games: Complexity and Robustness.”
Logical Methods in Computer Science, vol. 7, no. 4, International Federation
of Computational Logic, 2011, doi:10.2168/LMCS-7(4:8)2011.'
short: K. Chatterjee, T.A. Henzinger, V. Prabhu, Logical Methods in Computer Science
7 (2011).
date_created: 2018-12-11T12:02:37Z
date_published: 2011-12-14T00:00:00Z
date_updated: 2023-02-23T11:46:35Z
day: '14'
ddc:
- '000'
- '005'
department:
- _id: KrCh
- _id: ToHe
doi: 10.2168/LMCS-7(4:8)2011
ec_funded: 1
file:
- access_level: open_access
checksum: 3480e1594bbef25ff7462fa93a8a814e
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:16:42Z
date_updated: 2020-07-14T12:46:07Z
file_id: '5231'
file_name: IST-2016-86-v2+1_1011.0688_3_.pdf
file_size: 588863
relation: main_file
file_date_updated: 2020-07-14T12:46:07Z
has_accepted_license: '1'
intvolume: ' 7'
issue: '4'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nd/4.0/
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: 25EFB36C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '215543'
name: COMponent-Based Embedded Systems design Techniques
publication: Logical Methods in Computer Science
publication_status: published
publisher: International Federation of Computational Logic
publist_id: '3324'
pubrep_id: '506'
quality_controlled: '1'
related_material:
record:
- id: '3876'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: 'Timed parity games: Complexity and robustness'
tmp:
image: /image/cc_by_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nd/4.0/legalcode
name: Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)
short: CC BY-ND (4.0)
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 7
year: '2011'
...
---
_id: '3316'
abstract:
- lang: eng
text: In addition to being correct, a system should be robust, that is, it should
behave reasonably even after receiving unexpected inputs. In this paper, we summarize
two formal notions of robustness that we have introduced previously for reactive
systems. One of the notions is based on assigning costs for failures on a user-provided
notion of incorrect transitions in a specification. Here, we define a system to
be robust if a finite number of incorrect inputs does not lead to an infinite
number of incorrect outputs. We also give a more refined notion of robustness
that aims to minimize the ratio of output failures to input failures. The second
notion is aimed at liveness. In contrast to the previous notion, it has no concept
of recovery from an error. Instead, it compares the ratio of the number of liveness
constraints that the system violates to the number of liveness constraints that
the environment violates.
article_processing_charge: No
author:
- first_name: Roderick
full_name: Bloem, Roderick
last_name: Bloem
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Karin
full_name: Greimel, Karin
last_name: Greimel
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Barbara
full_name: Jobstmann, Barbara
last_name: Jobstmann
citation:
ama: 'Bloem R, Chatterjee K, Greimel K, Henzinger TA, Jobstmann B. Specification-centered
robustness. In: 6th IEEE International Symposium on Industrial and Embedded
Systems. IEEE; 2011:176-185. doi:10.1109/SIES.2011.5953660'
apa: 'Bloem, R., Chatterjee, K., Greimel, K., Henzinger, T. A., & Jobstmann,
B. (2011). Specification-centered robustness. In 6th IEEE International Symposium
on Industrial and Embedded Systems (pp. 176–185). Vasteras, Sweden: IEEE.
https://doi.org/10.1109/SIES.2011.5953660'
chicago: Bloem, Roderick, Krishnendu Chatterjee, Karin Greimel, Thomas A Henzinger,
and Barbara Jobstmann. “Specification-Centered Robustness.” In 6th IEEE International
Symposium on Industrial and Embedded Systems, 176–85. IEEE, 2011. https://doi.org/10.1109/SIES.2011.5953660.
ieee: R. Bloem, K. Chatterjee, K. Greimel, T. A. Henzinger, and B. Jobstmann, “Specification-centered
robustness,” in 6th IEEE International Symposium on Industrial and Embedded
Systems, Vasteras, Sweden, 2011, pp. 176–185.
ista: 'Bloem R, Chatterjee K, Greimel K, Henzinger TA, Jobstmann B. 2011. Specification-centered
robustness. 6th IEEE International Symposium on Industrial and Embedded Systems. SIES:
International Symposium on Industrial Embedded Systems, 176–185.'
mla: Bloem, Roderick, et al. “Specification-Centered Robustness.” 6th IEEE International
Symposium on Industrial and Embedded Systems, IEEE, 2011, pp. 176–85, doi:10.1109/SIES.2011.5953660.
short: R. Bloem, K. Chatterjee, K. Greimel, T.A. Henzinger, B. Jobstmann, in:, 6th
IEEE International Symposium on Industrial and Embedded Systems, IEEE, 2011, pp.
176–185.
conference:
end_date: 2011-06-17
location: Vasteras, Sweden
name: ' SIES: International Symposium on Industrial Embedded Systems'
start_date: 2011-06-15
date_created: 2018-12-11T12:02:38Z
date_published: 2011-07-14T00:00:00Z
date_updated: 2021-01-12T07:42:36Z
day: '14'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1109/SIES.2011.5953660
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://openlib.tugraz.at/download.php?id=5cb57c8a49344&location=browse
month: '07'
oa: 1
oa_version: Published Version
page: 176 - 185
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25F2ACDE-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Rigorous Systems Engineering
- _id: 25F1337C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '214373'
name: Design for Embedded Systems
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: 6th IEEE International Symposium on Industrial and Embedded Systems
publication_status: published
publisher: IEEE
publist_id: '3323'
quality_controlled: '1'
scopus_import: 1
status: public
title: Specification-centered robustness
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3318'
abstract:
- lang: eng
text: Parvalbumin is thought to act in a manner similar to EGTA, but how a slow
Ca2+ buffer affects nanodomain-coupling regimes at GABAergic synapses is unclear.
Direct measurements of parvalbumin concentration and paired recordings in rodent
hippocampus and cerebellum revealed that parvalbumin affects synaptic dynamics
only when expressed at high levels. Modeling suggests that, in high concentrations,
parvalbumin may exert BAPTA-like effects, modulating nanodomain coupling via competition
with local saturation of endogenous fixed buffers.
author:
- first_name: Emmanuel
full_name: Eggermann, Emmanuel
last_name: Eggermann
- first_name: Peter M
full_name: Jonas, Peter M
id: 353C1B58-F248-11E8-B48F-1D18A9856A87
last_name: Jonas
orcid: 0000-0001-5001-4804
citation:
ama: Eggermann E, Jonas PM. How the “slow” Ca(2+) buffer parvalbumin affects transmitter
release in nanodomain coupling regimes at GABAergic synapses. Nature Neuroscience.
2011;15:20-22. doi:10.1038/nn.3002
apa: Eggermann, E., & Jonas, P. M. (2011). How the “slow” Ca(2+) buffer parvalbumin
affects transmitter release in nanodomain coupling regimes at GABAergic synapses.
Nature Neuroscience. Nature Publishing Group. https://doi.org/10.1038/nn.3002
chicago: Eggermann, Emmanuel, and Peter M Jonas. “How the ‘Slow’ Ca(2+) Buffer Parvalbumin
Affects Transmitter Release in Nanodomain Coupling Regimes at GABAergic Synapses.”
Nature Neuroscience. Nature Publishing Group, 2011. https://doi.org/10.1038/nn.3002.
ieee: E. Eggermann and P. M. Jonas, “How the ‘slow’ Ca(2+) buffer parvalbumin affects
transmitter release in nanodomain coupling regimes at GABAergic synapses,” Nature
Neuroscience, vol. 15. Nature Publishing Group, pp. 20–22, 2011.
ista: Eggermann E, Jonas PM. 2011. How the “slow” Ca(2+) buffer parvalbumin affects
transmitter release in nanodomain coupling regimes at GABAergic synapses. Nature
Neuroscience. 15, 20–22.
mla: Eggermann, Emmanuel, and Peter M. Jonas. “How the ‘Slow’ Ca(2+) Buffer Parvalbumin
Affects Transmitter Release in Nanodomain Coupling Regimes at GABAergic Synapses.”
Nature Neuroscience, vol. 15, Nature Publishing Group, 2011, pp. 20–22,
doi:10.1038/nn.3002.
short: E. Eggermann, P.M. Jonas, Nature Neuroscience 15 (2011) 20–22.
date_created: 2018-12-11T12:02:38Z
date_published: 2011-12-04T00:00:00Z
date_updated: 2021-01-12T07:42:37Z
day: '04'
department:
- _id: PeJo
doi: 10.1038/nn.3002
intvolume: ' 15'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3631701/
month: '12'
oa: 1
oa_version: Submitted Version
page: 20 - 22
publication: Nature Neuroscience
publication_status: published
publisher: Nature Publishing Group
publist_id: '3321'
quality_controlled: '1'
scopus_import: 1
status: public
title: How the “slow” Ca(2+) buffer parvalbumin affects transmitter release in nanodomain
coupling regimes at GABAergic synapses
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 15
year: '2011'
...
---
_id: '3319'
abstract:
- lang: eng
text: We address the problem of metric learning for multi-view data, namely the
construction of embedding projections from data in different representations into
a shared feature space, such that the Euclidean distance in this space provides
a meaningful within-view as well as between-view similarity. Our motivation stems
from the problem of cross-media retrieval tasks, where the availability of a joint
Euclidean distance function is a pre-requisite to allow fast, in particular hashing-based,
nearest neighbor queries. We formulate an objective function that expresses the
intuitive concept that matching samples are mapped closely together in the output
space, whereas non-matching samples are pushed apart, no matter in which view
they are available. The resulting optimization problem is not convex, but it can
be decomposed explicitly into a convex and a concave part, thereby allowing efficient
optimization using the convex-concave procedure. Experiments on an image retrieval
task show that nearest-neighbor based cross-view retrieval is indeed possible,
and the proposed technique improves the retrieval accuracy over baseline techniques.
article_processing_charge: No
author:
- first_name: Novi
full_name: Quadrianto, Novi
last_name: Quadrianto
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
citation:
ama: 'Quadrianto N, Lampert C. Learning multi-view neighborhood preserving projections.
In: ML Research Press; 2011:425-432.'
apa: 'Quadrianto, N., & Lampert, C. (2011). Learning multi-view neighborhood
preserving projections (pp. 425–432). Presented at the ICML: International Conference
on Machine Learning, Bellevue, United States: ML Research Press.'
chicago: Quadrianto, Novi, and Christoph Lampert. “Learning Multi-View Neighborhood
Preserving Projections,” 425–32. ML Research Press, 2011.
ieee: 'N. Quadrianto and C. Lampert, “Learning multi-view neighborhood preserving
projections,” presented at the ICML: International Conference on Machine Learning,
Bellevue, United States, 2011, pp. 425–432.'
ista: 'Quadrianto N, Lampert C. 2011. Learning multi-view neighborhood preserving
projections. ICML: International Conference on Machine Learning, 425–432.'
mla: Quadrianto, Novi, and Christoph Lampert. Learning Multi-View Neighborhood
Preserving Projections. ML Research Press, 2011, pp. 425–32.
short: N. Quadrianto, C. Lampert, in:, ML Research Press, 2011, pp. 425–432.
conference:
end_date: 2011-07-02
location: Bellevue, United States
name: 'ICML: International Conference on Machine Learning'
start_date: 2011-06-28
date_created: 2018-12-11T12:02:39Z
date_published: 2011-01-01T00:00:00Z
date_updated: 2023-10-17T11:59:50Z
day: '01'
department:
- _id: ChLa
language:
- iso: eng
month: '01'
oa_version: None
page: 425 - 432
publication_status: published
publisher: ML Research Press
publist_id: '3316'
scopus_import: '1'
status: public
title: Learning multi-view neighborhood preserving projections
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3320'
abstract:
- lang: eng
text: Powerful statistical models that can be learned efficiently from large amounts
of data are currently revolutionizing computer vision. These models possess a
rich internal structure reflecting task-specific relations and constraints. This
monograph introduces the reader to the most popular classes of structured models
in computer vision. Our focus is discrete undirected graphical models which we
cover in detail together with a description of algorithms for both probabilistic
inference and maximum a posteriori inference. We discuss separately recently successful
techniques for prediction in general structured models. In the second part of
this monograph we describe methods for parameter learning where we distinguish
the classic maximum likelihood based methods from the more recent prediction-based
parameter learning methods. We highlight developments to enhance current models
and discuss kernelized models and latent variable models. To make the monograph
more practical and to provide links to further study we provide examples of successful
application of many methods in the computer vision literature.
article_processing_charge: No
article_type: original
author:
- first_name: Sebastian
full_name: Nowozin, Sebastian
last_name: Nowozin
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
citation:
ama: Nowozin S, Lampert C. Structured learning and prediction in computer vision.
Foundations and Trends in Computer Graphics and Vision. 2011;6(3-4):185-365.
doi:10.1561/0600000033
apa: Nowozin, S., & Lampert, C. (2011). Structured learning and prediction in
computer vision. Foundations and Trends in Computer Graphics and Vision.
Now Publishers. https://doi.org/10.1561/0600000033
chicago: Nowozin, Sebastian, and Christoph Lampert. “Structured Learning and Prediction
in Computer Vision.” Foundations and Trends in Computer Graphics and Vision.
Now Publishers, 2011. https://doi.org/10.1561/0600000033.
ieee: S. Nowozin and C. Lampert, “Structured learning and prediction in computer
vision,” Foundations and Trends in Computer Graphics and Vision, vol. 6,
no. 3–4. Now Publishers, pp. 185–365, 2011.
ista: Nowozin S, Lampert C. 2011. Structured learning and prediction in computer
vision. Foundations and Trends in Computer Graphics and Vision. 6(3–4), 185–365.
mla: Nowozin, Sebastian, and Christoph Lampert. “Structured Learning and Prediction
in Computer Vision.” Foundations and Trends in Computer Graphics and Vision,
vol. 6, no. 3–4, Now Publishers, 2011, pp. 185–365, doi:10.1561/0600000033.
short: S. Nowozin, C. Lampert, Foundations and Trends in Computer Graphics and Vision
6 (2011) 185–365.
date_created: 2018-12-11T12:02:39Z
date_published: 2011-05-23T00:00:00Z
date_updated: 2023-10-17T11:52:46Z
day: '23'
ddc:
- '000'
department:
- _id: ChLa
doi: 10.1561/0600000033
file:
- access_level: open_access
checksum: f1043ef389f1558e2a226bb51568511f
content_type: application/pdf
creator: dernst
date_created: 2020-05-14T14:34:47Z
date_updated: 2020-07-14T12:46:07Z
file_id: '7837'
file_name: 2011_CompGraphicsVision_Nowozin.pdf
file_size: 3745064
relation: main_file
file_date_updated: 2020-07-14T12:46:07Z
has_accepted_license: '1'
intvolume: ' 6'
issue: 3-4
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
page: 185 - 365
publication: Foundations and Trends in Computer Graphics and Vision
publication_status: published
publisher: Now Publishers
publist_id: '3315'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Structured learning and prediction in computer vision
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 6
year: '2011'
...
---
_id: '3322'
abstract:
- lang: eng
text: We study multi-label prediction for structured output spaces, a problem that
occurs, for example, in object detection in images, secondary structure prediction
in computational biology, and graph matching with symmetries. Conventional multi-label
classification techniques are typically not applicable in this situation, because
they require explicit enumeration of the label space, which is infeasible in case
of structured outputs. Relying on techniques originally designed for single- label
structured prediction, in particular structured support vector machines, results
in reduced prediction accuracy, or leads to infeasible optimization problems.
In this work we derive a maximum-margin training formulation for multi-label structured
prediction that remains computationally tractable while achieving high prediction
accuracy. It also shares most beneficial properties with single-label maximum-margin
approaches, in particular a formulation as a convex optimization problem, efficient
working set training, and PAC-Bayesian generalization bounds.
article_processing_charge: No
author:
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
citation:
ama: Lampert C. Maximum Margin Multi Label Structured Prediction. Neural
Information Processing Systems Foundation; 2011.
apa: 'Lampert, C. (2011). Maximum margin multi label structured prediction.
NIPS: Neural Information Processing Systems. Neural Information Processing
Systems Foundation.'
chicago: 'Lampert, Christoph. Maximum Margin Multi Label Structured Prediction.
NIPS: Neural Information Processing Systems. Neural Information Processing
Systems Foundation, 2011.'
ieee: C. Lampert, Maximum margin multi label structured prediction. Neural
Information Processing Systems Foundation, 2011.
ista: Lampert C. 2011. Maximum margin multi label structured prediction, Neural
Information Processing Systems Foundation,p.
mla: 'Lampert, Christoph. “Maximum Margin Multi Label Structured Prediction.” NIPS:
Neural Information Processing Systems, Neural Information Processing Systems
Foundation, 2011.'
short: C. Lampert, Maximum Margin Multi Label Structured Prediction, Neural Information
Processing Systems Foundation, 2011.
date_created: 2018-12-11T12:02:40Z
date_published: 2011-12-13T00:00:00Z
date_updated: 2023-10-17T11:47:36Z
day: '13'
department:
- _id: ChLa
language:
- iso: eng
month: '12'
oa_version: None
publication: 'NIPS: Neural Information Processing Systems'
publication_status: published
publisher: Neural Information Processing Systems Foundation
publist_id: '3313'
related_material:
record:
- id: '3163'
relation: earlier_version
status: public
status: public
title: Maximum margin multi label structured prediction
type: conference_poster
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3323'
abstract:
- lang: eng
text: We present a new decidable logic called TREX for expressing constraints about
imperative tree data structures. In particular, TREX supports a transitive closure
operator that can express reachability constraints, which often appear in data
structure invariants. We show that our logic is closed under weakest precondition
computation, which enables its use for automated software verification. We further
show that satisfiability of formulas in TREX is decidable in NP. The low complexity
makes it an attractive alternative to more expensive logics such as monadic second-order
logic (MSOL) over trees, which have been traditionally used for reasoning about
tree data structures.
alternative_title:
- 'LNAI '
author:
- first_name: Thomas
full_name: Wies, Thomas
id: 447BFB88-F248-11E8-B48F-1D18A9856A87
last_name: Wies
- first_name: Marco
full_name: Muñiz, Marco
last_name: Muñiz
- first_name: Viktor
full_name: Kuncak, Viktor
last_name: Kuncak
citation:
ama: 'Wies T, Muñiz M, Kuncak V. An efficient decision procedure for imperative
tree data structures. In: Vol 6803. Springer; 2011:476-491. doi:10.1007/978-3-642-22438-6_36'
apa: 'Wies, T., Muñiz, M., & Kuncak, V. (2011). An efficient decision procedure
for imperative tree data structures (Vol. 6803, pp. 476–491). Presented at the
CADE 23: Automated Deduction , Wrocław, Poland: Springer. https://doi.org/10.1007/978-3-642-22438-6_36'
chicago: Wies, Thomas, Marco Muñiz, and Viktor Kuncak. “An Efficient Decision Procedure
for Imperative Tree Data Structures,” 6803:476–91. Springer, 2011. https://doi.org/10.1007/978-3-642-22438-6_36.
ieee: 'T. Wies, M. Muñiz, and V. Kuncak, “An efficient decision procedure for imperative
tree data structures,” presented at the CADE 23: Automated Deduction , Wrocław,
Poland, 2011, vol. 6803, pp. 476–491.'
ista: 'Wies T, Muñiz M, Kuncak V. 2011. An efficient decision procedure for imperative
tree data structures. CADE 23: Automated Deduction , LNAI , vol. 6803, 476–491.'
mla: Wies, Thomas, et al. An Efficient Decision Procedure for Imperative Tree
Data Structures. Vol. 6803, Springer, 2011, pp. 476–91, doi:10.1007/978-3-642-22438-6_36.
short: T. Wies, M. Muñiz, V. Kuncak, in:, Springer, 2011, pp. 476–491.
conference:
end_date: 2011-08-05
location: Wrocław, Poland
name: 'CADE 23: Automated Deduction '
start_date: 2011-07-31
date_created: 2018-12-11T12:02:40Z
date_published: 2011-07-19T00:00:00Z
date_updated: 2023-02-23T12:23:48Z
day: '19'
department:
- _id: ToHe
doi: 10.1007/978-3-642-22438-6_36
intvolume: ' 6803'
language:
- iso: eng
month: '07'
oa_version: None
page: 476 - 491
publication_status: published
publisher: Springer
publist_id: '3312'
quality_controlled: '1'
related_material:
record:
- id: '5383'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: An efficient decision procedure for imperative tree data structures
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6803
year: '2011'
...
---
_id: '3324'
abstract:
- lang: eng
text: 'Automated termination provers often use the following schema to prove that
a program terminates: construct a relational abstraction of the program''s transition
relation and then show that the relational abstraction is well-founded. The focus
of current tools has been on developing sophisticated techniques for constructing
the abstractions while relying on known decidable logics (such as linear arithmetic)
to express them. We believe we can significantly increase the class of programs
that are amenable to automated termination proofs by identifying more expressive
decidable logics for reasoning about well-founded relations. We therefore present
a new decision procedure for reasoning about multiset orderings, which are among
the most powerful orderings used to prove termination. We show that, using our
decision procedure, one can automatically prove termination of natural abstractions
of programs.'
alternative_title:
- LNCS
author:
- first_name: Ruzica
full_name: Piskac, Ruzica
last_name: Piskac
- first_name: Thomas
full_name: Wies, Thomas
id: 447BFB88-F248-11E8-B48F-1D18A9856A87
last_name: Wies
citation:
ama: 'Piskac R, Wies T. Decision procedures for automating termination proofs. In:
Jhala R, Schmidt D, eds. Vol 6538. Springer; 2011:371-386. doi:10.1007/978-3-642-18275-4_26'
apa: 'Piskac, R., & Wies, T. (2011). Decision procedures for automating termination
proofs. In R. Jhala & D. Schmidt (Eds.) (Vol. 6538, pp. 371–386). Presented
at the VMCAI: Verification Model Checking and Abstract Interpretation, Texas,
USA: Springer. https://doi.org/10.1007/978-3-642-18275-4_26'
chicago: Piskac, Ruzica, and Thomas Wies. “Decision Procedures for Automating Termination
Proofs.” edited by Ranjit Jhala and David Schmidt, 6538:371–86. Springer, 2011.
https://doi.org/10.1007/978-3-642-18275-4_26.
ieee: 'R. Piskac and T. Wies, “Decision procedures for automating termination proofs,”
presented at the VMCAI: Verification Model Checking and Abstract Interpretation,
Texas, USA, 2011, vol. 6538, pp. 371–386.'
ista: 'Piskac R, Wies T. 2011. Decision procedures for automating termination proofs.
VMCAI: Verification Model Checking and Abstract Interpretation, LNCS, vol. 6538,
371–386.'
mla: Piskac, Ruzica, and Thomas Wies. Decision Procedures for Automating Termination
Proofs. Edited by Ranjit Jhala and David Schmidt, vol. 6538, Springer, 2011,
pp. 371–86, doi:10.1007/978-3-642-18275-4_26.
short: R. Piskac, T. Wies, in:, R. Jhala, D. Schmidt (Eds.), Springer, 2011, pp.
371–386.
conference:
end_date: 2011-01-25
location: Texas, USA
name: 'VMCAI: Verification Model Checking and Abstract Interpretation'
start_date: 2011-01-23
date_created: 2018-12-11T12:02:40Z
date_published: 2011-01-01T00:00:00Z
date_updated: 2021-01-12T07:42:39Z
day: '01'
department:
- _id: ToHe
doi: 10.1007/978-3-642-18275-4_26
editor:
- first_name: Ranjit
full_name: Jhala, Ranjit
last_name: Jhala
- first_name: David
full_name: Schmidt, David
last_name: Schmidt
intvolume: ' 6538'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://infoscience.epfl.ch/record/170697/
month: '01'
oa: 1
oa_version: Submitted Version
page: 371 - 386
publication_status: published
publisher: Springer
publist_id: '3311'
quality_controlled: '1'
scopus_import: 1
status: public
title: Decision procedures for automating termination proofs
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6538
year: '2011'
...
---
_id: '3325'
abstract:
- lang: eng
text: We introduce streaming data string transducers that map input data strings
to output data strings in a single left-to-right pass in linear time. Data strings
are (unbounded) sequences of data values, tagged with symbols from a finite set,
over a potentially infinite data do- main that supports only the operations of
equality and ordering. The transducer uses a finite set of states, a finite set
of variables ranging over the data domain, and a finite set of variables ranging
over data strings. At every step, it can make decisions based on the next in-
put symbol, updating its state, remembering the input data value in its data variables,
and updating data-string variables by concatenat- ing data-string variables and
new symbols formed from data vari- ables, while avoiding duplication. We establish
that the problems of checking functional equivalence of two streaming transducers,
and of checking whether a streaming transducer satisfies pre/post verification
conditions specified by streaming acceptors over in- put/output data-strings,
are in PSPACE. We identify a class of imperative and a class of functional pro-
grams, manipulating lists of data items, which can be effectively translated to
streaming data-string transducers. The imperative pro- grams dynamically modify
a singly-linked heap by changing next- pointers of heap-nodes and by adding new
nodes. The main re- striction specifies how the next-pointers can be used for
traversal. We also identify an expressively equivalent fragment of functional
programs that traverse a list using syntactically restricted recursive calls.
Our results lead to algorithms for assertion checking and for checking functional
equivalence of two programs, written possibly in different programming styles,
for commonly used routines such as insert, delete, and reverse.
article_processing_charge: No
author:
- first_name: Rajeev
full_name: Alur, Rajeev
last_name: Alur
- first_name: Pavol
full_name: Cerny, Pavol
id: 4DCBEFFE-F248-11E8-B48F-1D18A9856A87
last_name: Cerny
citation:
ama: 'Alur R, Cerny P. Streaming transducers for algorithmic verification of single
pass list processing programs. In: Vol 46. ACM; 2011:599-610. doi:10.1145/1926385.1926454'
apa: 'Alur, R., & Cerny, P. (2011). Streaming transducers for algorithmic verification
of single pass list processing programs (Vol. 46, pp. 599–610). Presented at the
POPL: Principles of Programming Languages, Texas, USA: ACM. https://doi.org/10.1145/1926385.1926454'
chicago: Alur, Rajeev, and Pavol Cerny. “Streaming Transducers for Algorithmic Verification
of Single Pass List Processing Programs,” 46:599–610. ACM, 2011. https://doi.org/10.1145/1926385.1926454.
ieee: 'R. Alur and P. Cerny, “Streaming transducers for algorithmic verification
of single pass list processing programs,” presented at the POPL: Principles of
Programming Languages, Texas, USA, 2011, vol. 46, no. 1, pp. 599–610.'
ista: 'Alur R, Cerny P. 2011. Streaming transducers for algorithmic verification
of single pass list processing programs. POPL: Principles of Programming Languages
vol. 46, 599–610.'
mla: Alur, Rajeev, and Pavol Cerny. Streaming Transducers for Algorithmic Verification
of Single Pass List Processing Programs. Vol. 46, no. 1, ACM, 2011, pp. 599–610,
doi:10.1145/1926385.1926454.
short: R. Alur, P. Cerny, in:, ACM, 2011, pp. 599–610.
conference:
end_date: 2011-01-28
location: Texas, USA
name: 'POPL: Principles of Programming Languages'
start_date: 2011-01-26
date_created: 2018-12-11T12:02:41Z
date_published: 2011-01-26T00:00:00Z
date_updated: 2022-03-21T08:12:51Z
day: '26'
department:
- _id: ToHe
doi: 10.1145/1926385.1926454
intvolume: ' 46'
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 599 - 610
publication_status: published
publisher: ACM
publist_id: '3310'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Streaming transducers for algorithmic verification of single pass list processing
programs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 46
year: '2011'
...
---
_id: '3326'
abstract:
- lang: eng
text: 'Weighted automata map input words to numerical values. Ap- plications of
weighted automata include formal verification of quantitative properties, as well
as text, speech, and image processing. A weighted au- tomaton is defined with
respect to a semiring. For the tropical semiring, the weight of a run is the sum
of the weights of the transitions taken along the run, and the value of a word
is the minimal weight of an accepting run on it. In the 90’s, Krob studied the
decidability of problems on rational series defined with respect to the tropical
semiring. Rational series are strongly related to weighted automata, and Krob’s
results apply to them. In par- ticular, it follows from Krob’s results that the
universality problem (that is, deciding whether the values of all words are below
some threshold) is decidable for weighted automata defined with respect to the
tropical semir- ing with domain ∪ {∞}, and that the equality problem is undecidable
when the domain is ∪ {∞}. In this paper we continue the study of the borders of
decidability in weighted automata, describe alternative and direct proofs of the
above results, and tighten them further. Unlike the proofs of Krob, which are
algebraic in their nature, our proofs stay in the terrain of state machines, and
the reduction is from the halting problem of a two-counter machine. This enables
us to significantly simplify Krob’s reasoning, make the un- decidability result
accessible to the automata-theoretic community, and strengthen it to apply already
to a very simple class of automata: all the states are accepting, there are no
initial nor final weights, and all the weights on the transitions are from the
set {−1, 0, 1}. The fact we work directly with the automata enables us to tighten
also the decidability re- sults and to show that the universality problem for
weighted automata defined with respect to the tropical semiring with domain ∪
{∞}, and in fact even with domain ≥0 ∪ {∞}, is PSPACE-complete. Our results thus
draw a sharper picture about the decidability of decision problems for weighted
automata, in both the front of containment vs. universality and the front of the
∪ {∞} vs. the ∪ {∞} domains.'
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Shaull
full_name: Almagor, Shaull
last_name: Almagor
- first_name: Udi
full_name: Boker, Udi
id: 31E297B6-F248-11E8-B48F-1D18A9856A87
last_name: Boker
- first_name: Orna
full_name: Kupferman, Orna
last_name: Kupferman
citation:
ama: 'Almagor S, Boker U, Kupferman O. What’s decidable about weighted automata
. In: Vol 6996. Springer; 2011:482-491. doi:10.1007/978-3-642-24372-1_37'
apa: 'Almagor, S., Boker, U., & Kupferman, O. (2011). What’s decidable about
weighted automata (Vol. 6996, pp. 482–491). Presented at the ATVA: Automated
Technology for Verification and Analysis, Taipei, Taiwan: Springer. https://doi.org/10.1007/978-3-642-24372-1_37'
chicago: Almagor, Shaull, Udi Boker, and Orna Kupferman. “What’s Decidable about
Weighted Automata ,” 6996:482–91. Springer, 2011. https://doi.org/10.1007/978-3-642-24372-1_37.
ieee: 'S. Almagor, U. Boker, and O. Kupferman, “What’s decidable about weighted
automata ,” presented at the ATVA: Automated Technology for Verification and Analysis,
Taipei, Taiwan, 2011, vol. 6996, pp. 482–491.'
ista: 'Almagor S, Boker U, Kupferman O. 2011. What’s decidable about weighted automata
. ATVA: Automated Technology for Verification and Analysis, LNCS, vol. 6996, 482–491.'
mla: Almagor, Shaull, et al. What’s Decidable about Weighted Automata . Vol.
6996, Springer, 2011, pp. 482–91, doi:10.1007/978-3-642-24372-1_37.
short: S. Almagor, U. Boker, O. Kupferman, in:, Springer, 2011, pp. 482–491.
conference:
end_date: 2011-10-14
location: Taipei, Taiwan
name: 'ATVA: Automated Technology for Verification and Analysis'
start_date: 2011-10-11
date_created: 2018-12-11T12:02:41Z
date_published: 2011-10-14T00:00:00Z
date_updated: 2021-01-12T07:42:40Z
day: '14'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-642-24372-1_37
file:
- access_level: open_access
checksum: a7ca08a2cb1b6925f4c18a3034ae5659
content_type: application/pdf
creator: dernst
date_created: 2020-05-19T16:08:32Z
date_updated: 2020-07-14T12:46:07Z
file_id: '7868'
file_name: 2011_LNCS_Almagor.pdf
file_size: 182309
relation: main_file
file_date_updated: 2020-07-14T12:46:07Z
has_accepted_license: '1'
intvolume: ' 6996'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
page: 482 - 491
publication_status: published
publisher: Springer
publist_id: '3309'
quality_controlled: '1'
status: public
title: 'What’s decidable about weighted automata '
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 6996
year: '2011'
...
---
_id: '3328'
abstract:
- lang: eng
text: 'We report on a generic uni- and bivariate algebraic kernel that is publicly
available with CGAL 3.7. It comprises complete, correct, though efficient state-of-the-art
implementations on polynomials, roots of polynomial systems, and the support to
analyze algebraic curves defined by bivariate polynomials. The kernel design is
generic, that is, various number types and substeps can be exchanged. It is accompanied
with a ready-to-use interface to enable arrangements induced by algebraic curves,
that have already been used as basis for various geometric applications, as arrangements
on Dupin cyclides or the triangulation of algebraic surfaces. We present two novel
applications: arrangements of rotated algebraic curves and Boolean set operations
on polygons bounded by segments of algebraic curves. We also provide experiments
showing that our general implementation is competitive and even often clearly
outperforms existing implementations that are explicitly tailored for specific
types of non-linear curves that are available in CGAL.'
article_processing_charge: No
author:
- first_name: Eric
full_name: Berberich, Eric
last_name: Berberich
- first_name: Michael
full_name: Hemmer, Michael
last_name: Hemmer
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
citation:
ama: 'Berberich E, Hemmer M, Kerber M. A generic algebraic kernel for non linear
geometric applications. In: ACM; 2011:179-186. doi:10.1145/1998196.1998224'
apa: 'Berberich, E., Hemmer, M., & Kerber, M. (2011). A generic algebraic kernel
for non linear geometric applications (pp. 179–186). Presented at the SCG: Symposium
on Computational Geometry, Paris, France: ACM. https://doi.org/10.1145/1998196.1998224'
chicago: Berberich, Eric, Michael Hemmer, and Michael Kerber. “A Generic Algebraic
Kernel for Non Linear Geometric Applications,” 179–86. ACM, 2011. https://doi.org/10.1145/1998196.1998224.
ieee: 'E. Berberich, M. Hemmer, and M. Kerber, “A generic algebraic kernel for non
linear geometric applications,” presented at the SCG: Symposium on Computational
Geometry, Paris, France, 2011, pp. 179–186.'
ista: 'Berberich E, Hemmer M, Kerber M. 2011. A generic algebraic kernel for non
linear geometric applications. SCG: Symposium on Computational Geometry, 179–186.'
mla: Berberich, Eric, et al. A Generic Algebraic Kernel for Non Linear Geometric
Applications. ACM, 2011, pp. 179–86, doi:10.1145/1998196.1998224.
short: E. Berberich, M. Hemmer, M. Kerber, in:, ACM, 2011, pp. 179–186.
conference:
end_date: 2011-06-15
location: Paris, France
name: 'SCG: Symposium on Computational Geometry'
start_date: 2011-06-13
date_created: 2018-12-11T12:02:42Z
date_published: 2011-06-13T00:00:00Z
date_updated: 2021-01-12T07:42:41Z
day: '13'
department:
- _id: HeEd
doi: 10.1145/1998196.1998224
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://hal.inria.fr/inria-00480031/file/RR-7274.pdf
month: '06'
oa: 1
oa_version: Published Version
page: 179 - 186
publication_status: published
publisher: ACM
publist_id: '3307'
quality_controlled: '1'
scopus_import: 1
status: public
title: A generic algebraic kernel for non linear geometric applications
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3329'
abstract:
- lang: eng
text: 'We consider the offset-deconstruction problem: Given a polygonal shape Q
with n vertices, can it be expressed, up to a tolerance µ in Hausdorff distance,
as the Minkowski sum of another polygonal shape P with a disk of fixed radius?
If it does, we also seek a preferably simple-looking solution shape P; then, P''s
offset constitutes an accurate, vertex-reduced, and smoothened approximation of
Q. We give an O(n log n)-time exact decision algorithm that handles any polygonal
shape, assuming the real-RAM model of computation. An alternative algorithm, based
purely on rational arithmetic, answers the same deconstruction problem, up to
an uncertainty parameter, and its running time depends on the parameter δ (in
addition to the other input parameters: n, δ and the radius of the disk). If the
input shape is found to be approximable, the rational-arithmetic algorithm also
computes an approximate solution shape for the problem. For convex shapes, the
complexity of the exact decision algorithm drops to O(n), which is also the time
required to compute a solution shape P with at most one more vertex than a vertex-minimal
one. Our study is motivated by applications from two different domains. However,
since the offset operation has numerous uses, we anticipate that the reverse question
that we study here will be still more broadly applicable. We present results obtained
with our implementation of the rational-arithmetic algorithm.'
author:
- first_name: Eric
full_name: Berberich, Eric
last_name: Berberich
- first_name: Dan
full_name: Halperin, Dan
last_name: Halperin
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
- first_name: Roza
full_name: Pogalnikova, Roza
last_name: Pogalnikova
citation:
ama: 'Berberich E, Halperin D, Kerber M, Pogalnikova R. Deconstructing approximate
offsets. In: Proceedings of the Twenty-Seventh Annual Symposium on Computational
Geometry. ACM; 2011:187-196. doi:10.1145/1998196.1998225'
apa: 'Berberich, E., Halperin, D., Kerber, M., & Pogalnikova, R. (2011). Deconstructing
approximate offsets. In Proceedings of the twenty-seventh annual symposium
on Computational geometry (pp. 187–196). Paris, France: ACM. https://doi.org/10.1145/1998196.1998225'
chicago: Berberich, Eric, Dan Halperin, Michael Kerber, and Roza Pogalnikova. “Deconstructing
Approximate Offsets.” In Proceedings of the Twenty-Seventh Annual Symposium
on Computational Geometry, 187–96. ACM, 2011. https://doi.org/10.1145/1998196.1998225.
ieee: E. Berberich, D. Halperin, M. Kerber, and R. Pogalnikova, “Deconstructing
approximate offsets,” in Proceedings of the twenty-seventh annual symposium
on Computational geometry, Paris, France, 2011, pp. 187–196.
ista: 'Berberich E, Halperin D, Kerber M, Pogalnikova R. 2011. Deconstructing approximate
offsets. Proceedings of the twenty-seventh annual symposium on Computational geometry.
SCG: Symposium on Computational Geometry, 187–196.'
mla: Berberich, Eric, et al. “Deconstructing Approximate Offsets.” Proceedings
of the Twenty-Seventh Annual Symposium on Computational Geometry, ACM, 2011,
pp. 187–96, doi:10.1145/1998196.1998225.
short: E. Berberich, D. Halperin, M. Kerber, R. Pogalnikova, in:, Proceedings of
the Twenty-Seventh Annual Symposium on Computational Geometry, ACM, 2011, pp.
187–196.
conference:
end_date: 2011-06-15
location: Paris, France
name: 'SCG: Symposium on Computational Geometry'
start_date: 2011-06-13
date_created: 2018-12-11T12:02:42Z
date_published: 2011-06-13T00:00:00Z
date_updated: 2023-02-23T11:12:57Z
day: '13'
department:
- _id: HeEd
doi: 10.1145/1998196.1998225
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1109.2158
month: '06'
oa: 1
oa_version: Preprint
page: 187 - 196
publication: Proceedings of the twenty-seventh annual symposium on Computational geometry
publication_status: published
publisher: ACM
publist_id: '3306'
quality_controlled: '1'
related_material:
record:
- id: '3115'
relation: later_version
status: public
scopus_import: 1
status: public
title: Deconstructing approximate offsets
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3330'
abstract:
- lang: eng
text: We consider the problem of approximating all real roots of a square-free polynomial
f. Given isolating intervals, our algorithm refines each of them to a width at
most 2-L, that is, each of the roots is approximated to L bits after the binary
point. Our method provides a certified answer for arbitrary real polynomials,
only requiring finite approximations of the polynomial coefficient and choosing
a suitable working precision adaptively. In this way, we get a correct algorithm
that is simple to implement and practically efficient. Our algorithm uses the
quadratic interval refinement method; we adapt that method to be able to cope
with inaccuracies when evaluating f, without sacrificing its quadratic convergence
behavior. We prove a bound on the bit complexity of our algorithm in terms of
degree, coefficient size and discriminant. Our bound improves previous work on
integer polynomials by a factor of deg f and essentially matches best known theoretical
bounds on root approximation which are obtained by very sophisticated algorithms.
article_processing_charge: No
arxiv: 1
author:
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
- first_name: Michael
full_name: Sagraloff, Michael
last_name: Sagraloff
citation:
ama: 'Kerber M, Sagraloff M. Root refinement for real polynomials. In: Springer;
2011:209-216. doi:10.1145/1993886.1993920'
apa: 'Kerber, M., & Sagraloff, M. (2011). Root refinement for real polynomials
(pp. 209–216). Presented at the ISSAC: International Symposium on Symbolic and
Algebraic Computation, California, USA: Springer. https://doi.org/10.1145/1993886.1993920'
chicago: Kerber, Michael, and Michael Sagraloff. “Root Refinement for Real Polynomials,”
209–16. Springer, 2011. https://doi.org/10.1145/1993886.1993920.
ieee: 'M. Kerber and M. Sagraloff, “Root refinement for real polynomials,” presented
at the ISSAC: International Symposium on Symbolic and Algebraic Computation, California,
USA, 2011, pp. 209–216.'
ista: 'Kerber M, Sagraloff M. 2011. Root refinement for real polynomials. ISSAC:
International Symposium on Symbolic and Algebraic Computation, 209–216.'
mla: Kerber, Michael, and Michael Sagraloff. Root Refinement for Real Polynomials.
Springer, 2011, pp. 209–16, doi:10.1145/1993886.1993920.
short: M. Kerber, M. Sagraloff, in:, Springer, 2011, pp. 209–216.
conference:
end_date: 2011-06-11
location: California, USA
name: 'ISSAC: International Symposium on Symbolic and Algebraic Computation'
start_date: 2011-06-08
date_created: 2018-12-11T12:02:43Z
date_published: 2011-06-08T00:00:00Z
date_updated: 2021-01-12T07:42:42Z
day: '08'
department:
- _id: HeEd
doi: 10.1145/1993886.1993920
external_id:
arxiv:
- '1104.1362'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1104.1362
month: '06'
oa: 1
oa_version: Preprint
page: 209 - 216
publication_status: published
publisher: Springer
publist_id: '3304'
quality_controlled: '1'
scopus_import: 1
status: public
title: Root refinement for real polynomials
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2011'
...