17 citations · 24 across the 5 of their papers we have counts for
8 papers
Randomization Helps in Online Graph Exploration: Breaking the Deterministic Lower Bound on Cycles
Júlia Baligács, Jan Hązła, Lena Volk
In online graph exploration, introduced by Kalyanasundaram and Pruhs (1994), an agent must visit all vertices of an initially unknown weighted graph and return to its starting posi…
Geometric opinion exchange polarizes in every dimension
Abdou Majeed Alidou, Júlia Baligács, Jan Hązła
A recent line of work studies models of opinion exchange where agent opinions about topics are tracked simultaneously. The opinions are represented as vectors on the unit $(d-1…
Inevitability of Polarization in Geometric Opinion Exchange
Abdou Majeed Alidou, Júlia Baligács, Max Hahn-Klimroth +3
Polarization and unexpected correlations between opinions on diverse topics (including in politics, culture and consumer choices) are an object of sustained attention. However, num…
A Geometric Model of Opinion Polarization
Jan Hązła, Yan Jin, Elchanan Mossel +1
We introduce a simple, geometric model of opinion polarization. It is a model of political persuasion, as well as marketing and advertising, utilizing social values. It focuses on…
Reasoning in Bayesian Opinion Exchange Networks Is PSPACE-Hard
Jan Hązła, Ali Jadbabaie, Elchanan Mossel +1
We study the Bayesian model of opinion exchange of fully rational agents arranged on a network. In this model, the agents receive private signals that are indicative of an unkown s…
Bayesian Decision Making in Groups is Hard
Jan Hązła, Ali Jadbabaie, Elchanan Mossel +1
We study the computations that Bayesian agents undertake when exchanging opinions over a network. The agents act repeatedly on their private information and take myopic actions tha…
Forbidden Subgraph Bounds for Parallel Repetition and the Density Hales-Jewett Theorem
Jan Hązła, Thomas Holenstein, Anup Rao
We study a special kind of bounds (so called forbidden subgraph bounds, cf. Feige, Verbitsky '02) for parallel repetition of multi-prover games. First, we show that forbidden subgr…
Upper Tail Estimates with Combinatorial Proofs
Jan Hązła, Thomas Holenstein
We study generalisations of a simple, combinatorial proof of a Chernoff bound similar to the one by Impagliazzo and Kabanets (RANDOM, 2010). In particular, we prove a randomized ve…