---
_id: '1624'
abstract:
- lang: eng
text: Population structure can facilitate evolution of cooperation. In a structured
population, cooperators can form clusters which resist exploitation by defectors.
Recently, it was observed that a shift update rule is an extremely strong amplifier
of cooperation in a one dimensional spatial model. For the shift update rule,
an individual is chosen for reproduction proportional to fecundity; the offspring
is placed next to the parent; a random individual dies. Subsequently, the population
is rearranged (shifted) until all individual cells are again evenly spaced out.
For large population size and a one dimensional population structure, the shift
update rule favors cooperation for any benefit-to-cost ratio greater than one.
But every attempt to generalize shift updating to higher dimensions while maintaining
its strong effect has failed. The reason is that in two dimensions the clusters
are fragmented by the movements caused by rearranging the cells. Here we introduce
the natural phenomenon of a repulsive force between cells of different types.
After a birth and death event, the cells are being rearranged minimizing the overall
energy expenditure. If the repulsive force is sufficiently high, shift becomes
a strong promoter of cooperation in two dimensions.
acknowledgement: 'The research was supported by the Austrian Science Fund (FWF) Grant
No P23499-N23, FWF NFN Grant No S11407-N23 (RiSE/SHiNE), ERC Start grant (279307:
Graph Games), and Microsoft Faculty Fellows award. Support from the John Templeton
foundation is gratefully acknowledged.'
article_number: '17147'
author:
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Ben
full_name: Adlam, Ben
last_name: Adlam
- first_name: Martin
full_name: Nowak, Martin
last_name: Nowak
citation:
ama: Pavlogiannis A, Chatterjee K, Adlam B, Nowak M. Cellular cooperation with shift
updating and repulsion. Scientific Reports. 2015;5. doi:10.1038/srep17147
apa: Pavlogiannis, A., Chatterjee, K., Adlam, B., & Nowak, M. (2015). Cellular
cooperation with shift updating and repulsion. Scientific Reports. Nature
Publishing Group. https://doi.org/10.1038/srep17147
chicago: Pavlogiannis, Andreas, Krishnendu Chatterjee, Ben Adlam, and Martin Nowak.
“Cellular Cooperation with Shift Updating and Repulsion.” Scientific Reports.
Nature Publishing Group, 2015. https://doi.org/10.1038/srep17147.
ieee: A. Pavlogiannis, K. Chatterjee, B. Adlam, and M. Nowak, “Cellular cooperation
with shift updating and repulsion,” Scientific Reports, vol. 5. Nature
Publishing Group, 2015.
ista: Pavlogiannis A, Chatterjee K, Adlam B, Nowak M. 2015. Cellular cooperation
with shift updating and repulsion. Scientific Reports. 5, 17147.
mla: Pavlogiannis, Andreas, et al. “Cellular Cooperation with Shift Updating and
Repulsion.” Scientific Reports, vol. 5, 17147, Nature Publishing Group,
2015, doi:10.1038/srep17147.
short: A. Pavlogiannis, K. Chatterjee, B. Adlam, M. Nowak, Scientific Reports 5
(2015).
date_created: 2018-12-11T11:53:06Z
date_published: 2015-11-25T00:00:00Z
date_updated: 2021-01-12T06:52:05Z
day: '25'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1038/srep17147
ec_funded: 1
file:
- access_level: open_access
checksum: 38e06d8310d2087cae5f6d4d4bfe082b
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:12:29Z
date_updated: 2020-07-14T12:45:07Z
file_id: '4947'
file_name: IST-2016-466-v1+1_srep17147.pdf
file_size: 1021931
relation: main_file
file_date_updated: 2020-07-14T12:45:07Z
has_accepted_license: '1'
intvolume: ' 5'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '11'
oa: 1
oa_version: Published Version
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: Scientific Reports
publication_status: published
publisher: Nature Publishing Group
publist_id: '5536'
pubrep_id: '466'
quality_controlled: '1'
scopus_import: 1
status: public
title: Cellular cooperation with shift updating and repulsion
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 5
year: '2015'
...
---
_id: '1625'
abstract:
- lang: eng
text: In recent years we have seen numerous improvements on 3D scanning and tracking
of human faces, greatly advancing the creation of digital doubles for film and
video games. However, despite the high-resolution quality of the reconstruction
approaches available, current methods are unable to capture one of the most important
regions of the face - the eye region. In this work we present the first method
for detailed spatio-temporal reconstruction of eyelids. Tracking and reconstructing
eyelids is extremely challenging, as this region exhibits very complex and unique
skin deformation where skin is folded under while opening the eye. Furthermore,
eyelids are often only partially visible and obstructed due to selfocclusion and
eyelashes. Our approach is to combine a geometric deformation model with image
data, leveraging multi-view stereo, optical flow, contour tracking and wrinkle
detection from local skin appearance. Our deformation model serves as a prior
that enables reconstruction of eyelids even under strong self-occlusions caused
by rolling and folding skin as the eye opens and closes. The output is a person-specific,
time-varying eyelid reconstruction with anatomically plausible deformations. Our
high-resolution detailed eyelids couple naturally with current facial performance
capture approaches. As a result, our method can largely increase the fidelity
of facial capture and the creation of digital doubles.
article_number: '44'
author:
- first_name: Amit
full_name: Bermano, Amit
last_name: Bermano
- first_name: Thabo
full_name: Beeler, Thabo
last_name: Beeler
- first_name: Yeara
full_name: Kozlov, Yeara
last_name: Kozlov
- first_name: Derek
full_name: Bradley, Derek
last_name: Bradley
- first_name: Bernd
full_name: Bickel, Bernd
id: 49876194-F248-11E8-B48F-1D18A9856A87
last_name: Bickel
orcid: 0000-0001-6511-9385
- first_name: Markus
full_name: Gross, Markus
last_name: Gross
citation:
ama: 'Bermano A, Beeler T, Kozlov Y, Bradley D, Bickel B, Gross M. Detailed spatio-temporal
reconstruction of eyelids. In: Vol 34. ACM; 2015. doi:10.1145/2766924'
apa: 'Bermano, A., Beeler, T., Kozlov, Y., Bradley, D., Bickel, B., & Gross,
M. (2015). Detailed spatio-temporal reconstruction of eyelids (Vol. 34). Presented
at the SIGGRAPH: Special Interest Group on Computer Graphics and Interactive Techniques,
Los Angeles, CA, United States: ACM. https://doi.org/10.1145/2766924'
chicago: Bermano, Amit, Thabo Beeler, Yeara Kozlov, Derek Bradley, Bernd Bickel,
and Markus Gross. “Detailed Spatio-Temporal Reconstruction of Eyelids,” Vol. 34.
ACM, 2015. https://doi.org/10.1145/2766924.
ieee: 'A. Bermano, T. Beeler, Y. Kozlov, D. Bradley, B. Bickel, and M. Gross, “Detailed
spatio-temporal reconstruction of eyelids,” presented at the SIGGRAPH: Special
Interest Group on Computer Graphics and Interactive Techniques, Los Angeles, CA,
United States, 2015, vol. 34, no. 4.'
ista: 'Bermano A, Beeler T, Kozlov Y, Bradley D, Bickel B, Gross M. 2015. Detailed
spatio-temporal reconstruction of eyelids. SIGGRAPH: Special Interest Group on
Computer Graphics and Interactive Techniques vol. 34, 44.'
mla: Bermano, Amit, et al. Detailed Spatio-Temporal Reconstruction of Eyelids.
Vol. 34, no. 4, 44, ACM, 2015, doi:10.1145/2766924.
short: A. Bermano, T. Beeler, Y. Kozlov, D. Bradley, B. Bickel, M. Gross, in:, ACM,
2015.
conference:
end_date: 2015-08-13
location: Los Angeles, CA, United States
name: 'SIGGRAPH: Special Interest Group on Computer Graphics and Interactive Techniques'
start_date: 2015-08-09
date_created: 2018-12-11T11:53:06Z
date_published: 2015-07-27T00:00:00Z
date_updated: 2021-01-12T06:52:05Z
day: '27'
department:
- _id: BeBi
doi: 10.1145/2766924
intvolume: ' 34'
issue: '4'
language:
- iso: eng
month: '07'
oa_version: None
publication_status: published
publisher: ACM
publist_id: '5535'
quality_controlled: '1'
scopus_import: 1
status: public
title: Detailed spatio-temporal reconstruction of eyelids
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 34
year: '2015'
...
---
_id: '1626'
abstract:
- lang: eng
text: This paper introduces "OmniAD," a novel data-driven pipeline to
model and acquire the aerodynamics of three-dimensional rigid objects. Traditionally,
aerodynamics are examined through elaborate wind tunnel experiments or expensive
fluid dynamics computations, and are only measured for a small number of discrete
wind directions. OmniAD allows the evaluation of aerodynamic forces, such as drag
and lift, for any incoming wind direction using a novel representation based on
spherical harmonics. Our datadriven technique acquires the aerodynamic properties
of an object simply by capturing its falling motion using a single camera. Once
model parameters are estimated, OmniAD enables realistic realtime simulation of
rigid bodies, such as the tumbling and gliding of leaves, without simulating the
surrounding air. In addition, we propose an intuitive user interface based on
OmniAD to interactively design three-dimensional kites that actually fly. Various
nontraditional kites were designed to demonstrate the physical validity of our
model.
alternative_title:
- ACM Transactions on Graphics
article_number: '113'
author:
- first_name: Tobias
full_name: Martin, Tobias
last_name: Martin
- first_name: Nobuyuki
full_name: Umetani, Nobuyuki
last_name: Umetani
- first_name: Bernd
full_name: Bickel, Bernd
id: 49876194-F248-11E8-B48F-1D18A9856A87
last_name: Bickel
orcid: 0000-0001-6511-9385
citation:
ama: 'Martin T, Umetani N, Bickel B. OmniAD: Data-driven omni-directional aerodynamics.
In: Vol 34. ACM; 2015. doi:10.1145/2766919'
apa: 'Martin, T., Umetani, N., & Bickel, B. (2015). OmniAD: Data-driven omni-directional
aerodynamics (Vol. 34). Presented at the SIGGRAPH: Special Interest Group on Computer
Graphics and Interactive Techniques, Los Angeles, CA, United States: ACM. https://doi.org/10.1145/2766919'
chicago: 'Martin, Tobias, Nobuyuki Umetani, and Bernd Bickel. “OmniAD: Data-Driven
Omni-Directional Aerodynamics,” Vol. 34. ACM, 2015. https://doi.org/10.1145/2766919.'
ieee: 'T. Martin, N. Umetani, and B. Bickel, “OmniAD: Data-driven omni-directional
aerodynamics,” presented at the SIGGRAPH: Special Interest Group on Computer Graphics
and Interactive Techniques, Los Angeles, CA, United States, 2015, vol. 34, no.
4.'
ista: 'Martin T, Umetani N, Bickel B. 2015. OmniAD: Data-driven omni-directional
aerodynamics. SIGGRAPH: Special Interest Group on Computer Graphics and Interactive
Techniques, ACM Transactions on Graphics, vol. 34, 113.'
mla: 'Martin, Tobias, et al. OmniAD: Data-Driven Omni-Directional Aerodynamics.
Vol. 34, no. 4, 113, ACM, 2015, doi:10.1145/2766919.'
short: T. Martin, N. Umetani, B. Bickel, in:, ACM, 2015.
conference:
end_date: 2015-08-13
location: Los Angeles, CA, United States
name: 'SIGGRAPH: Special Interest Group on Computer Graphics and Interactive Techniques'
start_date: 2015-08-09
date_created: 2018-12-11T11:53:06Z
date_published: 2015-07-27T00:00:00Z
date_updated: 2021-01-12T06:52:05Z
day: '27'
department:
- _id: BeBi
doi: 10.1145/2766919
intvolume: ' 34'
issue: '4'
language:
- iso: eng
month: '07'
oa_version: None
publication_status: published
publisher: ACM
publist_id: '5532'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'OmniAD: Data-driven omni-directional aerodynamics'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 34
year: '2015'
...
---
_id: '1627'
abstract:
- lang: eng
text: We present a computational tool for fabrication-oriented design of flexible
rod meshes. Given a deformable surface and a set of deformed poses as input, our
method automatically computes a printable rod mesh that, once manufactured, closely
matches the input poses under the same boundary conditions. The core of our method
is formed by an optimization scheme that adjusts the cross-sectional profiles
of the rods and their rest centerline in order to best approximate the target
deformations. This approach allows us to locally control the bending and stretching
resistance of the surface with a single material, yielding high design flexibility
and low fabrication cost.
acknowledgement: This work was supported in part by grants from the Spanish Ministry
of Economy (TIN2012-35840), and the European Research Council (ERC Starting Grant
no. 280135 Animetrics).
article_number: '138'
author:
- first_name: Jesús
full_name: Pérez, Jesús
last_name: Pérez
- first_name: Bernhard
full_name: Thomaszewski, Bernhard
last_name: Thomaszewski
- first_name: Stelian
full_name: Coros, Stelian
last_name: Coros
- first_name: Bernd
full_name: Bickel, Bernd
id: 49876194-F248-11E8-B48F-1D18A9856A87
last_name: Bickel
orcid: 0000-0001-6511-9385
- first_name: José
full_name: Canabal, José
last_name: Canabal
- first_name: Robert
full_name: Sumner, Robert
last_name: Sumner
- first_name: Miguel
full_name: Otaduy, Miguel
last_name: Otaduy
citation:
ama: 'Pérez J, Thomaszewski B, Coros S, et al. Design and fabrication of flexible
rod meshes. In: Vol 34. ACM; 2015. doi:10.1145/2766998'
apa: 'Pérez, J., Thomaszewski, B., Coros, S., Bickel, B., Canabal, J., Sumner, R.,
& Otaduy, M. (2015). Design and fabrication of flexible rod meshes (Vol. 34).
Presented at the SIGGRAPH: Special Interest Group on Computer Graphics and Interactive
Techniques, Los Angeles, CA, United States: ACM. https://doi.org/10.1145/2766998'
chicago: Pérez, Jesús, Bernhard Thomaszewski, Stelian Coros, Bernd Bickel, José
Canabal, Robert Sumner, and Miguel Otaduy. “Design and Fabrication of Flexible
Rod Meshes,” Vol. 34. ACM, 2015. https://doi.org/10.1145/2766998.
ieee: 'J. Pérez et al., “Design and fabrication of flexible rod meshes,”
presented at the SIGGRAPH: Special Interest Group on Computer Graphics and Interactive
Techniques, Los Angeles, CA, United States, 2015, vol. 34, no. 4.'
ista: 'Pérez J, Thomaszewski B, Coros S, Bickel B, Canabal J, Sumner R, Otaduy M.
2015. Design and fabrication of flexible rod meshes. SIGGRAPH: Special Interest
Group on Computer Graphics and Interactive Techniques vol. 34, 138.'
mla: Pérez, Jesús, et al. Design and Fabrication of Flexible Rod Meshes.
Vol. 34, no. 4, 138, ACM, 2015, doi:10.1145/2766998.
short: J. Pérez, B. Thomaszewski, S. Coros, B. Bickel, J. Canabal, R. Sumner, M.
Otaduy, in:, ACM, 2015.
conference:
end_date: 2015-08-13
location: Los Angeles, CA, United States
name: 'SIGGRAPH: Special Interest Group on Computer Graphics and Interactive Techniques'
start_date: 2015-08-09
date_created: 2018-12-11T11:53:07Z
date_published: 2015-07-27T00:00:00Z
date_updated: 2021-01-12T06:52:06Z
day: '27'
department:
- _id: BeBi
doi: 10.1145/2766998
intvolume: ' 34'
issue: '4'
language:
- iso: eng
month: '07'
oa_version: None
publication_status: published
publisher: ACM
publist_id: '5530'
quality_controlled: '1'
scopus_import: 1
status: public
title: Design and fabrication of flexible rod meshes
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 34
year: '2015'
...
---
_id: '1628'
abstract:
- lang: eng
text: We propose a method for fabricating deformable objects with spatially varying
elasticity using 3D printing. Using a single, relatively stiff printer material,
our method designs an assembly of smallscale microstructures that have the effect
of a softer material at the object scale, with properties depending on the microstructure
used in each part of the object. We build on work in the area of metamaterials,
using numerical optimization to design tiled microstructures with desired properties,
but with the key difference that our method designs families of related structures
that can be interpolated to smoothly vary the material properties over a wide
range. To create an object with spatially varying elastic properties, we tile
the object's interior with microstructures drawn from these families, generating
a different microstructure for each cell using an efficient algorithm to select
compatible structures for neighboring cells. We show results computed for both
2D and 3D objects, validating several 2D and 3D printed structures using standard
material tests as well as demonstrating various example applications.
article_number: '136'
article_processing_charge: No
author:
- first_name: Christian
full_name: Schumacher, Christian
last_name: Schumacher
- first_name: Bernd
full_name: Bickel, Bernd
id: 49876194-F248-11E8-B48F-1D18A9856A87
last_name: Bickel
orcid: 0000-0001-6511-9385
- first_name: Jan
full_name: Rys, Jan
last_name: Rys
- first_name: Steve
full_name: Marschner, Steve
last_name: Marschner
- first_name: Chiara
full_name: Daraio, Chiara
last_name: Daraio
- first_name: Markus
full_name: Gross, Markus
last_name: Gross
citation:
ama: 'Schumacher C, Bickel B, Rys J, Marschner S, Daraio C, Gross M. Microstructures
to control elasticity in 3D printing. In: Vol 34. ACM; 2015. doi:10.1145/2766926'
apa: 'Schumacher, C., Bickel, B., Rys, J., Marschner, S., Daraio, C., & Gross,
M. (2015). Microstructures to control elasticity in 3D printing (Vol. 34). Presented
at the SIGGRAPH: Special Interest Group on Computer Graphics and Interactive Techniques,
Los Angeles, CA, USA: ACM. https://doi.org/10.1145/2766926'
chicago: Schumacher, Christian, Bernd Bickel, Jan Rys, Steve Marschner, Chiara Daraio,
and Markus Gross. “Microstructures to Control Elasticity in 3D Printing,” Vol.
34. ACM, 2015. https://doi.org/10.1145/2766926.
ieee: 'C. Schumacher, B. Bickel, J. Rys, S. Marschner, C. Daraio, and M. Gross,
“Microstructures to control elasticity in 3D printing,” presented at the SIGGRAPH:
Special Interest Group on Computer Graphics and Interactive Techniques, Los Angeles,
CA, USA, 2015, vol. 34, no. 4.'
ista: 'Schumacher C, Bickel B, Rys J, Marschner S, Daraio C, Gross M. 2015. Microstructures
to control elasticity in 3D printing. SIGGRAPH: Special Interest Group on Computer
Graphics and Interactive Techniques vol. 34, 136.'
mla: Schumacher, Christian, et al. Microstructures to Control Elasticity in 3D
Printing. Vol. 34, no. 4, 136, ACM, 2015, doi:10.1145/2766926.
short: C. Schumacher, B. Bickel, J. Rys, S. Marschner, C. Daraio, M. Gross, in:,
ACM, 2015.
conference:
end_date: 2015-08-13
location: Los Angeles, CA, USA
name: 'SIGGRAPH: Special Interest Group on Computer Graphics and Interactive Techniques'
start_date: 2015-08-09
date_created: 2018-12-11T11:53:07Z
date_published: 2015-08-01T00:00:00Z
date_updated: 2021-01-12T06:52:06Z
day: '01'
department:
- _id: BeBi
doi: 10.1145/2766926
intvolume: ' 34'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1145/2766926
month: '08'
oa: 1
oa_version: Published Version
publication_status: published
publisher: ACM
publist_id: '5529'
quality_controlled: '1'
scopus_import: 1
status: public
title: Microstructures to control elasticity in 3D printing
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 34
year: '2015'
...
---
_id: '1630'
abstract:
- lang: eng
text: We present a method to learn and propagate shape placements in 2D polygonal
scenes from a few examples provided by a user. The placement of a shape is modeled
as an oriented bounding box. Simple geometric relationships between this bounding
box and nearby scene polygons define a feature set for the placement. The feature
sets of all example placements are then used to learn a probabilistic model over
all possible placements and scenes. With this model, we can generate a new set
of placements with similar geometric relationships in any given scene. We introduce
extensions that enable propagation and generation of shapes in 3D scenes, as
well as the application of a learned modeling session to large scenes without
additional user interaction. These concepts allow us to generate complex scenes
with thousands of objects with relatively little user interaction.
acknowledgement: This publication is based upon work supported by the KAUST Office
of Competitive Research Funds (OCRF) under Award No. 62140401, the KAUST Visual
Computing Center and the Austrian Science Fund (FWF) projects DEEP PICTURES (no.
P24352-N23) and Data-Driven Procedural Modeling of Interiors (no. P24600-N23).
article_number: '108'
author:
- first_name: Paul
full_name: Guerrero, Paul
last_name: Guerrero
- first_name: Stefan
full_name: Jeschke, Stefan
id: 44D6411A-F248-11E8-B48F-1D18A9856A87
last_name: Jeschke
- first_name: Michael
full_name: Wimmer, Michael
last_name: Wimmer
- first_name: Peter
full_name: Wonka, Peter
last_name: Wonka
citation:
ama: 'Guerrero P, Jeschke S, Wimmer M, Wonka P. Learning shape placements by example.
In: Vol 34. ACM; 2015. doi:10.1145/2766933'
apa: 'Guerrero, P., Jeschke, S., Wimmer, M., & Wonka, P. (2015). Learning shape
placements by example (Vol. 34). Presented at the SIGGRAPH: Special Interest Group
on Computer Graphics and Interactive Techniques, Los Angeles, CA, United States:
ACM. https://doi.org/10.1145/2766933'
chicago: Guerrero, Paul, Stefan Jeschke, Michael Wimmer, and Peter Wonka. “Learning
Shape Placements by Example,” Vol. 34. ACM, 2015. https://doi.org/10.1145/2766933.
ieee: 'P. Guerrero, S. Jeschke, M. Wimmer, and P. Wonka, “Learning shape placements
by example,” presented at the SIGGRAPH: Special Interest Group on Computer Graphics
and Interactive Techniques, Los Angeles, CA, United States, 2015, vol. 34, no.
4.'
ista: 'Guerrero P, Jeschke S, Wimmer M, Wonka P. 2015. Learning shape placements
by example. SIGGRAPH: Special Interest Group on Computer Graphics and Interactive
Techniques vol. 34, 108.'
mla: Guerrero, Paul, et al. Learning Shape Placements by Example. Vol. 34,
no. 4, 108, ACM, 2015, doi:10.1145/2766933.
short: P. Guerrero, S. Jeschke, M. Wimmer, P. Wonka, in:, ACM, 2015.
conference:
end_date: 2015-08-13
location: Los Angeles, CA, United States
name: 'SIGGRAPH: Special Interest Group on Computer Graphics and Interactive Techniques'
start_date: 2015-08-09
date_created: 2018-12-11T11:53:08Z
date_published: 2015-07-27T00:00:00Z
date_updated: 2021-01-12T06:52:07Z
day: '27'
ddc:
- '000'
department:
- _id: ChWo
doi: 10.1145/2766933
file:
- access_level: open_access
checksum: 8b05a51e372c9b0b5af9a00098a9538b
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:07:49Z
date_updated: 2020-07-14T12:45:07Z
file_id: '4647'
file_name: IST-2016-576-v1+1_guerrero-2015-lsp-paper.pdf
file_size: 11902290
relation: main_file
file_date_updated: 2020-07-14T12:45:07Z
has_accepted_license: '1'
intvolume: ' 34'
issue: '4'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Submitted Version
project:
- _id: 25357BD2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 24352-N23
name: 'Deep Pictures: Creating Visual and Haptic Vector Images'
publication_status: published
publisher: ACM
publist_id: '5525'
pubrep_id: '576'
quality_controlled: '1'
scopus_import: 1
status: public
title: Learning shape placements by example
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 34
year: '2015'
...
---
_id: '1632'
abstract:
- lang: eng
text: "This paper presents a liquid simulation technique that enforces the incompressibility
condition using a stream function solve instead of a pressure projection. Previous
methods have used stream function techniques for the simulation of detailed single-phase
flows, but a formulation for liquid simulation has proved elusive in part due
to the free surface boundary conditions. In this paper, we introduce a stream
function approach to liquid simulations with novel boundary conditions for free
surfaces, solid obstacles, and solid-fluid coupling.\r\n\r\nAlthough our approach
increases the dimension of the linear system necessary to enforce incompressibility,
it provides interesting and surprising benefits. First, the resulting flow is
guaranteed to be divergence-free regardless of the accuracy of the solve. Second,
our free-surface boundary conditions guarantee divergence-free motion even in
the un-simulated air phase, which enables two-phase flow simulation by only computing
a single phase. We implemented this method using a variant of FLIP simulation
which only samples particles within a narrow band of the liquid surface, and we
illustrate the effectiveness of our method for detailed two-phase flow simulations
with complex boundaries, detailed bubble interactions, and two-way solid-fluid
coupling."
acknowledgement: The first author was supported by a JSPS Postdoctoral Fellowship
for Research Abroad. This work was also supported by the ERC projects ERC-2014-StG-637014
realFlow and ERC-2014- StG-638176 BigSplash.
alternative_title:
- ACM Transactions on Graphics
article_number: '53'
author:
- first_name: Ryoichi
full_name: Ando, Ryoichi
last_name: Ando
- first_name: Nils
full_name: Thuerey, Nils
last_name: Thuerey
- first_name: Christopher J
full_name: Wojtan, Christopher J
id: 3C61F1D2-F248-11E8-B48F-1D18A9856A87
last_name: Wojtan
orcid: 0000-0001-6646-5546
citation:
ama: 'Ando R, Thuerey N, Wojtan C. A stream function solver for liquid simulations.
In: Vol 34. ACM; 2015. doi:10.1145/2766935'
apa: 'Ando, R., Thuerey, N., & Wojtan, C. (2015). A stream function solver for
liquid simulations (Vol. 34). Presented at the SIGGRAPH: Special Interest Group
on Computer Graphics and Interactive Techniques, Los Angeles, CA, USA: ACM. https://doi.org/10.1145/2766935'
chicago: Ando, Ryoichi, Nils Thuerey, and Chris Wojtan. “A Stream Function Solver
for Liquid Simulations,” Vol. 34. ACM, 2015. https://doi.org/10.1145/2766935.
ieee: 'R. Ando, N. Thuerey, and C. Wojtan, “A stream function solver for liquid
simulations,” presented at the SIGGRAPH: Special Interest Group on Computer Graphics
and Interactive Techniques, Los Angeles, CA, USA, 2015, vol. 34, no. 4.'
ista: 'Ando R, Thuerey N, Wojtan C. 2015. A stream function solver for liquid simulations.
SIGGRAPH: Special Interest Group on Computer Graphics and Interactive Techniques,
ACM Transactions on Graphics, vol. 34, 53.'
mla: Ando, Ryoichi, et al. A Stream Function Solver for Liquid Simulations.
Vol. 34, no. 4, 53, ACM, 2015, doi:10.1145/2766935.
short: R. Ando, N. Thuerey, C. Wojtan, in:, ACM, 2015.
conference:
end_date: 2015-08-13
location: Los Angeles, CA, USA
name: 'SIGGRAPH: Special Interest Group on Computer Graphics and Interactive Techniques'
start_date: 2015-08-09
date_created: 2018-12-11T11:53:09Z
date_published: 2015-07-27T00:00:00Z
date_updated: 2023-02-23T10:07:37Z
day: '27'
ddc:
- '000'
department:
- _id: ChWo
doi: 10.1145/2766935
file:
- access_level: open_access
checksum: 7a9afdfaba9209157ce19376e15bc90b
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:11:52Z
date_updated: 2020-07-14T12:45:07Z
file_id: '4909'
file_name: IST-2016-610-v1+1_vecpotential.pdf
file_size: 21831121
relation: main_file
file_date_updated: 2020-07-14T12:45:07Z
has_accepted_license: '1'
intvolume: ' 34'
issue: '4'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Submitted Version
publication_status: published
publisher: ACM
publist_id: '5523'
pubrep_id: '610'
quality_controlled: '1'
scopus_import: 1
status: public
title: A stream function solver for liquid simulations
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 34
year: '2015'
...
---
_id: '1633'
abstract:
- lang: eng
text: "We present a method for simulating brittle fracture under the assumptions
of quasi-static linear elastic fracture mechanics (LEFM). Using the boundary element
method (BEM) and Lagrangian crack-fronts, we produce highly detailed fracture
surfaces. The computational cost of the BEM is alleviated by using a low-resolution
mesh and interpolating the resulting stress intensity factors when propagating
the high-resolution crack-front.\r\n\r\nOur system produces physics-based fracture
surfaces with high spatial and temporal resolution, taking spatial variation of
material toughness and/or strength into account. It also allows for crack initiation
to be handled separately from crack propagation, which is not only more reasonable
from a physics perspective, but can also be used to control the simulation.\r\n\r\nSeparating
the resolution of the crack-front from the resolution of the computational mesh
increases the efficiency and therefore the amount of visual detail on the resulting
fracture surfaces. The BEM also allows us to re-use previously computed blocks
of the system matrix."
article_number: '151'
author:
- first_name: David
full_name: Hahn, David
id: 357A6A66-F248-11E8-B48F-1D18A9856A87
last_name: Hahn
- first_name: Christopher J
full_name: Wojtan, Christopher J
id: 3C61F1D2-F248-11E8-B48F-1D18A9856A87
last_name: Wojtan
orcid: 0000-0001-6646-5546
citation:
ama: 'Hahn D, Wojtan C. High-resolution brittle fracture simulation with boundary
elements. In: Vol 34. ACM; 2015. doi:10.1145/2766896'
apa: 'Hahn, D., & Wojtan, C. (2015). High-resolution brittle fracture simulation
with boundary elements (Vol. 34). Presented at the SIGGRAPH: Special Interest
Group on Computer Graphics and Interactive Techniques, Los Angeles, CA, United
States: ACM. https://doi.org/10.1145/2766896'
chicago: Hahn, David, and Chris Wojtan. “High-Resolution Brittle Fracture Simulation
with Boundary Elements,” Vol. 34. ACM, 2015. https://doi.org/10.1145/2766896.
ieee: 'D. Hahn and C. Wojtan, “High-resolution brittle fracture simulation with
boundary elements,” presented at the SIGGRAPH: Special Interest Group on Computer
Graphics and Interactive Techniques, Los Angeles, CA, United States, 2015, vol.
34, no. 4.'
ista: 'Hahn D, Wojtan C. 2015. High-resolution brittle fracture simulation with
boundary elements. SIGGRAPH: Special Interest Group on Computer Graphics and Interactive
Techniques vol. 34, 151.'
mla: Hahn, David, and Chris Wojtan. High-Resolution Brittle Fracture Simulation
with Boundary Elements. Vol. 34, no. 4, 151, ACM, 2015, doi:10.1145/2766896.
short: D. Hahn, C. Wojtan, in:, ACM, 2015.
conference:
end_date: 2015-08-13
location: Los Angeles, CA, United States
name: 'SIGGRAPH: Special Interest Group on Computer Graphics and Interactive Techniques'
start_date: 2015-08-09
date_created: 2018-12-11T11:53:09Z
date_published: 2015-07-27T00:00:00Z
date_updated: 2023-09-07T12:02:56Z
day: '27'
ddc:
- '000'
department:
- _id: ChWo
doi: 10.1145/2766896
ec_funded: 1
file:
- access_level: open_access
checksum: 955aee971983f6b6152bcc1c9b4a7c20
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:15:13Z
date_updated: 2020-07-14T12:45:07Z
file_id: '5131'
file_name: IST-2016-609-v1+1_FractureBEM.pdf
file_size: 20154270
relation: main_file
file_date_updated: 2020-07-14T12:45:07Z
has_accepted_license: '1'
intvolume: ' 34'
issue: '4'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Submitted Version
project:
- _id: 2533E772-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '638176'
name: Efficient Simulation of Natural Phenomena at Extremely Large Scales
publication_status: published
publisher: ACM
publist_id: '5522'
pubrep_id: '609'
quality_controlled: '1'
related_material:
record:
- id: '839'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: High-resolution brittle fracture simulation with boundary elements
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 34
year: '2015'
...
---
_id: '1634'
abstract:
- lang: eng
text: Simulating the delightful dynamics of soap films, bubbles, and foams has traditionally
required the use of a fully three-dimensional many-phase Navier-Stokes solver,
even though their visual appearance is completely dominated by the thin liquid
surface. We depart from earlier work on soap bubbles and foams by noting that
their dynamics are naturally described by a Lagrangian vortex sheet model in which
circulation is the primary variable. This leads us to derive a novel circulation-preserving
surface-only discretization of foam dynamics driven by surface tension on a non-manifold
triangle mesh. We represent the surface using a mesh-based multimaterial surface
tracker which supports complex bubble topology changes, and evolve the surface
according to the ambient air flow induced by a scalar circulation field stored
on the mesh. Surface tension forces give rise to a simple update rule for circulation,
even at non-manifold Plateau borders, based on a discrete measure of signed scalar
mean curvature. We further incorporate vertex constraints to enable the interaction
of soap films with wires. The result is a method that is at once simple, robust,
and efficient, yet able to capture an array of soap films behaviors including
foam rearrangement, catenoid collapse, blowing bubbles, and double bubbles being
pulled apart.
article_number: '149'
author:
- first_name: Fang
full_name: Da, Fang
last_name: Da
- first_name: Christopher
full_name: Batty, Christopher
last_name: Batty
- 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: Eitan
full_name: Grinspun, Eitan
last_name: Grinspun
citation:
ama: 'Da F, Batty C, Wojtan C, Grinspun E. Double bubbles sans toil and trouble:
discrete circulation-preserving vortex sheets for soap films and foams. In: Vol
34. ACM; 2015. doi:10.1145/2767003'
apa: 'Da, F., Batty, C., Wojtan, C., & Grinspun, E. (2015). Double bubbles sans
toil and trouble: discrete circulation-preserving vortex sheets for soap films
and foams (Vol. 34). Presented at the SIGGRAPH: Special Interest Group on Computer
Graphics and Interactive Techniques, Los Angeles, CA, United States: ACM. https://doi.org/10.1145/2767003'
chicago: 'Da, Fang, Christopher Batty, Chris Wojtan, and Eitan Grinspun. “Double
Bubbles sans Toil and Trouble: Discrete Circulation-Preserving Vortex Sheets for
Soap Films and Foams,” Vol. 34. ACM, 2015. https://doi.org/10.1145/2767003.'
ieee: 'F. Da, C. Batty, C. Wojtan, and E. Grinspun, “Double bubbles sans toil and
trouble: discrete circulation-preserving vortex sheets for soap films and foams,”
presented at the SIGGRAPH: Special Interest Group on Computer Graphics and Interactive
Techniques, Los Angeles, CA, United States, 2015, vol. 34, no. 4.'
ista: 'Da F, Batty C, Wojtan C, Grinspun E. 2015. Double bubbles sans toil and trouble:
discrete circulation-preserving vortex sheets for soap films and foams. SIGGRAPH:
Special Interest Group on Computer Graphics and Interactive Techniques vol. 34,
149.'
mla: 'Da, Fang, et al. Double Bubbles sans Toil and Trouble: Discrete Circulation-Preserving
Vortex Sheets for Soap Films and Foams. Vol. 34, no. 4, 149, ACM, 2015, doi:10.1145/2767003.'
short: F. Da, C. Batty, C. Wojtan, E. Grinspun, in:, ACM, 2015.
conference:
end_date: 2015-08-13
location: Los Angeles, CA, United States
name: 'SIGGRAPH: Special Interest Group on Computer Graphics and Interactive Techniques'
start_date: 2015-08-09
date_created: 2018-12-11T11:53:09Z
date_published: 2015-07-27T00:00:00Z
date_updated: 2023-02-23T10:07:42Z
day: '27'
ddc:
- '000'
department:
- _id: ChWo
doi: 10.1145/2767003
ec_funded: 1
file:
- access_level: open_access
checksum: 57b07d78d2d612a8052744b37d4a71fa
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:11:14Z
date_updated: 2020-07-14T12:45:07Z
file_id: '4867'
file_name: IST-2016-608-v1+1_doublebubbles.pdf
file_size: 8973215
relation: main_file
file_date_updated: 2020-07-14T12:45:07Z
has_accepted_license: '1'
intvolume: ' 34'
issue: '4'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Submitted Version
project:
- _id: 2533E772-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '638176'
name: Efficient Simulation of Natural Phenomena at Extremely Large Scales
publication_status: published
publisher: ACM
publist_id: '5521'
pubrep_id: '608'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'Double bubbles sans toil and trouble: discrete circulation-preserving vortex
sheets for soap films and foams'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 34
year: '2015'
...
---
_id: '1635'
abstract:
- lang: eng
text: We calculate a Ricci curvature lower bound for some classical examples of
random walks, namely, a chain on a slice of the n-dimensional discrete cube (the
so-called Bernoulli-Laplace model) and the random transposition shuffle of the
symmetric group of permutations on n letters.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Matthias
full_name: Erbar, Matthias
last_name: Erbar
- first_name: Jan
full_name: Maas, Jan
id: 4C5696CE-F248-11E8-B48F-1D18A9856A87
last_name: Maas
orcid: 0000-0002-0845-1338
- first_name: Prasad
full_name: Tetali, Prasad
last_name: Tetali
citation:
ama: Erbar M, Maas J, Tetali P. Discrete Ricci curvature bounds for Bernoulli-Laplace
and random transposition models. Annales de la faculté des sciences de Toulouse.
2015;24(4):781-800. doi:10.5802/afst.1464
apa: Erbar, M., Maas, J., & Tetali, P. (2015). Discrete Ricci curvature bounds
for Bernoulli-Laplace and random transposition models. Annales de La Faculté
Des Sciences de Toulouse. Faculté des sciences de Toulouse. https://doi.org/10.5802/afst.1464
chicago: Erbar, Matthias, Jan Maas, and Prasad Tetali. “Discrete Ricci Curvature
Bounds for Bernoulli-Laplace and Random Transposition Models.” Annales de La
Faculté Des Sciences de Toulouse. Faculté des sciences de Toulouse, 2015.
https://doi.org/10.5802/afst.1464.
ieee: M. Erbar, J. Maas, and P. Tetali, “Discrete Ricci curvature bounds for Bernoulli-Laplace
and random transposition models,” Annales de la faculté des sciences de Toulouse,
vol. 24, no. 4. Faculté des sciences de Toulouse, pp. 781–800, 2015.
ista: Erbar M, Maas J, Tetali P. 2015. Discrete Ricci curvature bounds for Bernoulli-Laplace
and random transposition models. Annales de la faculté des sciences de Toulouse.
24(4), 781–800.
mla: Erbar, Matthias, et al. “Discrete Ricci Curvature Bounds for Bernoulli-Laplace
and Random Transposition Models.” Annales de La Faculté Des Sciences de Toulouse,
vol. 24, no. 4, Faculté des sciences de Toulouse, 2015, pp. 781–800, doi:10.5802/afst.1464.
short: M. Erbar, J. Maas, P. Tetali, Annales de La Faculté Des Sciences de Toulouse
24 (2015) 781–800.
date_created: 2018-12-11T11:53:10Z
date_published: 2015-01-01T00:00:00Z
date_updated: 2023-10-18T07:48:28Z
day: '01'
department:
- _id: JaMa
doi: 10.5802/afst.1464
external_id:
arxiv:
- '1409.8605'
intvolume: ' 24'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1409.8605
month: '01'
oa: 1
oa_version: Preprint
page: 781 - 800
publication: Annales de la faculté des sciences de Toulouse
publication_status: published
publisher: Faculté des sciences de Toulouse
publist_id: '5520'
quality_controlled: '1'
status: public
title: Discrete Ricci curvature bounds for Bernoulli-Laplace and random transposition
models
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 24
year: '2015'
...
---
_id: '1636'
abstract:
- lang: eng
text: "Constraint Satisfaction Problem (CSP) is a fundamental algorithmic problem
that appears in many areas of Computer Science. It can be equivalently stated
as computing a homomorphism R→ΓΓ between two relational structures, e.g. between
two directed graphs. Analyzing its complexity has been a prominent research direction,
especially for the fixed template CSPs where the right side ΓΓ is fixed and the
left side R is unconstrained.\r\n\r\nFar fewer results are known for the hybrid
setting that restricts both sides simultaneously. It assumes that R belongs to
a certain class of relational structures (called a structural restriction in this
paper). We study which structural restrictions are effective, i.e. there exists
a fixed template ΓΓ (from a certain class of languages) for which the problem
is tractable when R is restricted, and NP-hard otherwise. We provide a characterization
for structural restrictions that are closed under inverse homomorphisms. The criterion
is based on the chromatic number of a relational structure defined in this paper;
it generalizes the standard chromatic number of a graph.\r\n\r\nAs our main tool,
we use the algebraic machinery developed for fixed template CSPs. To apply it
to our case, we introduce a new construction called a “lifted language”. We also
give a characterization for structural restrictions corresponding to minor-closed
families of graphs, extend results to certain Valued CSPs (namely conservative
valued languages), and state implications for (valued) CSPs with ordered variables
and for the maximum weight independent set problem on some restricted families
of graphs."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Michal
full_name: Rolinek, Michal
id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
last_name: Rolinek
- first_name: Rustem
full_name: Takhanov, Rustem
last_name: Takhanov
citation:
ama: 'Kolmogorov V, Rolinek M, Takhanov R. Effectiveness of structural restrictions
for hybrid CSPs. In: 26th International Symposium. Vol 9472. Springer Nature;
2015:566-577. doi:10.1007/978-3-662-48971-0_48'
apa: 'Kolmogorov, V., Rolinek, M., & Takhanov, R. (2015). Effectiveness of structural
restrictions for hybrid CSPs. In 26th International Symposium (Vol. 9472,
pp. 566–577). Nagoya, Japan: Springer Nature. https://doi.org/10.1007/978-3-662-48971-0_48'
chicago: Kolmogorov, Vladimir, Michal Rolinek, and Rustem Takhanov. “Effectiveness
of Structural Restrictions for Hybrid CSPs.” In 26th International Symposium,
9472:566–77. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-48971-0_48.
ieee: V. Kolmogorov, M. Rolinek, and R. Takhanov, “Effectiveness of structural restrictions
for hybrid CSPs,” in 26th International Symposium, Nagoya, Japan, 2015,
vol. 9472, pp. 566–577.
ista: 'Kolmogorov V, Rolinek M, Takhanov R. 2015. Effectiveness of structural restrictions
for hybrid CSPs. 26th International Symposium. ISAAC: International Symposium
on Algorithms and Computation, LNCS, vol. 9472, 566–577.'
mla: Kolmogorov, Vladimir, et al. “Effectiveness of Structural Restrictions for
Hybrid CSPs.” 26th International Symposium, vol. 9472, Springer Nature,
2015, pp. 566–77, doi:10.1007/978-3-662-48971-0_48.
short: V. Kolmogorov, M. Rolinek, R. Takhanov, in:, 26th International Symposium,
Springer Nature, 2015, pp. 566–577.
conference:
end_date: 2015-12-11
location: Nagoya, Japan
name: 'ISAAC: International Symposium on Algorithms and Computation'
start_date: 2015-12-09
date_created: 2018-12-11T11:53:10Z
date_published: 2015-12-01T00:00:00Z
date_updated: 2022-02-01T15:12:35Z
day: '01'
department:
- _id: VlKo
doi: 10.1007/978-3-662-48971-0_48
ec_funded: 1
external_id:
arxiv:
- '1504.07067'
intvolume: ' 9472'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1504.07067
month: '12'
oa: 1
oa_version: Preprint
page: 566 - 577
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: 26th International Symposium
publication_identifier:
isbn:
- 978-3-662-48970-3
publication_status: published
publisher: Springer Nature
publist_id: '5519'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Effectiveness of structural restrictions for hybrid CSPs
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 9472
year: '2015'
...
---
_id: '1637'
abstract:
- lang: eng
text: An instance of the Valued Constraint Satisfaction Problem (VCSP) is given
by a finite set of variables, a finite domain of labels, and a sum of functions,
each function depending on a subset of the variables. Each function can take finite
values specifying costs of assignments of labels to its variables or the infinite
value, which indicates an infeasible assignment. The goal is to find an assignment
of labels to the variables that minimizes the sum. We study, assuming that P ≠
NP, how the complexity of this very general problem depends on the set of functions
allowed in the instances, the so-called constraint language. The case when all
allowed functions take values in {0, ∞} corresponds to ordinary CSPs, where one
deals only with the feasibility issue and there is no optimization. This case
is the subject of the Algebraic CSP Dichotomy Conjecture predicting for which
constraint languages CSPs are tractable (i.e. solvable in polynomial time) and
for which NP-hard. The case when all allowed functions take only finite values
corresponds to finite-valued CSP, where the feasibility aspect is trivial and
one deals only with the optimization issue. The complexity of finite-valued CSPs
was fully classified by Thapper and Zivny. An algebraic necessary condition for
tractability of a general-valued CSP with a fixed constraint language was recently
given by Kozik and Ochremiak. As our main result, we prove that if a constraint
language satisfies this algebraic necessary condition, and the feasibility CSP
(i.e. the problem of deciding whether a given instance has a feasible solution)
corresponding to the VCSP with this language is tractable, then the VCSP is tractable.
The algorithm is a simple combination of the assumed algorithm for the feasibility
CSP and the standard LP relaxation. As a corollary, we obtain that a dichotomy
for ordinary CSPs would imply a dichotomy for general-valued CSPs.
alternative_title:
- 56th Annual Symposium on Foundations of Computer Science
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Andrei
full_name: Krokhin, Andrei
last_name: Krokhin
- first_name: Michal
full_name: Rolinek, Michal
id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
last_name: Rolinek
citation:
ama: 'Kolmogorov V, Krokhin A, Rolinek M. The complexity of general-valued CSPs.
In: IEEE; 2015:1246-1258. doi:10.1109/FOCS.2015.80'
apa: 'Kolmogorov, V., Krokhin, A., & Rolinek, M. (2015). The complexity of general-valued
CSPs (pp. 1246–1258). Presented at the FOCS: Foundations of Computer Science,
Berkeley, CA, United States: IEEE. https://doi.org/10.1109/FOCS.2015.80'
chicago: Kolmogorov, Vladimir, Andrei Krokhin, and Michal Rolinek. “The Complexity
of General-Valued CSPs,” 1246–58. IEEE, 2015. https://doi.org/10.1109/FOCS.2015.80.
ieee: 'V. Kolmogorov, A. Krokhin, and M. Rolinek, “The complexity of general-valued
CSPs,” presented at the FOCS: Foundations of Computer Science, Berkeley, CA, United
States, 2015, pp. 1246–1258.'
ista: 'Kolmogorov V, Krokhin A, Rolinek M. 2015. The complexity of general-valued
CSPs. FOCS: Foundations of Computer Science, 56th Annual Symposium on Foundations
of Computer Science, , 1246–1258.'
mla: Kolmogorov, Vladimir, et al. The Complexity of General-Valued CSPs.
IEEE, 2015, pp. 1246–58, doi:10.1109/FOCS.2015.80.
short: V. Kolmogorov, A. Krokhin, M. Rolinek, in:, IEEE, 2015, pp. 1246–1258.
conference:
end_date: 2015-10-20
location: Berkeley, CA, United States
name: 'FOCS: Foundations of Computer Science'
start_date: 2015-10-18
date_created: 2018-12-11T11:53:10Z
date_published: 2015-12-01T00:00:00Z
date_updated: 2023-02-23T12:44:26Z
day: '01'
department:
- _id: VlKo
doi: 10.1109/FOCS.2015.80
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1502.07327
month: '12'
oa: 1
oa_version: Preprint
page: 1246 - 1258
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication_status: published
publisher: IEEE
publist_id: '5518'
quality_controlled: '1'
related_material:
record:
- id: '644'
relation: other
status: public
scopus_import: 1
status: public
title: The complexity of general-valued CSPs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '1638'
abstract:
- lang: eng
text: The mitochondrial respiratory chain, also known as the electron transport
chain (ETC), is crucial to life, and energy production in the form of ATP is the
main mitochondrial function. Three proton-translocating enzymes of the ETC, namely
complexes I, III and IV, generate proton motive force, which in turn drives ATP
synthase (complex V). The atomic structures and basic mechanisms of most respiratory
complexes have previously been established, with the exception of complex I, the
largest complex in the ETC. Recently, the crystal structure of the entire complex
I was solved using a bacterial enzyme. The structure provided novel insights into
the core architecture of the complex, the electron transfer and proton translocation
pathways, as well as the mechanism that couples these two processes.
author:
- first_name: Leonid A
full_name: Sazanov, Leonid A
id: 338D39FE-F248-11E8-B48F-1D18A9856A87
last_name: Sazanov
orcid: 0000-0002-0977-7989
citation:
ama: 'Sazanov LA. A giant molecular proton pump: structure and mechanism of respiratory
complex I. Nature Reviews Molecular Cell Biology. 2015;16(6):375-388. doi:10.1038/nrm3997'
apa: 'Sazanov, L. A. (2015). A giant molecular proton pump: structure and mechanism
of respiratory complex I. Nature Reviews Molecular Cell Biology. Nature
Publishing Group. https://doi.org/10.1038/nrm3997'
chicago: 'Sazanov, Leonid A. “A Giant Molecular Proton Pump: Structure and Mechanism
of Respiratory Complex I.” Nature Reviews Molecular Cell Biology. Nature
Publishing Group, 2015. https://doi.org/10.1038/nrm3997.'
ieee: 'L. A. Sazanov, “A giant molecular proton pump: structure and mechanism of
respiratory complex I,” Nature Reviews Molecular Cell Biology, vol. 16,
no. 6. Nature Publishing Group, pp. 375–388, 2015.'
ista: 'Sazanov LA. 2015. A giant molecular proton pump: structure and mechanism
of respiratory complex I. Nature Reviews Molecular Cell Biology. 16(6), 375–388.'
mla: 'Sazanov, Leonid A. “A Giant Molecular Proton Pump: Structure and Mechanism
of Respiratory Complex I.” Nature Reviews Molecular Cell Biology, vol.
16, no. 6, Nature Publishing Group, 2015, pp. 375–88, doi:10.1038/nrm3997.'
short: L.A. Sazanov, Nature Reviews Molecular Cell Biology 16 (2015) 375–388.
date_created: 2018-12-11T11:53:11Z
date_published: 2015-05-22T00:00:00Z
date_updated: 2021-01-12T06:52:10Z
day: '22'
department:
- _id: LeSa
doi: 10.1038/nrm3997
intvolume: ' 16'
issue: '6'
language:
- iso: eng
month: '05'
oa_version: None
page: 375 - 388
publication: Nature Reviews Molecular Cell Biology
publication_status: published
publisher: Nature Publishing Group
publist_id: '5517'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'A giant molecular proton pump: structure and mechanism of respiratory complex
I'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16
year: '2015'
...
---
_id: '1639'
abstract:
- lang: eng
text: In this paper the optimal transport and the metamorphosis perspectives are
combined. For a pair of given input images geodesic paths in the space of images
are defined as minimizers of a resulting path energy. To this end, the underlying
Riemannian metric measures the rate of transport cost and the rate of viscous
dissipation. Furthermore, the model is capable to deal with strongly varying image
contrast and explicitly allows for sources and sinks in the transport equations
which are incorporated in the metric related to the metamorphosis approach by
Trouvé and Younes. In the non-viscous case with source term existence of geodesic
paths is proven in the space of measures. The proposed model is explored on the
range from merely optimal transport to strongly dissipative dynamics. For this
model a robust and effective variational time discretization of geodesic paths
is proposed. This requires to minimize a discrete path energy consisting of a
sum of consecutive image matching functionals. These functionals are defined on
corresponding pairs of intensity functions and on associated pairwise matching
deformations. Existence of time discrete geodesics is demonstrated. Furthermore,
a finite element implementation is proposed and applied to instructive test cases
and to real images. In the non-viscous case this is compared to the algorithm
proposed by Benamou and Brenier including a discretization of the source term.
Finally, the model is generalized to define discrete weighted barycentres with
applications to textures and objects.
acknowledgement: The authors acknowledge support of the Collaborative Research Centre
1060 funded by the German Science foundation. This work is further supported by
the King Abdullah University for Science and Technology (KAUST) Award No. KUK-I1-007-43
and the EPSRC grant Nr. EP/M00483X/1.
arxiv: 1
author:
- first_name: Jan
full_name: Maas, Jan
id: 4C5696CE-F248-11E8-B48F-1D18A9856A87
last_name: Maas
orcid: 0000-0002-0845-1338
- first_name: Martin
full_name: Rumpf, Martin
last_name: Rumpf
- first_name: Carola
full_name: Schönlieb, Carola
last_name: Schönlieb
- first_name: Stefan
full_name: Simon, Stefan
last_name: Simon
citation:
ama: 'Maas J, Rumpf M, Schönlieb C, Simon S. A generalized model for optimal transport
of images including dissipation and density modulation. ESAIM: Mathematical
Modelling and Numerical Analysis. 2015;49(6):1745-1769. doi:10.1051/m2an/2015043'
apa: 'Maas, J., Rumpf, M., Schönlieb, C., & Simon, S. (2015). A generalized
model for optimal transport of images including dissipation and density modulation.
ESAIM: Mathematical Modelling and Numerical Analysis. EDP Sciences. https://doi.org/10.1051/m2an/2015043'
chicago: 'Maas, Jan, Martin Rumpf, Carola Schönlieb, and Stefan Simon. “A Generalized
Model for Optimal Transport of Images Including Dissipation and Density Modulation.”
ESAIM: Mathematical Modelling and Numerical Analysis. EDP Sciences, 2015.
https://doi.org/10.1051/m2an/2015043.'
ieee: 'J. Maas, M. Rumpf, C. Schönlieb, and S. Simon, “A generalized model for optimal
transport of images including dissipation and density modulation,” ESAIM: Mathematical
Modelling and Numerical Analysis, vol. 49, no. 6. EDP Sciences, pp. 1745–1769,
2015.'
ista: 'Maas J, Rumpf M, Schönlieb C, Simon S. 2015. A generalized model for optimal
transport of images including dissipation and density modulation. ESAIM: Mathematical
Modelling and Numerical Analysis. 49(6), 1745–1769.'
mla: 'Maas, Jan, et al. “A Generalized Model for Optimal Transport of Images Including
Dissipation and Density Modulation.” ESAIM: Mathematical Modelling and Numerical
Analysis, vol. 49, no. 6, EDP Sciences, 2015, pp. 1745–69, doi:10.1051/m2an/2015043.'
short: 'J. Maas, M. Rumpf, C. Schönlieb, S. Simon, ESAIM: Mathematical Modelling
and Numerical Analysis 49 (2015) 1745–1769.'
date_created: 2018-12-11T11:53:11Z
date_published: 2015-11-01T00:00:00Z
date_updated: 2021-01-12T06:52:10Z
day: '01'
department:
- _id: JaMa
doi: 10.1051/m2an/2015043
external_id:
arxiv:
- '1504.01988'
intvolume: ' 49'
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1504.01988
month: '11'
oa: 1
oa_version: Preprint
page: 1745 - 1769
publication: 'ESAIM: Mathematical Modelling and Numerical Analysis'
publication_status: published
publisher: EDP Sciences
publist_id: '5514'
quality_controlled: '1'
scopus_import: 1
status: public
title: A generalized model for optimal transport of images including dissipation and
density modulation
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 49
year: '2015'
...
---
_id: '1640'
abstract:
- lang: eng
text: Auxin and cytokinin are key endogenous regulators of plant development. Although
cytokinin-mediated modulation of auxin distribution is a developmentally crucial
hormonal interaction, its molecular basis is largely unknown. Here we show a direct
regulatory link between cytokinin signalling and the auxin transport machinery
uncovering a mechanistic framework for cytokinin-auxin cross-talk. We show that
the CYTOKININ RESPONSE FACTORS (CRFs), transcription factors downstream of cytokinin
perception, transcriptionally control genes encoding PIN-FORMED (PIN) auxin transporters
at a specific PIN CYTOKININ RESPONSE ELEMENT (PCRE) domain. Removal of this cis-regulatory
element effectively uncouples PIN transcription from the CRF-mediated cytokinin
regulation and attenuates plant cytokinin sensitivity. We propose that CRFs represent
a missing cross-talk component that fine-tunes auxin transport capacity downstream
of cytokinin signalling to control plant development.
acknowledged_ssus:
- _id: Bio
- _id: LifeSc
acknowledgement: This work was supported by the European Research Council Starting
Independent Research grant (ERC-2007-Stg-207362-HCPO to E.B., M.S., C.C.), by the
Ghent University Multidisciplinary Research Partnership ‘Biotechnology for a Sustainable
Economy’ no.01MRB510W, by the Research Foundation—Flanders (grant 3G033711 to J.-A.O.),
by the Austrian Science Fund (FWF01_I1774S) to K.Ö.,E.B., and by the Interuniversity
Attraction Poles Programme (IUAP P7/29 ‘MARS’) initiated by the Belgian Science
Policy Office. I.D.C. and S.V. are post-doctoral fellows of the Research Foundation—Flanders
(FWO). This research was supported by the Scientific Service Units (SSU) of IST-Austria
through resources provided by the Bioimaging Facility (BIF), the Life Science Facility
(LSF).
article_number: '8717'
author:
- first_name: Mária
full_name: Šimášková, Mária
last_name: Šimášková
- first_name: José
full_name: O'Brien, José
last_name: O'Brien
- first_name: Mamoona
full_name: Khan-Djamei, Mamoona
id: 391B5BBC-F248-11E8-B48F-1D18A9856A87
last_name: Khan-Djamei
- first_name: Giel
full_name: Van Noorden, Giel
last_name: Van Noorden
- first_name: Krisztina
full_name: Ötvös, Krisztina
id: 29B901B0-F248-11E8-B48F-1D18A9856A87
last_name: Ötvös
orcid: 0000-0002-5503-4983
- first_name: Anne
full_name: Vieten, Anne
last_name: Vieten
- first_name: Inge
full_name: De Clercq, Inge
last_name: De Clercq
- first_name: Johanna
full_name: Van Haperen, Johanna
last_name: Van Haperen
- first_name: Candela
full_name: Cuesta, Candela
id: 33A3C818-F248-11E8-B48F-1D18A9856A87
last_name: Cuesta
orcid: 0000-0003-1923-2410
- first_name: Klára
full_name: Hoyerová, Klára
last_name: Hoyerová
- first_name: Steffen
full_name: Vanneste, Steffen
last_name: Vanneste
- first_name: Peter
full_name: Marhavy, Peter
id: 3F45B078-F248-11E8-B48F-1D18A9856A87
last_name: Marhavy
orcid: 0000-0001-5227-5741
- first_name: Krzysztof T
full_name: Wabnik, Krzysztof T
id: 4DE369A4-F248-11E8-B48F-1D18A9856A87
last_name: Wabnik
orcid: 0000-0001-7263-0560
- first_name: Frank
full_name: Van Breusegem, Frank
last_name: Van Breusegem
- first_name: Moritz
full_name: Nowack, Moritz
last_name: Nowack
- first_name: Angus
full_name: Murphy, Angus
last_name: Murphy
- first_name: Jiřĺ
full_name: Friml, Jiřĺ
id: 4159519E-F248-11E8-B48F-1D18A9856A87
last_name: Friml
orcid: 0000-0002-8302-7596
- first_name: Dolf
full_name: Weijers, Dolf
last_name: Weijers
- first_name: Tom
full_name: Beeckman, Tom
last_name: Beeckman
- first_name: Eva
full_name: Benková, Eva
id: 38F4F166-F248-11E8-B48F-1D18A9856A87
last_name: Benková
orcid: 0000-0002-8510-9739
citation:
ama: Šimášková M, O’Brien J, Khan-Djamei M, et al. Cytokinin response factors regulate
PIN-FORMED auxin transporters. Nature Communications. 2015;6. doi:10.1038/ncomms9717
apa: Šimášková, M., O’Brien, J., Khan-Djamei, M., Van Noorden, G., Ötvös, K., Vieten,
A., … Benková, E. (2015). Cytokinin response factors regulate PIN-FORMED auxin
transporters. Nature Communications. Nature Publishing Group. https://doi.org/10.1038/ncomms9717
chicago: Šimášková, Mária, José O’Brien, Mamoona Khan-Djamei, Giel Van Noorden,
Krisztina Ötvös, Anne Vieten, Inge De Clercq, et al. “Cytokinin Response Factors
Regulate PIN-FORMED Auxin Transporters.” Nature Communications. Nature
Publishing Group, 2015. https://doi.org/10.1038/ncomms9717.
ieee: M. Šimášková et al., “Cytokinin response factors regulate PIN-FORMED
auxin transporters,” Nature Communications, vol. 6. Nature Publishing Group,
2015.
ista: Šimášková M, O’Brien J, Khan-Djamei M, Van Noorden G, Ötvös K, Vieten A, De
Clercq I, Van Haperen J, Cuesta C, Hoyerová K, Vanneste S, Marhavý P, Wabnik KT,
Van Breusegem F, Nowack M, Murphy A, Friml J, Weijers D, Beeckman T, Benková E.
2015. Cytokinin response factors regulate PIN-FORMED auxin transporters. Nature
Communications. 6, 8717.
mla: Šimášková, Mária, et al. “Cytokinin Response Factors Regulate PIN-FORMED Auxin
Transporters.” Nature Communications, vol. 6, 8717, Nature Publishing Group,
2015, doi:10.1038/ncomms9717.
short: M. Šimášková, J. O’Brien, M. Khan-Djamei, G. Van Noorden, K. Ötvös, A. Vieten,
I. De Clercq, J. Van Haperen, C. Cuesta, K. Hoyerová, S. Vanneste, P. Marhavý,
K.T. Wabnik, F. Van Breusegem, M. Nowack, A. Murphy, J. Friml, D. Weijers, T.
Beeckman, E. Benková, Nature Communications 6 (2015).
date_created: 2018-12-11T11:53:12Z
date_published: 2015-01-01T00:00:00Z
date_updated: 2021-01-12T06:52:11Z
day: '01'
ddc:
- '580'
department:
- _id: EvBe
- _id: JiFr
doi: 10.1038/ncomms9717
ec_funded: 1
file:
- access_level: open_access
checksum: c2c84bca37401435fedf76bad0ba0579
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:18:36Z
date_updated: 2020-07-14T12:45:08Z
file_id: '5358'
file_name: IST-2018-1020-v1+1_Simaskova_et_al_NatCom_2015.pdf
file_size: 1471217
relation: main_file
file_date_updated: 2020-07-14T12:45:08Z
has_accepted_license: '1'
intvolume: ' 6'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
project:
- _id: 253FCA6A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '207362'
name: Hormonal cross-talk in plant organogenesis
- _id: 2542D156-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I 1774-B16
name: Hormone cross-talk drives nutrient dependent plant development
publication: Nature Communications
publication_status: published
publisher: Nature Publishing Group
publist_id: '5513'
pubrep_id: '1020'
quality_controlled: '1'
scopus_import: 1
status: public
title: Cytokinin response factors regulate PIN-FORMED auxin transporters
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 6
year: '2015'
...
---
_id: '1642'
abstract:
- lang: eng
text: The Hanani-Tutte theorem is a classical result proved for the first time in
the 1930s that characterizes planar graphs as graphs that admit a drawing in the
plane in which every pair of edges not sharing a vertex cross an even number of
times. We generalize this result to clustered graphs with two disjoint clusters,
and show that a straightforward extension to flat clustered graphs with three
or more disjoint clusters is not possible. For general clustered graphs we show
a variant of the Hanani-Tutte theorem in the case when each cluster induces a
connected subgraph. Di Battista and Frati proved that clustered planarity of embedded
clustered graphs whose every face is incident to at most five vertices can be
tested in polynomial time. We give a new and short proof of this result, using
the matroid intersection algorithm.
acknowledgement: e research leading to these results has received funding fromthe
People Programme (Marie Curie Actions) of the European Union’s Seventh Framework
Programme(FP7/2007-2013) under REA grant agreement no [291734], and ESF Eurogiga
project GraDR as GAˇCRGIG/11/E023.
article_number: 'P4.24 '
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Jan
full_name: Kynčl, Jan
last_name: Kynčl
- first_name: Igor
full_name: Malinovič, Igor
last_name: Malinovič
- first_name: Dömötör
full_name: Pálvölgyi, Dömötör
last_name: Pálvölgyi
citation:
ama: Fulek R, Kynčl J, Malinovič I, Pálvölgyi D. Clustered planarity testing revisited.
Electronic Journal of Combinatorics. 2015;22(4). doi:10.37236/5002
apa: Fulek, R., Kynčl, J., Malinovič, I., & Pálvölgyi, D. (2015). Clustered
planarity testing revisited. Electronic Journal of Combinatorics. Electronic
Journal of Combinatorics. https://doi.org/10.37236/5002
chicago: Fulek, Radoslav, Jan Kynčl, Igor Malinovič, and Dömötör Pálvölgyi. “Clustered
Planarity Testing Revisited.” Electronic Journal of Combinatorics. Electronic
Journal of Combinatorics, 2015. https://doi.org/10.37236/5002.
ieee: R. Fulek, J. Kynčl, I. Malinovič, and D. Pálvölgyi, “Clustered planarity testing
revisited,” Electronic Journal of Combinatorics, vol. 22, no. 4. Electronic
Journal of Combinatorics, 2015.
ista: Fulek R, Kynčl J, Malinovič I, Pálvölgyi D. 2015. Clustered planarity testing
revisited. Electronic Journal of Combinatorics. 22(4), P4.24.
mla: Fulek, Radoslav, et al. “Clustered Planarity Testing Revisited.” Electronic
Journal of Combinatorics, vol. 22, no. 4, P4.24, Electronic Journal of Combinatorics,
2015, doi:10.37236/5002.
short: R. Fulek, J. Kynčl, I. Malinovič, D. Pálvölgyi, Electronic Journal of Combinatorics
22 (2015).
date_created: 2018-12-11T11:53:12Z
date_published: 2015-11-13T00:00:00Z
date_updated: 2023-02-21T16:03:02Z
day: '13'
ddc:
- '514'
- '516'
department:
- _id: UlWa
doi: 10.37236/5002
ec_funded: 1
external_id:
arxiv:
- '1305.4519'
file:
- access_level: open_access
checksum: 40b5920b49ee736694f59f39588ee206
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:15:03Z
date_updated: 2020-07-14T12:45:08Z
file_id: '5120'
file_name: IST-2016-714-v1+1_5002-15499-3-PB.pdf
file_size: 443655
relation: main_file
file_date_updated: 2020-07-14T12:45:08Z
has_accepted_license: '1'
intvolume: ' 22'
issue: '4'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Electronic Journal of Combinatorics
publication_identifier:
eissn:
- 1077-8926
publication_status: published
publisher: Electronic Journal of Combinatorics
publist_id: '5511'
pubrep_id: '714'
quality_controlled: '1'
related_material:
record:
- id: '10793'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Clustered planarity testing revisited
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 22
year: '2015'
...
---
_id: '1644'
abstract:
- lang: eng
text: Increasing the computational complexity of evaluating a hash function, both
for the honest users as well as for an adversary, is a useful technique employed
for example in password-based cryptographic schemes to impede brute-force attacks,
and also in so-called proofs of work (used in protocols like Bitcoin) to show
that a certain amount of computation was performed by a legitimate user. A natural
approach to adjust the complexity of a hash function is to iterate it c times,
for some parameter c, in the hope that any query to the scheme requires c evaluations
of the underlying hash function. However, results by Dodis et al. (Crypto 2012)
imply that plain iteration falls short of achieving this goal, and designing schemes
which provably have such a desirable property remained an open problem. This paper
formalizes explicitly what it means for a given scheme to amplify the query complexity
of a hash function. In the random oracle model, the goal of a secure query-complexity
amplifier (QCA) scheme is captured as transforming, in the sense of indifferentiability,
a random oracle allowing R queries (for the adversary) into one provably allowing
only r < R queries. Turned around, this means that making r queries to the
scheme requires at least R queries to the actual random oracle. Second, a new
scheme, called collision-free iteration, is proposed and proven to achieve c-fold
QCA for both the honest parties and the adversary, for any fixed parameter c.
alternative_title:
- LNCS
author:
- first_name: Grégory
full_name: Demay, Grégory
last_name: Demay
- first_name: Peter
full_name: Gazi, Peter
id: 3E0BFE38-F248-11E8-B48F-1D18A9856A87
last_name: Gazi
- first_name: Ueli
full_name: Maurer, Ueli
last_name: Maurer
- first_name: Björn
full_name: Tackmann, Björn
last_name: Tackmann
citation:
ama: 'Demay G, Gazi P, Maurer U, Tackmann B. Query-complexity amplification for
random oracles. In: Vol 9063. Springer; 2015:159-180. doi:10.1007/978-3-319-17470-9_10'
apa: 'Demay, G., Gazi, P., Maurer, U., & Tackmann, B. (2015). Query-complexity
amplification for random oracles (Vol. 9063, pp. 159–180). Presented at the ICITS:
International Conference on Information Theoretic Security, Lugano, Switzerland:
Springer. https://doi.org/10.1007/978-3-319-17470-9_10'
chicago: Demay, Grégory, Peter Gazi, Ueli Maurer, and Björn Tackmann. “Query-Complexity
Amplification for Random Oracles,” 9063:159–80. Springer, 2015. https://doi.org/10.1007/978-3-319-17470-9_10.
ieee: 'G. Demay, P. Gazi, U. Maurer, and B. Tackmann, “Query-complexity amplification
for random oracles,” presented at the ICITS: International Conference on Information
Theoretic Security, Lugano, Switzerland, 2015, vol. 9063, pp. 159–180.'
ista: 'Demay G, Gazi P, Maurer U, Tackmann B. 2015. Query-complexity amplification
for random oracles. ICITS: International Conference on Information Theoretic Security,
LNCS, vol. 9063, 159–180.'
mla: Demay, Grégory, et al. Query-Complexity Amplification for Random Oracles.
Vol. 9063, Springer, 2015, pp. 159–80, doi:10.1007/978-3-319-17470-9_10.
short: G. Demay, P. Gazi, U. Maurer, B. Tackmann, in:, Springer, 2015, pp. 159–180.
conference:
end_date: 2015-05-05
location: Lugano, Switzerland
name: 'ICITS: International Conference on Information Theoretic Security'
start_date: 2015-05-02
date_created: 2018-12-11T11:53:13Z
date_published: 2015-01-01T00:00:00Z
date_updated: 2021-01-12T06:52:13Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-319-17470-9_10
ec_funded: 1
intvolume: ' 9063'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://eprint.iacr.org/2015/315
month: '01'
oa: 1
oa_version: Submitted Version
page: 159 - 180
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication_status: published
publisher: Springer
publist_id: '5507'
quality_controlled: '1'
scopus_import: 1
status: public
title: Query-complexity amplification for random oracles
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9063
year: '2015'
...
---
_id: '1645'
abstract:
- lang: eng
text: Secret-key constructions are often proved secure in a model where one or more
underlying components are replaced by an idealized oracle accessible to the attacker.
This model gives rise to information-theoretic security analyses, and several
advances have been made in this area over the last few years. This paper provides
a systematic overview of what is achievable in this model, and how existing works
fit into this view.
article_number: '7133163'
author:
- first_name: Peter
full_name: Gazi, Peter
id: 3E0BFE38-F248-11E8-B48F-1D18A9856A87
last_name: Gazi
- first_name: Stefano
full_name: Tessaro, Stefano
last_name: Tessaro
citation:
ama: 'Gazi P, Tessaro S. Secret-key cryptography from ideal primitives: A systematic
verview. In: 2015 IEEE Information Theory Workshop. IEEE; 2015. doi:10.1109/ITW.2015.7133163'
apa: 'Gazi, P., & Tessaro, S. (2015). Secret-key cryptography from ideal primitives:
A systematic verview. In 2015 IEEE Information Theory Workshop. Jerusalem,
Israel: IEEE. https://doi.org/10.1109/ITW.2015.7133163'
chicago: 'Gazi, Peter, and Stefano Tessaro. “Secret-Key Cryptography from Ideal
Primitives: A Systematic Verview.” In 2015 IEEE Information Theory Workshop.
IEEE, 2015. https://doi.org/10.1109/ITW.2015.7133163.'
ieee: 'P. Gazi and S. Tessaro, “Secret-key cryptography from ideal primitives: A
systematic verview,” in 2015 IEEE Information Theory Workshop, Jerusalem,
Israel, 2015.'
ista: 'Gazi P, Tessaro S. 2015. Secret-key cryptography from ideal primitives: A
systematic verview. 2015 IEEE Information Theory Workshop. ITW 2015: IEEE Information
Theory Workshop, 7133163.'
mla: 'Gazi, Peter, and Stefano Tessaro. “Secret-Key Cryptography from Ideal Primitives:
A Systematic Verview.” 2015 IEEE Information Theory Workshop, 7133163,
IEEE, 2015, doi:10.1109/ITW.2015.7133163.'
short: P. Gazi, S. Tessaro, in:, 2015 IEEE Information Theory Workshop, IEEE, 2015.
conference:
end_date: 2015-05-01
location: Jerusalem, Israel
name: 'ITW 2015: IEEE Information Theory Workshop'
start_date: 2015-04-26
date_created: 2018-12-11T11:53:13Z
date_published: 2015-06-24T00:00:00Z
date_updated: 2021-01-12T06:52:13Z
day: '24'
department:
- _id: KrPi
doi: 10.1109/ITW.2015.7133163
ec_funded: 1
language:
- iso: eng
month: '06'
oa_version: None
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication: 2015 IEEE Information Theory Workshop
publication_status: published
publisher: IEEE
publist_id: '5506'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'Secret-key cryptography from ideal primitives: A systematic verview'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '1646'
abstract:
- lang: eng
text: 'A pseudorandom function (PRF) is a keyed function F : K × X → Y where, for
a random key k ∈ K, the function F(k, ·) is indistinguishable from a uniformly
random function, given black-box access. A key-homomorphic PRF has the additional
feature that for any keys k, k'' and any input x, we have F(k+k'', x) = F(k, x)⊕F(k'',
x) for some group operations +,⊕ on K and Y, respectively. A constrained PRF for
a family of setsS ⊆ P(X) has the property that, given any key k and set S ∈ S,
one can efficiently compute a “constrained” key kS that enables evaluation of
F(k, x) on all inputs x ∈ S, while the values F(k, x) for x /∈ S remain pseudorandom
even given kS. In this paper we construct PRFs that are simultaneously constrained
and key homomorphic, where the homomorphic property holds even for constrained
keys. We first show that the multilinear map-based bit-fixing and circuit-constrained
PRFs of Boneh and Waters (Asiacrypt 2013) can be modified to also be keyhomomorphic.
We then show that the LWE-based key-homomorphic PRFs of Banerjee and Peikert (Crypto
2014) are essentially already prefix-constrained PRFs, using a (non-obvious) definition
of constrained keys and associated group operation. Moreover, the constrained
keys themselves are pseudorandom, and the constraining and evaluation functions
can all be computed in low depth. As an application of key-homomorphic constrained
PRFs,we construct a proxy re-encryption schemewith fine-grained access control.
This scheme allows storing encrypted data on an untrusted server, where each file
can be encrypted relative to some attributes, so that only parties whose constrained
keys match the attributes can decrypt. Moreover, the server can re-key (arbitrary
subsets of) the ciphertexts without learning anything about the plaintexts, thus
permitting efficient and finegrained revocation.'
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Abishek
full_name: Banerjee, Abishek
last_name: Banerjee
- first_name: Georg
full_name: Fuchsbauer, Georg
id: 46B4C3EE-F248-11E8-B48F-1D18A9856A87
last_name: Fuchsbauer
- first_name: Chris
full_name: Peikert, Chris
last_name: Peikert
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Sophie
full_name: Stevens, Sophie
last_name: Stevens
citation:
ama: 'Banerjee A, Fuchsbauer G, Peikert C, Pietrzak KZ, Stevens S. Key-homomorphic
constrained pseudorandom functions. In: 12th Theory of Cryptography Conference.
Vol 9015. Springer Nature; 2015:31-60. doi:10.1007/978-3-662-46497-7_2'
apa: 'Banerjee, A., Fuchsbauer, G., Peikert, C., Pietrzak, K. Z., & Stevens,
S. (2015). Key-homomorphic constrained pseudorandom functions. In 12th Theory
of Cryptography Conference (Vol. 9015, pp. 31–60). Warsaw, Poland: Springer
Nature. https://doi.org/10.1007/978-3-662-46497-7_2'
chicago: Banerjee, Abishek, Georg Fuchsbauer, Chris Peikert, Krzysztof Z Pietrzak,
and Sophie Stevens. “Key-Homomorphic Constrained Pseudorandom Functions.” In 12th
Theory of Cryptography Conference, 9015:31–60. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-46497-7_2.
ieee: A. Banerjee, G. Fuchsbauer, C. Peikert, K. Z. Pietrzak, and S. Stevens, “Key-homomorphic
constrained pseudorandom functions,” in 12th Theory of Cryptography Conference,
Warsaw, Poland, 2015, vol. 9015, pp. 31–60.
ista: 'Banerjee A, Fuchsbauer G, Peikert C, Pietrzak KZ, Stevens S. 2015. Key-homomorphic
constrained pseudorandom functions. 12th Theory of Cryptography Conference. TCC:
Theory of Cryptography Conference, LNCS, vol. 9015, 31–60.'
mla: Banerjee, Abishek, et al. “Key-Homomorphic Constrained Pseudorandom Functions.”
12th Theory of Cryptography Conference, vol. 9015, Springer Nature, 2015,
pp. 31–60, doi:10.1007/978-3-662-46497-7_2.
short: A. Banerjee, G. Fuchsbauer, C. Peikert, K.Z. Pietrzak, S. Stevens, in:, 12th
Theory of Cryptography Conference, Springer Nature, 2015, pp. 31–60.
conference:
end_date: 2015-03-25
location: Warsaw, Poland
name: 'TCC: Theory of Cryptography Conference'
start_date: 2015-03-23
date_created: 2018-12-11T11:53:14Z
date_published: 2015-03-01T00:00:00Z
date_updated: 2022-02-03T08:41:46Z
day: '01'
ddc:
- '000'
- '004'
department:
- _id: KrPi
doi: 10.1007/978-3-662-46497-7_2
ec_funded: 1
file:
- access_level: open_access
checksum: 3c5093bda5783c89beaacabf1aa0e60e
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:15:17Z
date_updated: 2020-07-14T12:45:08Z
file_id: '5136'
file_name: IST-2016-679-v1+1_180.pdf
file_size: 450665
relation: main_file
file_date_updated: 2020-07-14T12:45:08Z
has_accepted_license: '1'
intvolume: ' 9015'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2015/180
month: '03'
oa: 1
oa_version: Submitted Version
page: 31 - 60
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication: 12th Theory of Cryptography Conference
publication_identifier:
isbn:
- 978-3-662-46496-0
publication_status: published
publisher: Springer Nature
publist_id: '5505'
pubrep_id: '679'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Key-homomorphic constrained pseudorandom functions
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 9015
year: '2015'
...
---
_id: '1647'
abstract:
- lang: eng
text: Round-optimal blind signatures are notoriously hard to construct in the standard
model, especially in the malicious-signer model, where blindness must hold under
adversarially chosen keys. This is substantiated by several impossibility results.
The only construction that can be termed theoretically efficient, by Garg and
Gupta (Eurocrypt’14), requires complexity leveraging, inducing an exponential
security loss. We present a construction of practically efficient round-optimal
blind signatures in the standard model. It is conceptually simple and builds on
the recent structure-preserving signatures on equivalence classes (SPSEQ) from
Asiacrypt’14. While the traditional notion of blindness follows from standard
assumptions, we prove blindness under adversarially chosen keys under an interactive
variant of DDH. However, we neither require non-uniform assumptions nor complexity
leveraging. We then show how to extend our construction to partially blind signatures
and to blind signatures on message vectors, which yield a construction of one-show
anonymous credentials à la “anonymous credentials light” (CCS’13) in the standard
model. Furthermore, we give the first SPS-EQ construction under noninteractive
assumptions and show how SPS-EQ schemes imply conventional structure-preserving
signatures, which allows us to apply optimality results for the latter to SPS-EQ.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Georg
full_name: Fuchsbauer, Georg
id: 46B4C3EE-F248-11E8-B48F-1D18A9856A87
last_name: Fuchsbauer
- first_name: Christian
full_name: Hanser, Christian
last_name: Hanser
- first_name: Daniel
full_name: Slamanig, Daniel
last_name: Slamanig
citation:
ama: 'Fuchsbauer G, Hanser C, Slamanig D. Practical round-optimal blind signatures
in the standard model. In: Vol 9216. Springer; 2015:233-253. doi:10.1007/978-3-662-48000-7_12'
apa: 'Fuchsbauer, G., Hanser, C., & Slamanig, D. (2015). Practical round-optimal
blind signatures in the standard model (Vol. 9216, pp. 233–253). Presented at
the CRYPTO: International Cryptology Conference, Santa Barbara, CA, United States:
Springer. https://doi.org/10.1007/978-3-662-48000-7_12'
chicago: Fuchsbauer, Georg, Christian Hanser, and Daniel Slamanig. “Practical Round-Optimal
Blind Signatures in the Standard Model,” 9216:233–53. Springer, 2015. https://doi.org/10.1007/978-3-662-48000-7_12.
ieee: 'G. Fuchsbauer, C. Hanser, and D. Slamanig, “Practical round-optimal blind
signatures in the standard model,” presented at the CRYPTO: International Cryptology
Conference, Santa Barbara, CA, United States, 2015, vol. 9216, pp. 233–253.'
ista: 'Fuchsbauer G, Hanser C, Slamanig D. 2015. Practical round-optimal blind signatures
in the standard model. CRYPTO: International Cryptology Conference, LNCS, vol.
9216, 233–253.'
mla: Fuchsbauer, Georg, et al. Practical Round-Optimal Blind Signatures in the
Standard Model. Vol. 9216, Springer, 2015, pp. 233–53, doi:10.1007/978-3-662-48000-7_12.
short: G. Fuchsbauer, C. Hanser, D. Slamanig, in:, Springer, 2015, pp. 233–253.
conference:
end_date: 2015-08-20
location: Santa Barbara, CA, United States
name: 'CRYPTO: International Cryptology Conference'
start_date: 2015-08-16
date_created: 2018-12-11T11:53:14Z
date_published: 2015-08-01T00:00:00Z
date_updated: 2023-02-21T16:44:51Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-662-48000-7_12
ec_funded: 1
intvolume: ' 9216'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2015/626.pdf
month: '08'
oa: 1
oa_version: Submitted Version
page: 233 - 253
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication_status: published
publisher: Springer
publist_id: '5503'
quality_controlled: '1'
related_material:
record:
- id: '1225'
relation: later_version
status: public
scopus_import: 1
status: public
title: Practical round-optimal blind signatures in the standard model
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9216
year: '2015'
...