Cover Image

Optimal Polynomial-Time Estimators: A Bayesian Notion of Approximation Algorithm

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kosoy, Vanessa, Appel, Alexander
Format:	Preprint
Published:	2016
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Time complexity for deterministic string machines
by: Cataltepe, Ali, et al.
Published: (2024)

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

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

A Polynomial Time Algorithm for 3SAT
by: Quigley, Robert
Published: (2024)

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

A Near-Optimal Polynomial Distance Lemma Over Boolean Slices
by: Amireddy, Prashanth, et al.
Published: (2025)

Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
by: Guruswami, Venkatesan, et al.
Published: (2024)

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

Near Optimal Hardness of Approximating $k$-CSP
by: Minzer, Dor, et al.
Published: (2025)

The Optimal Approximation Factor in Density Estimation
by: Bousquet, Olivier, et al.
Published: (2019)

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

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
by: Esmer, Barış Can, et al.
Published: (2022)

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

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
by: Buhrman, Harry, et al.
Published: (2025)

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

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

Classically Sampling Noisy Quantum Circuits in Quasi-Polynomial Time under Approximate Markovianity
by: Zhang, Yifan F., et al.
Published: (2025)

Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields
by: Dwivedi, Ashish, et al.
Published: (2024)

Polynomial-Time Optimal Group Selection via the Double-Commutator Eigenvalue Problem
by: Thornton, Mitchell A.
Published: (2026)

Regret Bounds for Robust Online Decision Making
by: Appel, Alexander, et al.
Published: (2025)

Sharp Phase Transitions in Estimation with Low-Degree Polynomials
by: Sohn, Youngtak, et al.
Published: (2025)

Optimal Sensor and Actuator Selection for Factored Markov Decision Processes: Complexity, Approximability and Algorithms
by: Bhargav, Jayanth, et al.
Published: (2024)

A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees
by: Shao, Shuai, et al.
Published: (2023)

Quantum Algorithms for Approximate Graph Isomorphism Testing
by: Kulkarni, Prateek P.
Published: (2026)

Testing Isomorphism of Graphs in Polynomial Time
by: Xue, Rui
Published: (2023)

A Schematic Definition of Quantum Polynomial Time Computability
by: Yamakami, Tomoyuki
Published: (2018)

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

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

On Matrix Multiplication and Polynomial Identity Testing
by: Andrews, Robert
Published: (2022)

On Boolean PCSPs with Polynomial Threshold Polymorphisms
by: Michno, Katzper
Published: (2025)

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

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

Sublinear Time Algorithms for Abelian Group Isomorphism and Basis Construction
by: Bshouty, Nader H.
Published: (2025)

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

Computing the Elementary Symmetric Polynomials in Positive Characteristics
by: Orzel, Ian
Published: (2025)

On Factorization of Sparse Polynomials of Bounded Individual Degree
by: Chuyoon, Aminadav, et al.
Published: (2026)

Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth
by: Rajakumar, Joel, et al.
Published: (2024)

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

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
by: Khanna, Sanjeev, et al.
Published: (2025)

Algorithmically Optimal Outer Measures
by: Lutz, Jack H., et al.
Published: (2020)