Approximating Succinct MaxSat.

Approximating Succinct MaxSat.

We study the approximability of the version of MAXSAT where exponentially large instances are succinctly represented using circuits. First, we prove that the NP-hardness for approximating MAXSAT can be lifted to a corresponding NEXP-hardness for approximating circuit-succinct MAXSAT for some constan...

书目详细资料
Main Authors:	Schallhart, C, Trevisan, L
格式:	Journal article
语言:	English
出版:	2005

相似书籍

Clausal Forms in MaxSAT and MinSAT
由: Chu Min Li, et al.
出版: (2022-11-01)

Decoding quantum color codes with MaxSAT
由: Lucas Berent, et al.
出版: (2024-10-01)

Dynamic Initial Weight Assignment for MaxSAT
由: Abdelraouf Ishtaiwi, et al.
出版: (2021-03-01)

Negative Learning Ant Colony Optimization for MaxSAT
由: Teddy Nurcahyadi, et al.
出版: (2022-08-01)

The Impact of Implied Constraints on MaxSAT B2B Instances
由: Miquel Bofill, et al.
出版: (2022-08-01)

A continuous-time MaxSAT solver with high analog performance
由: Botond Molnár, et al.
出版: (2018-11-01)

Initial Solution Generation and Diversified Variable Picking in Local Search for (Weighted) Partial MaxSAT
由: Zaijun Zhang, et al.
出版: (2022-12-01)

Counterexample guided program repair using zero-shot learning and MaxSAT-based fault localization
由: Orvalho, P, et al.
出版: (2025)

On the Succinctness of Atoms of Dependency
由: Martin Lück, et al.
出版: (2019-08-01)

Succinct Computational Secret Sharing
由: Applebaum, Benny, et al.
出版: (2023)

Succinct non-subsequence arguments
由: Ling, San, et al.
出版: (2024)

Succinct summaries of research methods
由: Xianqing Luo, et al.
出版: (2022-12-01)

Succinct non-Interactive arguments
由: Chiesa, Alessandro
出版: (2015)

Research on the Solution Space of 2-SAT and Max-2-SAT
由: Li Bai-Feng, et al.
出版: (2016-01-01)

Compositional Algorithms for Succinct Safety Games
由: Romain Brenguier, et al.
出版: (2016-02-01)

Succinct Representation of Codes with Applications to Testing
由: Sudan, Madhu, et al.
出版: (2010)

On deploying succinct zero-knowledge proofs
由: Virza, Madars
出版: (2018)

Reachability in Succinct and Parametric One−Counter Automata
由: Haase, C, et al.
出版: (2009)

Reachability in Succinct and Parametric One-Counter Automata
由: Haase, C, et al.
出版: (2009)

Max 2-SAT with up to 108 qubits
由: Siddhartha Santra, et al.
出版: (2014-01-01)

On the use of Max-SAT and PDDL in RBAC maintenance
由: Marco Benedetti, et al.
出版: (2019-07-01)

On the succinctness of query rewriting over shallow ontologies
由: Kikot, Stanislav, et al.
出版: (2014)

The succinctness of first-order logic on linear orders
由: Martin Grohe, et al.
出版: (2005-06-01)

Impossibility of Succinct Quantum Proofs for Collision-Freeness
由: Aaronson, Scott
出版: (2012)

Succinct garbled RAM from indistinguishablity obfuscation
由: Holmgren, Justin Lee
出版: (2016)

Succinctness as a Source of Complexity in Logical Formalisms
由: Gottlob, G, et al.
出版: (1999)

Reusable garbled circuits and succinct functional encryption
由: Goldwasser, Shafi, et al.
出版: (2014)

Succinctness of two-way probabilistic and quantum finite automata
由: Abuzer Yakaryilmaz, et al.
出版: (2010-01-01)

Model Checking Succinct and Parametric One-Counter Automata.
由: Göller, S, et al.
出版: (2010)

Model Checking Succinct and Parametric One−Counter Automata
由: Göller, S, et al.
出版: (2010)

A simple and succinct simulation of Nikolsky phenomenon and sign
由: Keshavmurthy A Adya, et al.
出版: (2020-01-01)

Indistinguishability Obfuscation for RAM Programs and Succinct Randomized Encodings
由: Bitansky, Nir, et al.
出版: (2021)

Revisiting Leakage-Resilient MACs and Succinctly-Committing AEAD
由: Mustafa Khairallah
出版: (2025-03-01)

Computing RF Tree Distance over Succinct Representations
由: António Pedro Branco, et al.
出版: (2023-12-01)

Countdown games, and simulation on (succinct) one-counter nets
由: Petr Jancar, et al.
出版: (2023-02-01)

A succinct rating scale for radiology report quality
由: Chengwu Yang, et al.
出版: (2014-12-01)

On the (Non−)Succinctness of Uniform Interpolation in General EL Terminologies
由: Nikitina, N, et al.
出版: (2012)

Breaking of 1RSB in Random Regular MAX-NAE-SAT
由: Bartha, Zsolt, et al.
出版: (2021)

MAX-SAT Problem using Hybrid Harmony Search Algorithm
由: Abu Doush Iyad, et al.
出版: (2018-10-01)

BSuccinct: Rust libraries and programs focused on succinct data structures
由: Piotr Beling
出版: (2024-05-01)