scientific article; zbMATH DE number 3489106

Cited in

(88)

Complexity questions in number theory
How to prove representation-independent independence results
Fast probabilistic algorithms for Hamiltonian circuits and matchings
Optimal algorithms for co-NP-sets and the EXP\(\overset{!}{ = }\)NEXP problem
Constructive complexity
On the theory of average case complexity
Self-witnessing polynomial-time complexity and prime factorization
On search, decision, and the efficiency of polynomial-time algorithms
An excursion to the Kolmogorov random strings
The discovery of algorithmic probability
A denial-of-service attack on fiber-based continuous-variable quantum key distribution
On relationships between complexity classes of Turing machines
Optimal design of switched Ethernet networks implementing the multiple spanning tree protocol
Autonomous theory building systems
The complexity of problems for quantified constraints
What one has to know when attacking \(\mathsf{P}\) vs.\(\mathsf{NP}\)
A theory of incremental compression
Learn to relax: integrating \(0-1\) integer linear programming with pseudo-Boolean conflict-driven search
Towards a unified approach to black-box constructions of zero-knowledge proofs
The complete set of minimal simple graphs that support unsatisfiable 2-CNFs
Satisfiability modulo theories and chiral heterotic string vacua with positive cosmological constant
Making sense of sensory input
Optimal testing for planted satisfiability problems
Computational depth: Concept and applications
Lower bounds for non-black-box zero knowledge
The 2004 Benjamin Franklin medal in computer and cognitive science presented to Richard M. Karp
Resource bounded symmetry of information revisited
Solving and Verifying the Boolean Pythagorean Triples Problem via Cube-and-Conquer
\(\mathrm P \overset {?} {=} \mathrm{NP}\)
Fixed-parameter tractability, a prehistory
Notes on Levin's theory of average-case complexity
On Khot’s unique games conjecture
On Dinur’s proof of the PCP theorem
Physical portrayal of computational complexity
Low-depth witnesses are easy to find
Algebraic attacks against random local functions and their countermeasures
Diverse Palindromic Factorization is NP-Complete
Smoothing the Gap Between NP and ER
Satisfiability in Boolean logic (SAT problem) is polynomial
Deciding Parity Games in Quasi-polynomial Time
Randomness and intractability in Kolmogorov complexity
On the Complexity of Local Graph Transformations
scientific article; zbMATH DE number 7561750 (Why is no real title available?)
scientific article; zbMATH DE number 7056228 (Why is no real title available?)
A Logical Approach to Constraint Satisfaction
On the complexity of two dimensional commuting local Hamiltonians
Parameterised complexity of model checking and satisfiability in propositional dependence logic
Hardness and methods to solve CLIQUE
The evolution of human communication and the information revolution --- A mathematical perspective
Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
Completeness for the complexity class \(\forall \exists \mathbb{R}\) and area-universality
A note on the self-witnessing property of computational problems
Quantaloidal approach to constraint satisfaction
Mathematics of computation through the lens of linear equations and lattices
NP-hardness of approximating meta-complexity: a cryptographic approach
On computing optimal temporal branchings
Interactive oracle arguments in the QROM and applications to succinct verification of quantum computation
Is ML-based cryptanalysis inherently limited? Simulating cryptographic adversaries via gradient-based methods
On computing optimal temporal branchings and spanning subgraphs
Inverse monoids associated with the complexity class NP
A complete diagrammatic calculus for Boolean satisfiability
Faster random k-CNF satisfiability
The complexity of promise SAT on non-Boolean domains
Orientable quadratic equations in wreath products of abelian groups
Guidable local Hamiltonian problems with implications to heuristic ansatz state preparation and the quantum PCP conjecture
Gap MCSP is not (Levin) NP-complete in obfustopia
On the parameterized complexity of diverse SAT
Kolmogorov complexity in the USSR (1975--1982): isolation and its end
Finite-model theory -- A personal perspective
Generating additional constraints in algebraic cryptanalysis using SAT oracles
NP-hardness of approximating meta-complexity: a cryptographic approach
Regularization of low error PCPs and an application to MCSP
Average case complexity theory
The 1982 ACM Turing Award lecture. An overview of computational complexity
Proof complexity of positive branching programs
Nondeterminism and the clique problem
An oracle with no up-complete sets, but NP = PSPACE
On approximability of satisfiable k-CSPs: V
On the expressive power of implication in classical propositional logic
On the parameterized complexity of diverse SAT
SAT reduces to the minimum circuit size problem with a random oracle
Attacks on Goldreich's pseudorandom generators by grouping and solving
Polynomial time computations in models of ET
Sophistication revisited
Time hierarchies for cryptographic function inversion with advice
In some curved spaces, one can solve NP-hard problems in polynomial time
Computing equilibria: a computational complexity perspective
A faster distributed protocol for constructing a minimum spanning tree

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4071737)