Computational Complexity
From MaRDI portal
Publication:5320667
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum algorithms and complexity in the theory of computing (68Q12) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)
Recommendations
Cited in
(only showing first 100 items - show all)- On the complexity of formulas in semantic programming
- Circuit complexity in interacting QFTs and RG flows
- The isoperimetric spectrum of finitely presented groups
- On the limits of gate elimination
- Computational complexity of the landscape. II: Cosmological considerations
- Analysis of FPTASes for the multi-objective shortest path problem
- Reducing the size of combinatorial optimization problems using the operator vaccine by fuzzy selector with adaptive heuristics
- Evolution of complexity following a quantum quench in free field theory
- Towards a characterization of constant-factor approximable finite-valued CSPs
- Sabidussi versus Hedetniemi for three variations of the chromatic number
- Quantum one-way permutation over the finite field of two elements
- On the complexity of input/output logic
- Keeping logic in the trivium of computer science: a teaching perspective
- Towards implementation of a generalized architecture for high-level quantum programming language
- Catalytic space: non-determinism and hierarchy
- Knapsack in graph groups
- Why is it hard to beat \(O(n^2)\) for longest common weakly increasing subsequence?
- The intersection of subgroups in free groups and linear programming
- Parameterized complexity of theory of mind reasoning in dynamic epistemic logic
- Approximate inference in Bayesian networks: parameterized complexity results
- A parameterized algorithmics framework for degree sequence completion problems in directed graphs
- On the complexity of the Leibniz hierarchy
- The complexity of counting models of linear-time temporal logic
- Metric estimates and membership complexity for Archimedean amoebae and tropical hypersurfaces
- Evaluation of circuits over nilpotent and polycyclic groups
- Research on the efficient computation mechanism -- in the case of N-vehicle exploration problem
- Understanding cutting planes for QBFs
- Computational complexity and 3-manifolds and zombies
- Complexity of deciding detectability in discrete event systems
- On \textsf{NC} algorithms for problems on bounded rank-width graphs
- How strong is Nisan's pseudo-random generator?
- Parameterized random complexity
- Small space analogues of Valiant's classes and the limitations of skew formulas
- On the computational complexity of data flow analysis over finite bounded meet semilattices
- Coloring invariants of knots and links are often intractable
- The complexity of computing a (quasi-)perfect equilibrium for an \(n\)-player extensive form game
- On the approximability of robust network design
- Better complexity bounds for cost register automata
- Recovering nonuniform planted partitions via iterated projection
- Rules with parameters in modal logic. II.
- Feasibly constructive proofs of succinct weak circuit lower bounds
- Counting substrate cycles in topologically restricted metabolic networks
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
- Parallelization of entanglement-resistant multi-prover interactive proofs
- Multivariate time series analysis from a Bayesian machine learning perspective
- On the hardness of covering-interdiction problems
- Weighted automata are compact and actively learnable
- The trouble with the second quantifier
- A unifying model for locally constrained spanning tree problems
- On the parametrized complexity of read-once refutations in UTVPI+ constraint systems
- On equations and first-order theory of one-relator monoids
- On the complexity of asynchronous freezing cellular automata
- The complexity of finding temporal separators under waiting time constraints
- Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II
- Comparing the notions of opacity for discrete-event systems
- On verification of D-detectability for discrete event systems
- A nondeterministic Turing machine variant to compute functions
- On the complexity of solution extension of optimization problems
- On some FPT problems without polynomial Turing compressions
- Asymptotic connectedness of random interval graphs in a one dimensional data delivery problem
- Choice logics and their computational properties
- Query answering over inconsistent knowledge bases: a probabilistic approach
- Computing the probability of getting infected: on the counting complexity of bootstrap percolation
- Gardens of Eden in the game of life
- Colored cut games
- Computational complexity of problems for deterministic presentations of sofic shifts
- Sensor scheduling design for complex networks under a distributed state estimation framework
- Reducing the time required to find the Kemeny ranking by exploiting a necessary condition for being a winner
- Self-driven algorithm for solving supermodular (,+) labeling problems based on subgradient descent
- A sieve stochastic gradient descent estimator for online nonparametric regression in Sobolev ellipsoids
- Liouville numbers and the computational complexity of changing bases
- On the complexity of conversion between classic real number representations
- PAC-learning gains of Turing machines over circuits and neural networks
- Approximate NFA universality motivated by information theory
- Mosaics of combinatorial designs for information-theoretic security
- Lower bounds and hardness magnification for sublinear-time shrinking cellular automata
- New limits of treewidth-based tractability in optimization
- Hardness and optimality in QBF proof systems modulo NP
- Analysis of periodic linear systems over finite fields with and without Floquet transform
- Equivalence classes and conditional hardness in massively parallel computations
- On regularity of Max-CSPs and Min-CSPs
- Advanced algorithms for abstract dialectical frameworks based on complexity analysis of subclasses and SAT solving
- An overview of structural systems theory
- Emergence of the fused spacetime from a continuum computing construct of reality
- Constructing locally leakage-resilient linear secret-sharing schemes
- On efficiency of notations for natural numbers
- Completeness, approximability and exponential time results for counting problems with easy decision version
- A logic of interactive proofs
- Between Turing and Kleene
- A tetrachotomy of ontology-mediated queries with a covering axiom
- On the decidability of infix inclusion problem
- On the complexity of finding shortest variable disjunction branch-and-bound proofs
- Real-time, constant-space, constant-randomness verifiers
- Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields
- Depth-first search in directed planar graphs, revisited
- Accelerating deep learning with memcomputing
- Constant work-space algorithms for facility location problems
- Strong continuous non-malleable encoding schemes with tamper-detection
- On NP-hard graph properties characterized by the spectrum
- On one-step worst-case optimal trisection in univariate bi-objective Lipschitz optimization
This page was built for publication: Computational Complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5320667)
