Image de couverture de livre

On one-way functions and the average time complexity of almost-optimal compression

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteur principal:	Zimand, Marius
Format:	Preprint
Publié:	2024
Sujets:	Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Computable one-way functions on the reals
par: Barmpalias, George, et autres
Publié: (2024)

Generalized one-way function and its application
par: Yin, Hua-Lei
Publié: (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
par: Folea, Rares, et autres
Publié: (2025)

Random regular graph states are complex at almost any depth
par: Ghosh, Soumik, et autres
Publié: (2024)

Instance complexity of Boolean functions
par: Liu, Alison Hsiang-Hsuan, et autres
Publié: (2023)

The complexity of computing in continuous time: space complexity is precision
par: Blanc, Manon, et autres
Publié: (2024)

The complexity of convexity number and percolation time in the cycle convexity
par: Lima, Carlos V. G. C., et autres
Publié: (2024)

Average-case deterministic query complexity of boolean functions with fixed weight
par: Li, Yuan, et autres
Publié: (2024)

On the average-case complexity of learning output distributions of quantum circuits
par: Nietner, Alexander, et autres
Publié: (2023)

Query complexity of Boolean functions on the middle slice of the cube
par: Gerbner, Dániel, et autres
Publié: (2023)

A Subexponential Reduction from Product Partition to Subset Sum
par: Costandin, Marius
Publié: (2024)

Quantum computational complexity of matrix functions
par: Cifuentes, Santiago, et autres
Publié: (2024)

One-way Communication Complexity of Minimum Vertex Cover in General Graphs
par: Derakhshan, Mahsa, et autres
Publié: (2025)

On query complexity measures and their relations for symmetric functions
par: Mittal, Rajat, et autres
Publié: (2021)

Quantum and classical query complexities of functions of matrices
par: Montanaro, Ashley, et autres
Publié: (2023)

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields
par: Li, Tiange, et autres
Publié: (2026)

Boolean function monotonicity testing requires (almost) $n^{1/2}$ queries
par: Chen, Mark, et autres
Publié: (2025)

On the envelope of Poisson functional on almost complex manifolds
par: Bertrand, Florian, et autres
Publié: (2023)

Orthogonal almost complex structure and its Nijenhuis tensor
par: Tang, Zizhou, et autres
Publié: (2024)

On the complexity of Multipacking
par: Das, Sandip, et autres
Publié: (2026)

The complexity of finding and enumerating optimal subgraphs to represent spatial correlation
par: Enright, Jessica, et autres
Publié: (2020)

Unambiguous parity-query complexity
par: Gavinsky, Dmytro
Publié: (2024)

On complexity of restricted fragments of Decision DNNF
par: Calí, Andrea, et autres
Publié: (2025)

Exponential improvements to the average-case hardness of BosonSampling
par: Bouland, Adam, et autres
Publié: (2024)

Parameterized complexity of scheduling unit-time jobs with generalized precedence constraints
par: Büsing, Christina, et autres
Publié: (2025)

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

Linear average-case complexity of algorithmic problems in groups
par: Olshanskii, Alexander, et autres
Publié: (2022)

Between the deterministic and non-deterministic query complexity
par: Gerbner, Dániel
Publié: (2019)

On a class of interdiction problems with partition matroids: complexity and polynomial-time algorithms
par: Ketkov, Sergey S., et autres
Publié: (2024)

Unconventional complexity classes in unconventional computing (extended abstract)
par: Porreca, Antonio E.
Publié: (2024)

Some structural complexity results for $\exists\mathbb R$
par: Meer, Klaus, et autres
Publié: (2025)

On one filtration of holomorphic functions
par: Jacobzon, Fiana
Publié: (2025)

Polynomial and analytic methods for classifying complexity of planar graph homomorphisms
par: Cai, Jin-Yi, et autres
Publié: (2024)

A primer on the closure of algebraic complexity classes under factoring
par: Bhargav, C. S., et autres
Publié: (2025)

Communication complexity of pointer chasing via the fixed-set lemma
par: Viola, Emanuele
Publié: (2025)

On the complexity of embedding in graph products
par: Biedl, Therese, et autres
Publié: (2023)

On the complexity of symmetric vs. functional PCSPs
par: Nakajima, Tamio-Vesa, et autres
Publié: (2022)

Positive Univariate Polynomials: SOS certificates, algorithms, bit complexity, and T-systems
par: Bender, Matías, et autres
Publié: (2025)

Decision algorithms for reversibility of one-dimensional non-linear cellular automata under null boundary conditions
par: Junchi, Ma, et autres
Publié: (2024)

Monitoring graph edges via shortest paths: computational complexity and approximation algorithms
par: Colli, Giordano
Publié: (2025)