Copertina

One-Way Functions and Polynomial Time Dimension

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Nandakumar, Satyadev, Pulari, Subin, S, Akhil, Sarma, Suronjona
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Point-to-set Principle and Constructive Dimension Faithfulness
di: Nandakumar, Satyadev, et al.
Pubblicazione: (2024)

Resource bounded Kučera-Gács Theorems
di: Nandakumar, Satyadev, et al.
Pubblicazione: (2026)

On the Constructive Dimension Spectrum of Polynomials
di: Koul, Prajval, et al.
Pubblicazione: (2026)

One-Way Communication Complexity of Partial XOR Functions
di: Podolskii, Vladimir V., et al.
Pubblicazione: (2023)

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

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

Lifting with Inner Functions of Polynomial Discrepancy
di: Manor, Yahel, et al.
Pubblicazione: (2024)

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

Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension
di: Klivans, Adam R., et al.
Pubblicazione: (2026)

A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions
di: Yao, Penghui, et al.
Pubblicazione: (2025)

Polynomial-Time PIT from (Almost) Necessary Assumptions
di: Andrews, Robert, et al.
Pubblicazione: (2025)

Range Avoidance in Boolean Circuits via Turan-type Bounds
di: Kuntewar, Neha, et al.
Pubblicazione: (2025)

A Critique of Du's "A Polynomial-Time Algorithm for 3-SAT
di: He, Yumeng, et al.
Pubblicazione: (2024)

A Critique of Quigley's "A Polynomial Time Algorithm for 3SAT"
di: DeJesse, Nicholas, et al.
Pubblicazione: (2025)

Optimal Polynomial-Time Estimators: A Bayesian Notion of Approximation Algorithm
di: Kosoy, Vanessa, et al.
Pubblicazione: (2016)

Oracle Separation between Noisy Quantum Polynomial Time and the Polynomial Hierarchy
di: Chia, Nai-Hui, et al.
Pubblicazione: (2024)

A Critique of Chen's "The 2-MAXSAT Problem Can Be Solved in Polynomial Time"
di: Le, Tran Duy Anh, et al.
Pubblicazione: (2024)

A Hierarchy of Tinhofer Graphs: Separations and Membership Testing
di: Bhattacharjee, Sutanay, et al.
Pubblicazione: (2026)

VP, VNP and Algebraic Branching Programs over Min-Plus Semirings
di: Komarath, Balagopal, et al.
Pubblicazione: (2026)

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

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

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

A New Reduction Method from Multivariate Polynomials to Univariate Polynomials
di: Wang, Cancan, et al.
Pubblicazione: (2024)

On Condensation of Block Sensitivity, Certificate Complexity and the $\mathsf{AND}$ (and $\mathsf{OR}$) Decision Tree Complexity
di: Nalli, Sai Soumya, et al.
Pubblicazione: (2026)

Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming
di: Gibor, Daniel
Pubblicazione: (2025)

On Normality and Equidistribution for Separator Enumerators
di: Pulari, Subin
Pubblicazione: (2026)

Efficient Constructions of Finite-State Independent Normal Pairs
di: Pulari, Subin
Pubblicazione: (2026)

Testing Isomorphism of Graphs in Polynomial Time
di: Xue, Rui
Pubblicazione: (2023)

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

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

Almost-catalytic Computation
di: Bisoyi, Sagar, et al.
Pubblicazione: (2024)

Hazard-free Decision Trees
di: Benson, Deepu, et al.
Pubblicazione: (2025)

Symmetric Algebraic Circuits and Homomorphism Polynomials
di: Dawar, Anuj, et al.
Pubblicazione: (2025)

On Matrix Multiplication and Polynomial Identity Testing
di: Andrews, Robert
Pubblicazione: (2022)

On Boolean PCSPs with Polynomial Threshold Polymorphisms
di: Michno, Katzper
Pubblicazione: (2025)

A Polynomial Time Algorithm for 3SAT
di: Quigley, Robert
Pubblicazione: (2024)

There is a Hyper-Greedoid lurking behind every Graphical Accessible Computational Search Problem solvable in Polynomial Time: $P \not= NP$
di: Kayibi, Koko-Kalambay Kalafan
Pubblicazione: (2018)

MP-Aggregation MP(R,2-WO) is Polynomial-Time Solvable When the Output Should Be Dichotomous Weak Preference Order
di: Chen, Jiehua
Pubblicazione: (2025)

Functional variant of Polynomial Analogue of Gandy's Fixed Point Theorem
di: Nechesov, Andrey
Pubblicazione: (2024)

Attacking the Polynomials in the Maze of Finite Fields problem
di: Barbero, Àngela, et al.
Pubblicazione: (2026)