Rathod, Abhishek

We study the problem of finding a minimum homology basis, that is, a shortest set of cycles that generates the $1$-dimensional homology classes with $\mathbb{Z}_2$ coefficients in a given simplicial complex $K$. This problem has been extensively studied in the last few years. For general complexes, the current best deterministic algorithm, by Dey e...

Kretschmer, William

A leading proposal for verifying near-term quantum supremacy experiments on noisy random quantum circuits is linear cross-entropy benchmarking. For a quantum circuit $C$ on $n$ qubits and a sample $z \in \{0,1\}^n$, the benchmark involves computing $|\langle z|C|0^n \rangle|^2$, i.e. the probability of measuring $z$ from the output distribution of ...

Wang, Yishu Mary, Arnaud Sagot, Marie-France Sinaimeri, Blerina

When a problem has more than one solution, it is often important, depending on the underlying context, to enumerate (i.e., to list) them all. Even when the enumeration can be done in polynomial delay, that is, spending no more than polynomial time to go from one solution to the next, this can be costly as the number of solutions themselves may be h...

Munro, J. Ian Nicholson, Patrick K. Benkner, Louisa Seelbach Wild, Sebastian

We present a new universal source code for distributions of unlabeled binary and ordinal trees that achieves optimal compression to within lower order terms for all tree sources covered by existing universal codes. At the same time, it supports answering many navigational queries on the compressed representation in constant time on the word-RAM; th...

Grosshans, Nathan

Hamoudi, Yassine

Kori, Mayuko Hasuo, Ichiro Katsumata, Shin-ya

The coincidence between initial algebras (IAs) and final coalgebras (FCs) is a phenomenon that underpins various important results in theoretical computer science. In this paper, we identify a general fibrational condition for the IA-FC coincidence, namely in the fiber over an initial algebra in the base category. Identifying (co)algebras in a fibe...

Vilmart, Renaud

Graphical calculi such as the ZH-calculus are powerful tools in the study and analysis of quantum processes, with links to other models of quantum computation such as quantum circuits, measurement-based computing, etc. A somewhat compact but systematic way to describe a quantum process is through the use of quantum multiple-valued decision diagrams...

Bouyer, Patricia Oualhadj, Youssouf Randour, Mickael Vandenhove, Pierre

We study stochastic zero-sum games on graphs, which are prevalent tools to model decision-making in presence of an antagonistic opponent in a random environment. In this setting, an important question is the one of strategy complexity: what kinds of strategies are sufficient or required to play optimally (e.g., randomization or memory requirements)...

Branciard, Cyril Mhalla, Mehdi Perdrix, Simon