Imagen de Portada

One-Way Communication Complexity of Partial XOR Functions

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Podolskii, Vladimir V., Sluch, Dmitrii
Formato:	Preprint
Publicado:	2023
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Complexity Aspects of the Extension of Wagner's Hierarchy to $k$-Partitions
por: Podolskii, Vladimir, et al.
Publicado: (2024)

Nearest Neighbor Complexity and Boolean Circuits
por: DiCicco, Mason, et al.
Publicado: (2024)

An XOR Lemma for Deterministic Communication Complexity
por: Iyer, Siddharth, et al.
Publicado: (2024)

XOR Lemmas for Communication via Marginal Information
por: Iyer, Siddharth, et al.
Publicado: (2023)

Strong XOR Lemma for Information Complexity
por: Sawettamalya, Pachara, et al.
Publicado: (2024)

One-Way Functions and Polynomial Time Dimension
por: Nandakumar, Satyadev, et al.
Publicado: (2024)

Deterministic Lifting Theorems for One-Way Number-on-Forehead Communication
por: Yang, Guangxu, et al.
Publicado: (2025)

Simple Circuit Extensions for XOR in PTIME
por: Carmosino, Marco, et al.
Publicado: (2025)

Quantum-Computable One-Way Functions without One-Way Functions
por: Kretschmer, William, et al.
Publicado: (2024)

Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function
por: Chukhin, Nikolai, et al.
Publicado: (2024)

Refuting approaches to the log-rank conjecture for XOR functions
por: Hatami, Hamed, et al.
Publicado: (2023)

Expanders Meet Reed-Muller: Easy Instances of Noisy k-XOR
por: Błasiok, Jarosław, et al.
Publicado: (2026)

Exponential Separation of Quantum and Classical One-Way Numbers-on-Forehead Communication
por: Yang, Guangxu, et al.
Publicado: (2026)

Parallel Repetition for $3$-Player XOR Games
por: Bhangale, Amey, et al.
Publicado: (2024)

Quantum Advantage from One-Way Functions
por: Morimae, Tomoyuki, et al.
Publicado: (2023)

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

Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity
por: Mackenzie, Simon, et al.
Publicado: (2024)

SAT, Gadgets, Max2XOR, and Quantum Annealers
por: Ansótegui, Carlos, et al.
Publicado: (2024)

Pseudodeterministic Communication Complexity
por: Göös, Mika, et al.
Publicado: (2025)

Parameterized Complexity of Fair Many-to-One Matchings
por: Javadi, Ramin, et al.
Publicado: (2024)

Quantum and Classical Communication Complexity of Permutation-Invariant Functions
por: Guan, Ziyi, et al.
Publicado: (2023)

Structure in Communication Complexity and Constant-Cost Complexity Classes
por: Hatami, Hamed, et al.
Publicado: (2024)

Communication Complexity is NP-hard
por: Hirahara, Shuichi, et al.
Publicado: (2025)

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
por: Mao, Songtao
Publicado: (2026)

Multiparty Communication Complexity of Collision Finding
por: Beame, Paul, et al.
Publicado: (2024)

Optimal Communication Complexity of Chained Index
por: Sundaresan, Janani
Publicado: (2024)

A Hierarchy for Constant Communication Complexity
por: Ambainis, Andris, et al.
Publicado: (2025)

On the Computational Hardness of Quantum One-Wayness
por: Cavalar, Bruno, et al.
Publicado: (2023)

Average-Case Reductions for $k$-XOR and Tensor PCA
por: Bresler, Guy, et al.
Publicado: (2026)

Quantum Public-Key Encryption with Tamper-Resilient Public Keys from One-Way Functions
por: Kitagawa, Fuyuki, et al.
Publicado: (2023)

Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR
por: Dinur, Itai, et al.
Publicado: (2021)

Complexity of some algorithmic problems in groups: a survey
por: Shpilrain, Vladimir
Publicado: (2024)

Second-Order Parameterizations for the Complexity Theory of Integrable Functions
por: Bacho, Aras, et al.
Publicado: (2025)

Towards EXPTIME One Way Functions: Bloom Filters, Succinct Graphs, Cliques, & Self Masking
por: Dolev, Shlomi
Publicado: (2025)

The No Endmarker Theorem for One-Way Probabilistic Pushdown Automata
por: Yamakami, Tomoyuki
Publicado: (2021)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
por: Greilhuber, Jakob, et al.
Publicado: (2025)

Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
por: de Rezende, Susanna F., et al.
Publicado: (2026)

A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity
por: Dvořák, Pavel, et al.
Publicado: (2024)

Communication Complexity of Disjointness under Product Distributions
por: Hunter, Zach, et al.
Publicado: (2026)

Partial and weighted matrix multiplication
por: Vrana, Péter
Publicado: (2024)