---
_id: '8182'
abstract:
- lang: eng
text: "Suppose that $n\\neq p^k$ and $n\\neq 2p^k$ for all $k$ and all primes $p$.
We prove that for any Hausdorff compactum $X$ with a free action of the symmetric
group $\\mathfrak S_n$ there exists an $\\mathfrak S_n$-equivariant map $X \\to\r\n{\\mathbb
R}^n$ whose image avoids the diagonal $\\{(x,x\\dots,x)\\in {\\mathbb R}^n|x\\in
{\\mathbb R}\\}$.\r\n Previously, the special cases of this statement for certain
$X$ were usually proved using the equivartiant obstruction theory. Such calculations
are difficult and may become infeasible past the first (primary) obstruction.
We\r\ntake a different approach which allows us to prove the vanishing of all
obstructions simultaneously. The essential step in the proof is classifying the
possible degrees of $\\mathfrak S_n$-equivariant maps from the boundary\r\n$\\partial\\Delta^{n-1}$
of $(n-1)$-simplex to itself. Existence of equivariant maps between spaces is
important for many questions arising from discrete mathematics and geometry, such
as Kneser's conjecture, the Square Peg conjecture, the Splitting Necklace problem,
and the Topological Tverberg conjecture, etc. We demonstrate the utility of our
result applying it to one such question, a specific instance of envy-free division
problem."
article_number: '1910.12628'
article_processing_charge: No
author:
- first_name: Sergey
full_name: Avvakumov, Sergey
id: 3827DAC8-F248-11E8-B48F-1D18A9856A87
last_name: Avvakumov
- first_name: Sergey
full_name: Kudrya, Sergey
id: ecf01965-d252-11ea-95a5-8ada5f6c6a67
last_name: Kudrya
citation:
ama: Avvakumov S, Kudrya S. Vanishing of all equivariant obstructions and the mapping
degree. arXiv.
apa: Avvakumov, S., & Kudrya, S. (n.d.). Vanishing of all equivariant obstructions
and the mapping degree. arXiv. arXiv.
chicago: Avvakumov, Sergey, and Sergey Kudrya. “Vanishing of All Equivariant Obstructions
and the Mapping Degree.” ArXiv. arXiv, n.d.
ieee: S. Avvakumov and S. Kudrya, “Vanishing of all equivariant obstructions and
the mapping degree,” arXiv. arXiv.
ista: Avvakumov S, Kudrya S. Vanishing of all equivariant obstructions and the mapping
degree. arXiv, 1910.12628.
mla: Avvakumov, Sergey, and Sergey Kudrya. “Vanishing of All Equivariant Obstructions
and the Mapping Degree.” ArXiv, 1910.12628, arXiv.
short: S. Avvakumov, S. Kudrya, ArXiv (n.d.).
date_created: 2020-07-30T10:45:08Z
date_published: 2019-10-28T00:00:00Z
date_updated: 2023-09-07T13:12:17Z
day: '28'
department:
- _id: UlWa
external_id:
arxiv:
- '1910.12628'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1910.12628
month: '10'
oa: 1
oa_version: Preprint
project:
- _id: 26611F5C-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P31312
name: Algorithms for Embeddings and Homotopy Theory
publication: arXiv
publication_status: submitted
publisher: arXiv
related_material:
record:
- id: '11446'
relation: later_version
status: public
- id: '8156'
relation: dissertation_contains
status: public
status: public
title: Vanishing of all equivariant obstructions and the mapping degree
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2019'
...
---
_id: '8185'
abstract:
- lang: eng
text: "In this paper we study envy-free division problems. The classical approach
to some of such problems, used by David Gale, reduces to considering continuous
maps of a simplex to itself and finding sufficient conditions when this map hits
the center of the simplex. The mere continuity is not sufficient for such a conclusion,
the usual assumption (for example, in the Knaster--Kuratowski--Mazurkiewicz and
the Gale theorem) is a certain boundary condition.\r\n We follow Erel Segal-Halevi,
Fr\\'ed\\'eric Meunier, and Shira Zerbib, and replace the boundary condition by
another assumption, which has the economic meaning of possibility for a player
to prefer an empty part in the segment\r\npartition problem. We solve the problem
positively when $n$, the number of players that divide the segment, is a prime
power, and we provide counterexamples for every $n$ which is not a prime power.
We also provide counterexamples relevant to a wider class of fair or envy-free
partition problems when $n$ is odd and not a prime power."
article_number: '1907.11183'
article_processing_charge: No
author:
- first_name: Sergey
full_name: Avvakumov, Sergey
id: 3827DAC8-F248-11E8-B48F-1D18A9856A87
last_name: Avvakumov
- first_name: Roman
full_name: Karasev, Roman
last_name: Karasev
citation:
ama: Avvakumov S, Karasev R. Envy-free division using mapping degree. arXiv.
doi:10.48550/arXiv.1907.11183
apa: Avvakumov, S., & Karasev, R. (n.d.). Envy-free division using mapping degree.
arXiv. https://doi.org/10.48550/arXiv.1907.11183
chicago: Avvakumov, Sergey, and Roman Karasev. “Envy-Free Division Using Mapping
Degree.” ArXiv, n.d. https://doi.org/10.48550/arXiv.1907.11183.
ieee: S. Avvakumov and R. Karasev, “Envy-free division using mapping degree,” arXiv.
.
ista: Avvakumov S, Karasev R. Envy-free division using mapping degree. arXiv, 1907.11183.
mla: Avvakumov, Sergey, and Roman Karasev. “Envy-Free Division Using Mapping Degree.”
ArXiv, 1907.11183, doi:10.48550/arXiv.1907.11183.
short: S. Avvakumov, R. Karasev, ArXiv (n.d.).
date_created: 2020-07-30T10:45:51Z
date_published: 2019-07-25T00:00:00Z
date_updated: 2023-09-07T13:12:17Z
day: '25'
department:
- _id: UlWa
doi: 10.48550/arXiv.1907.11183
external_id:
arxiv:
- '1907.11183'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1907.11183
month: '07'
oa: 1
oa_version: Preprint
project:
- _id: 26611F5C-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P31312
name: Algorithms for Embeddings and Homotopy Theory
publication: arXiv
publication_status: submitted
related_material:
link:
- relation: later_version
url: https://doi.org/10.1112/mtk.12059
record:
- id: '8156'
relation: dissertation_contains
status: public
status: public
title: Envy-free division using mapping degree
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2019'
...
---
_id: '7524'
abstract:
- lang: eng
text: "We prove a lower bound for the free energy (per unit volume) of the two-dimensional
Bose gas in the thermodynamic limit. We show that the free energy at density $\\rho$
and inverse temperature $\\beta$ differs from the one of the non-interacting system
by the correction term $4 \\pi \\rho^2 |\\ln a^2 \\rho|^{-1} (2 - [1 - \\beta_{\\mathrm{c}}/\\beta]_+^2)$.
Here $a$ is the scattering length of the interaction potential, $[\\cdot]_+ =
\\max\\{ 0, \\cdot \\}$ and $\\beta_{\\mathrm{c}}$ is the inverse Berezinskii--Kosterlitz--Thouless
critical temperature for superfluidity. The result is valid in the dilute limit\r\n$a^2\\rho
\\ll 1$ and if $\\beta \\rho \\gtrsim 1$."
article_processing_charge: No
author:
- first_name: Andreas
full_name: Deuchert, Andreas
id: 4DA65CD0-F248-11E8-B48F-1D18A9856A87
last_name: Deuchert
orcid: 0000-0003-3146-6746
- first_name: Simon
full_name: Mayer, Simon
id: 30C4630A-F248-11E8-B48F-1D18A9856A87
last_name: Mayer
- first_name: Robert
full_name: Seiringer, Robert
id: 4AFD0470-F248-11E8-B48F-1D18A9856A87
last_name: Seiringer
orcid: 0000-0002-6781-0521
citation:
ama: Deuchert A, Mayer S, Seiringer R. The free energy of the two-dimensional dilute
Bose gas. I. Lower bound. arXiv:191003372.
apa: Deuchert, A., Mayer, S., & Seiringer, R. (n.d.). The free energy of the
two-dimensional dilute Bose gas. I. Lower bound. arXiv:1910.03372. ArXiv.
chicago: Deuchert, Andreas, Simon Mayer, and Robert Seiringer. “The Free Energy
of the Two-Dimensional Dilute Bose Gas. I. Lower Bound.” ArXiv:1910.03372.
ArXiv, n.d.
ieee: A. Deuchert, S. Mayer, and R. Seiringer, “The free energy of the two-dimensional
dilute Bose gas. I. Lower bound,” arXiv:1910.03372. ArXiv.
ista: Deuchert A, Mayer S, Seiringer R. The free energy of the two-dimensional dilute
Bose gas. I. Lower bound. arXiv:1910.03372, .
mla: Deuchert, Andreas, et al. “The Free Energy of the Two-Dimensional Dilute Bose
Gas. I. Lower Bound.” ArXiv:1910.03372, ArXiv.
short: A. Deuchert, S. Mayer, R. Seiringer, ArXiv:1910.03372 (n.d.).
date_created: 2020-02-26T08:46:40Z
date_published: 2019-10-08T00:00:00Z
date_updated: 2023-09-07T13:12:41Z
day: '08'
department:
- _id: RoSe
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1910.03372
month: '10'
oa: 1
oa_version: Preprint
page: '61'
project:
- _id: 25C6DC12-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '694227'
name: Analysis of quantum many-body systems
publication: arXiv:1910.03372
publication_status: draft
publisher: ArXiv
related_material:
record:
- id: '7790'
relation: later_version
status: public
- id: '7514'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: The free energy of the two-dimensional dilute Bose gas. I. Lower bound
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2019'
...
---
_id: '6608'
abstract:
- lang: eng
text: We use the canonical bases produced by the tri-partition algorithm in (Edelsbrunner
and Ölsböck, 2018) to open and close holes in a polyhedral complex, K. In a concrete
application, we consider the Delaunay mosaic of a finite set, we let K be an Alpha
complex, and we use the persistence diagram of the distance function to guide
the hole opening and closing operations. The dependences between the holes define
a partial order on the cells in K that characterizes what can and what cannot
be constructed using the operations. The relations in this partial order reveal
structural information about the underlying filtration of complexes beyond what
is expressed by the persistence diagram.
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
- first_name: Katharina
full_name: Ölsböck, Katharina
id: 4D4AA390-F248-11E8-B48F-1D18A9856A87
last_name: Ölsböck
orcid: 0000-0002-4672-8297
citation:
ama: Edelsbrunner H, Ölsböck K. Holes and dependences in an ordered complex. Computer
Aided Geometric Design. 2019;73:1-15. doi:10.1016/j.cagd.2019.06.003
apa: Edelsbrunner, H., & Ölsböck, K. (2019). Holes and dependences in an ordered
complex. Computer Aided Geometric Design. Elsevier. https://doi.org/10.1016/j.cagd.2019.06.003
chicago: Edelsbrunner, Herbert, and Katharina Ölsböck. “Holes and Dependences in
an Ordered Complex.” Computer Aided Geometric Design. Elsevier, 2019. https://doi.org/10.1016/j.cagd.2019.06.003.
ieee: H. Edelsbrunner and K. Ölsböck, “Holes and dependences in an ordered complex,”
Computer Aided Geometric Design, vol. 73. Elsevier, pp. 1–15, 2019.
ista: Edelsbrunner H, Ölsböck K. 2019. Holes and dependences in an ordered complex.
Computer Aided Geometric Design. 73, 1–15.
mla: Edelsbrunner, Herbert, and Katharina Ölsböck. “Holes and Dependences in an
Ordered Complex.” Computer Aided Geometric Design, vol. 73, Elsevier, 2019,
pp. 1–15, doi:10.1016/j.cagd.2019.06.003.
short: H. Edelsbrunner, K. Ölsböck, Computer Aided Geometric Design 73 (2019) 1–15.
date_created: 2019-07-07T21:59:20Z
date_published: 2019-08-01T00:00:00Z
date_updated: 2023-09-07T13:15:29Z
day: '01'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1016/j.cagd.2019.06.003
ec_funded: 1
external_id:
isi:
- '000485207800001'
file:
- access_level: open_access
checksum: 7c99be505dc7533257d42eb1830cef04
content_type: application/pdf
creator: kschuh
date_created: 2019-07-08T15:24:26Z
date_updated: 2020-07-14T12:47:34Z
file_id: '6624'
file_name: Elsevier_2019_Edelsbrunner.pdf
file_size: 2665013
relation: main_file
file_date_updated: 2020-07-14T12:47:34Z
has_accepted_license: '1'
intvolume: ' 73'
isi: 1
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
page: 1-15
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication: Computer Aided Geometric Design
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
record:
- id: '7460'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Holes and dependences in an ordered complex
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
(CC BY-NC-ND 4.0)
short: CC BY-NC-ND (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 73
year: '2019'
...
---
_id: '6677'
abstract:
- lang: eng
text: "The Fiat-Shamir heuristic transforms a public-coin interactive proof into
a non-interactive argument, by replacing the verifier with a cryptographic hash
function that is applied to the protocol’s transcript. Constructing hash functions
for which this transformation is sound is a central and long-standing open question
in cryptography.\r\n\r\nWe show that solving the END−OF−METERED−LINE problem is
no easier than breaking the soundness of the Fiat-Shamir transformation when applied
to the sumcheck protocol. In particular, if the transformed protocol is sound,
then any hard problem in #P gives rise to a hard distribution in the class CLS,
which is contained in PPAD. Our result opens up the possibility of sampling moderately-sized
games for which it is hard to find a Nash equilibrium, by reducing the inversion
of appropriately chosen one-way functions to #SAT.\r\n\r\nOur main technical contribution
is a stateful incrementally verifiable procedure that, given a SAT instance over
n variables, counts the number of satisfying assignments. This is accomplished
via an exponential sequence of small steps, each computable in time poly(n). Incremental
verifiability means that each intermediate state includes a sumcheck-based proof
of its correctness, and the proof can be updated and verified in time poly(n)."
article_processing_charge: No
author:
- first_name: Arka Rai
full_name: Choudhuri, Arka Rai
last_name: Choudhuri
- first_name: Pavel
full_name: Hubáček, Pavel
last_name: Hubáček
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
- 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: Alon
full_name: Rosen, Alon
last_name: Rosen
- first_name: Guy N.
full_name: Rothblum, Guy N.
last_name: Rothblum
citation:
ama: 'Choudhuri AR, Hubáček P, Kamath Hosdurg C, Pietrzak KZ, Rosen A, Rothblum
GN. Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. In: Proceedings
of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019.
ACM Press; 2019:1103-1114. doi:10.1145/3313276.3316400'
apa: 'Choudhuri, A. R., Hubáček, P., Kamath Hosdurg, C., Pietrzak, K. Z., Rosen,
A., & Rothblum, G. N. (2019). Finding a Nash equilibrium is no easier than
breaking Fiat-Shamir. In Proceedings of the 51st Annual ACM SIGACT Symposium
on Theory of Computing - STOC 2019 (pp. 1103–1114). Phoenix, AZ, United States:
ACM Press. https://doi.org/10.1145/3313276.3316400'
chicago: Choudhuri, Arka Rai, Pavel Hubáček, Chethan Kamath Hosdurg, Krzysztof Z
Pietrzak, Alon Rosen, and Guy N. Rothblum. “Finding a Nash Equilibrium Is No Easier
than Breaking Fiat-Shamir.” In Proceedings of the 51st Annual ACM SIGACT Symposium
on Theory of Computing - STOC 2019, 1103–14. ACM Press, 2019. https://doi.org/10.1145/3313276.3316400.
ieee: A. R. Choudhuri, P. Hubáček, C. Kamath Hosdurg, K. Z. Pietrzak, A. Rosen,
and G. N. Rothblum, “Finding a Nash equilibrium is no easier than breaking Fiat-Shamir,”
in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
- STOC 2019, Phoenix, AZ, United States, 2019, pp. 1103–1114.
ista: 'Choudhuri AR, Hubáček P, Kamath Hosdurg C, Pietrzak KZ, Rosen A, Rothblum
GN. 2019. Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. Proceedings
of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019. STOC:
Symposium on Theory of Computing, 1103–1114.'
mla: Choudhuri, Arka Rai, et al. “Finding a Nash Equilibrium Is No Easier than Breaking
Fiat-Shamir.” Proceedings of the 51st Annual ACM SIGACT Symposium on Theory
of Computing - STOC 2019, ACM Press, 2019, pp. 1103–14, doi:10.1145/3313276.3316400.
short: A.R. Choudhuri, P. Hubáček, C. Kamath Hosdurg, K.Z. Pietrzak, A. Rosen, G.N.
Rothblum, in:, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of
Computing - STOC 2019, ACM Press, 2019, pp. 1103–1114.
conference:
end_date: 2019-06-26
location: Phoenix, AZ, United States
name: 'STOC: Symposium on Theory of Computing'
start_date: 2019-06-23
date_created: 2019-07-24T09:20:53Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2023-09-07T13:15:55Z
day: '01'
department:
- _id: KrPi
doi: 10.1145/3313276.3316400
ec_funded: 1
external_id:
isi:
- '000523199100100'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2019/549
month: '06'
oa: 1
oa_version: Preprint
page: 1103-1114
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing -
STOC 2019
publication_identifier:
isbn:
- '9781450367059'
publication_status: published
publisher: ACM Press
quality_controlled: '1'
related_material:
record:
- id: '7896'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2019'
...