:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Author:	Zimand, Marius
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2412.03392
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Computable one-way functions on the reals
by: Barmpalias, George, et al.
Published: (2024)

Generalized one-way function and its application
by: Yin, Hua-Lei
Published: (2024)

A new metric for evaluating the performance and complexity of computer programs: A new approach to the traditional ways of measuring the complexity of algorithms and estimating running times
by: Folea, Rares, et al.
Published: (2025)

Random regular graph states are complex at almost any depth
by: Ghosh, Soumik, et al.
Published: (2024)

Instance complexity of Boolean functions
by: Liu, Alison Hsiang-Hsuan, et al.
Published: (2023)

The complexity of computing in continuous time: space complexity is precision
by: Blanc, Manon, et al.
Published: (2024)

On the average-case complexity of learning output distributions of quantum circuits
by: Nietner, Alexander, et al.
Published: (2023)

Average-case deterministic query complexity of boolean functions with fixed weight
by: Li, Yuan, et al.
Published: (2024)

The complexity of convexity number and percolation time in the cycle convexity
by: Lima, Carlos V. G. C., et al.
Published: (2024)

Quantum computational complexity of matrix functions
by: Cifuentes, Santiago, et al.
Published: (2024)

Query complexity of Boolean functions on the middle slice of the cube
by: Gerbner, Dániel, et al.
Published: (2023)

A Subexponential Reduction from Product Partition to Subset Sum
by: Costandin, Marius
Published: (2024)

On the envelope of Poisson functional on almost complex manifolds
by: Bertrand, Florian, et al.
Published: (2023)

One-way Communication Complexity of Minimum Vertex Cover in General Graphs
by: Derakhshan, Mahsa, et al.
Published: (2025)

On query complexity measures and their relations for symmetric functions
by: Mittal, Rajat, et al.
Published: (2021)

Quantum and classical query complexities of functions of matrices
by: Montanaro, Ashley, et al.
Published: (2023)

Boolean function monotonicity testing requires (almost) $n^{1/2}$ queries
by: Chen, Mark, et al.
Published: (2025)

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields
by: Li, Tiange, et al.
Published: (2026)

Orthogonal almost complex structure and its Nijenhuis tensor
by: Tang, Zizhou, et al.
Published: (2024)

The complexity of finding and enumerating optimal subgraphs to represent spatial correlation
by: Enright, Jessica, et al.
Published: (2020)

On the complexity of Multipacking
by: Das, Sandip, et al.
Published: (2026)

Linear average-case complexity of algorithmic problems in groups
by: Olshanskii, Alexander, et al.
Published: (2022)

Unambiguous parity-query complexity
by: Gavinsky, Dmytro
Published: (2024)

Another generalization of Hadamard test: Optimal sample complexities for learning functions on the unitary group
by: Suruga, Daiki
Published: (2025)

Parameterized complexity of scheduling unit-time jobs with generalized precedence constraints
by: Büsing, Christina, et al.
Published: (2025)

On the complexity of symmetric vs. functional PCSPs
by: Nakajima, Tamio-Vesa, et al.
Published: (2022)

Exponential improvements to the average-case hardness of BosonSampling
by: Bouland, Adam, et al.
Published: (2024)

On complexity of restricted fragments of Decision DNNF
by: Calí, Andrea, et al.
Published: (2025)

On a class of interdiction problems with partition matroids: complexity and polynomial-time algorithms
by: Ketkov, Sergey S., et al.
Published: (2024)

On one filtration of holomorphic functions
by: Jacobzon, Fiana
Published: (2025)

Between the deterministic and non-deterministic query complexity
by: Gerbner, Dániel
Published: (2019)

Reconstructing Sets of Strings from Their k-way Projections: Algorithms & Complexity
by: Tate, Elise, et al.
Published: (2025)

On the complexity of embedding in graph products
by: Biedl, Therese, et al.
Published: (2023)

Unconventional complexity classes in unconventional computing (extended abstract)
by: Porreca, Antonio E.
Published: (2024)

Some structural complexity results for $\exists\mathbb R$
by: Meer, Klaus, et al.
Published: (2025)

Polynomial and analytic methods for classifying complexity of planar graph homomorphisms
by: Cai, Jin-Yi, et al.
Published: (2024)

A primer on the closure of algebraic complexity classes under factoring
by: Bhargav, C. S., et al.
Published: (2025)

Communication complexity of pointer chasing via the fixed-set lemma
by: Viola, Emanuele
Published: (2025)

On the complexity of covering points by guillotine cuts
by: Garijo, Delia, et al.
Published: (2026)

On the class of almost subadditive weight functions
by: Schindl, Gerhard
Published: (2024)