Computational Complexity
From MaRDI portal
Publication:5320667
DOI10.1017/CBO9780511804090zbMath1193.68112OpenAlexW4298227433WikidataQ59702265 ScholiaQ59702265MaRDI QIDQ5320667
Publication date: 22 July 2009
Full work available at URL: https://doi.org/10.1017/cbo9780511804090
Analysis of algorithms and problem complexity (68Q25) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items
Chromatic kernel and its applications, Post-quench evolution of complexity and entanglement in a topological system, On the complexity of formulas in semantic programming, Generic properties of a computational task predict human effort and performance, Regularity properties for sparse regression, Concurrent phenomena at the reaction path of the \(S_{\mathrm N}2\) reaction \(\mathrm{CH}_3\mathrm{Cl}+F^-\). Information planes and statistical complexity analysis, Reverse complexity, A probabilistic interpretation of set-membership filtering: application to polynomial systems through polytopic bounding, 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, AND-compression of NP-complete problems: streamlined proof and minor observations, Comparator circuits over finite bounded posets, On regular realizability problems for context-free languages, Computational complexity of distance edge labeling, The VC-dimension of graphs with respect to \(k\)-connected subgraphs, Analysis of FPTASes for the multi-objective shortest path problem, Correlation bounds and \#SAT algorithms for small linear-size circuits, Is Valiant-Vazirani's isolation probability improvable?, Reducing the size of combinatorial optimization problems using the operator vaccine by fuzzy selector with adaptive heuristics, First characterization of a new method for numerically solving the Dirichlet problem of the two-dimensional electrical impedance equation, Evolution of complexity following a quantum quench in free field theory, Towards a characterization of constant-factor approximable finite-valued CSPs, Computational complexity of the landscape. I., On regular realizability problems, A complete one-way function based on a finite rank free \(\mathbb{Z}\times\mathbb{Z}\)-module, Sabidussi versus Hedetniemi for three variations of the chromatic number, On enumerating monomials and other combinatorial structures by polynomial interpolation, Quantum one-way permutation over the finite field of two elements, Reprint of: Memory-constrained algorithms for simple polygons, Computational implications of reducing data to sufficient statistics, Critical sets for Sudoku and general graph colorings, List-homomorphism problems on graphs and arc consistency, Pseudorandom generators for \(\mathrm{CC}^0[p\) and the Fourier spectrum of low-degree polynomials over finite fields], Computing a visibility polygon using few variables, A complementarity-based rolling friction model for rigid contacts, On the complexity of input/output logic, Proof systems for planning under 0-approximation semantics, Hardness of embedding simplicial complexes in \(\mathbb R^d\), Lower bounds on the sizes of integer programs without additional variables, Theory of interaction, PSPACE-completeness of majority automata networks, The complexity of power indexes with graph restricted coalitions, On the complexity of second-best abductive explanations, Pseudorandom generators against advised context-free languages, Linear algebraic methods in communication complexity, Keeping logic in the trivium of computer science: a teaching perspective, On derandomization and average-case complexity of monotone functions, Adaptation of a one-step worst-case optimal univariate algorithm of bi-objective Lipschitz optimization to multidimensional problems, Space complexity of perfect matching in bounded genus bipartite graphs, Information-theoretical complexity for the hydrogenic identity \(S_N2\) exchange reaction, Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds, Immunity and pseudorandomness of context-free languages, Convergence of random series and the rate of convergence of the strong law of large numbers in game-theoretic probability, Derandomization in game-theoretic probability, Generalized counting constraint satisfaction problems with determinantal circuits, Temporal logics for concurrent recursive programs: satisfiability and model checking, Computational complexity of threshold automata networks under different updating schemes, A one-step worst-case optimal algorithm for bi-objective univariate optimization, The kernelization complexity of connected domination in graphs with (no) small cycles, \textsc{PAutomaC}: a probabilistic automata and hidden Markov models learning competition, Lower bounds against weakly-uniform threshold circuits, On uniformity and circuit lower bounds, Review of real-time vehicle schedule recovery methods in transportation services, The complexity of debate checking, Space-time trade-offs for stack-based algorithms, Verifying time complexity of Turing machines, Quantum digital-to-analog conversion algorithm using decoherence, Application of distributed semi-quantum computing model in phase estimation, On the possibilistic approach to linear regression models involving uncertain, indeterminate or interval data, On minimum maximal distance-\(k\) matchings, The real nonnegative inverse eigenvalue problem is NP-hard, The complexity of finding effectors, Log-space conjugacy problem in the Grigorchuk group, Tableau systems for deontic action logics based on finite Boolean algebras, and their complexity, Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings, Color-blind index in graphs of very low degree, Collapsing and separating completeness notions under average-case and worst-case hypotheses, The complexity of the list homomorphism problem for graphs, The complexity of explicit constructions, Avoiding simplicity is complex, Smallest formulas for the parity of \(2^k\) variables are essentially unique, Instruction sequence processing operators, Complexity classes of equivalence problems revisited, Exact localisations of feedback sets, On complete one-way functions, Counting houses of Pareto optimal matchings in the house allocation problem, \textsc{ReachFewL} = \textsc{ReachUL}, Tradeoff lower lounds for stack machines, A formalization of multi-tape Turing machines, Absoluteness of subword inequality is undecidable, Extension complexity of formal languages, Graph coloring: a novel heuristic based on trailing path-properties, perspective and applications in structured networks, The ghost in the radiation: robust encodings of the black hole interior, Complexity of abstract argumentation under a claim-centric view, Tropical varieties for exponential sums, An inner approximation method to compute the weight set decomposition of a triobjective mixed-integer problem, On the query complexity of selecting minimal sets for monotone predicates, Computational complexity in the design of voting rules, The dependence of computability on numerical notations, Coverability in 2-VASS with one unary counter is in NP, Parameterised counting in logspace, Approximate NFA universality and related problems motivated by information theory, Communication complexity meets cellular automata: necessary conditions for intrinsic universality, The complexity landscape of claim-augmented argumentation frameworks, Analytical Problem Solving Based on Causal, Correlational and Deductive Models, On counting propositional logic and Wagner's hierarchy, Commuting quantum circuits and complexity of Ising partition functions, The risk of maternal complications after Cesarean delivery: near-far matching for instrumental variables study designs with large observational datasets, Complexity and multi-boundary wormholes in \(2 + 1\) dimensions, Complexity is a matter of distance, Subclasses of \textsc{Ptime} interpreted by programming languages, Leakage-resilient linear secret-sharing against arbitrary bounded-size leakage family, On computing probabilistic abductive explanations, The power of natural properties as oracles, О стойкости режима аутентифицированного шифрования с дополнительными данными MGM к угрозе нарушения конфиденциальности;On the security of authenticated encryption mode with associated data MGM with respect to confidentiality threat, Proof Compression and NP Versus PSPACE II: Addendum, Constraint satisfaction problem: what makes the problem easy, Identifying optimal strategies in kidney exchange games is \(\varSigma_2^p\)-complete, Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic, On real structured controllability/stabilizability/stability radius: complexity and unified rank-relaxation based methods, A System of Interaction and Structure III: The Complexity of BV and Pomset Logic, The minimum generating set problem, Large population limits of Markov processes on random networks, Hardness transitions and uniqueness of acyclic colouring, Weighted packet selection for rechargeable links in cryptocurrency networks: complexity and approximation, Paradigms for Unconditional Pseudorandom Generators, Biased opinion dynamics: when the devil is in the details, Towards Uniform Certification in QBF, Complexity of verification in self-assembly with prebuilt assemblies, Time-release cryptography from minimal circuit assumptions, Knapsack and the power word problem in solvable Baumslag–Solitar groups, New lower bounds for matrix multiplication and, PPAD-complete pure approximate Nash equilibria in Lipschitz games, Score-based explanations in data management and machine learning: an answer-set programming approach to counterfactual analysis, PPAD is as hard as LWE and iterated squaring, Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022, On the complexity of robust multi-stage problems with discrete recourse, Weighted packet selection for rechargeable links in cryptocurrency networks: complexity and approximation, Rejection-proof mechanisms for multi-agent kidney exchange, Algebraic reductions of knowledge, On algebraic array theories, Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial, Interactions of computational complexity theory and mathematics, Almost disjoint paths and separating by forbidden pairs, Communication and information complexity, Random quantum circuits transform local noise into global white noise, Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics, Unnamed Item, Complexity-theoretic aspects of expanding cellular automata, Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata, Randomness extraction in computability theory, Łukasiewicz Games, A generic optimization framework for resilient systems, Completeness Results for Counting Problems with Easy Decision, Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas, Probabilistic Algorithmic Randomness, ON THE POWER QUANTUM COMPUTATION OVER REAL HILBERT SPACES, Unnamed Item, Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization, IMAGE ENCRYPTION BASED ON TWO-DIMENSIONAL FRACTIONAL QUADRIC POLYNOMIAL MAP, THE RECOGNITION COMPLEXITY OF DECIDABLE THEORIES, Sublinear P system solutions to NP-complete problems, Space-efficient algorithms for reachability in directed geometric graphs, Complexity, information geometry, and Loschmidt echo near quantum criticality, Quantum algorithm for dynamic programming approach for DAGs and applications, Effective Poset Inequalities, On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1, GLOBAL ATTRACTIVITY, ASYMPTOTIC STABILITY AND BLOW-UP POINTS FOR NONLINEAR FUNCTIONAL-INTEGRAL EQUATIONS’ SOLUTIONS AND APPLICATIONS IN BANACH SPACE BC(R+) WITH COMPUTATIONAL COMPLEXITY, Smoothed counting of 0–1 points in polyhedra, Tight Localizations of Feedback Sets, An Exact Method for the Minimum Feedback Arc Set Problem, Why adiabatic quantum annealing is unlikely to yield speed-up, Chess Equilibrium Puzzles, PPAD-complete approximate pure Nash equilibria in Lipschitz games, On the reliability estimation of stochastic binary systems, The computational complexity of knot genus in a fixed 3‐manifold, NP-Hardness of Computing PL Geometric Category in Dimension 2, Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU, Explainable acceptance in probabilistic and incomplete abstract argumentation frameworks, Optimal Quantum Violations of n‐Locality Inequalities with Conditional Dependence on Inputs, Parallel algorithms for power circuits and the word problem of the Baumslag group, The Computational Complexity of Integer Programming with Alternations, A remark on pseudo proof systems and hard instances of the satisfiability problem, The Bounded and Precise Word Problems for Presentations of Groups, Unnamed Item, Characterizing polynomial Ramsey quantifiers, Model Reductions for Inference: Generality of Pairwise, Binary, and Planar Factor Graphs, Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms, Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma, Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs, Parallel Repetition of Two-Prover One-Round Games: An Exposition, A Solution Concept Related to “Bounded Rationality” for some Two-Echelon Models, Encodings of Turing machines in linear logic, The Complexity Landscape of Outcome Determination in Judgment Aggregation, The Undecidability of the Domino Problem, First-Order Model-Checking in Random Graphs and Complex Networks, Proof Compression and NP Versus PSPACE II, Constructing concrete hard instances of the maximum independent set problem, A note on the complexity of S4.2, Space Hardness of Solving Structured Linear Systems., Physical Computational Complexity and First-order Logic, Arithmetic Expression Construction., Parallelism and Time in Hierarchical Self-Assembly, Algebraic independence in positive characteristic: A $p$-adic calculus, Space Complexity of Reachability Testing in Labelled Graphs, Characterizingco-NLby a group action, Real-time, constant-space, constant-randomness verifiers, Unnamed Item, Unnamed Item, Computational topology and the Unique Games Conjecture, The computational power of parsing expression grammars, Grammar-based compression of unranked trees, No-signaling linear PCPs, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Cutting corners, No-signaling linear PCPs, On computational complexity of set automata, Unnamed Item, Obtaining a proportional allocation by deleting items, Recognizing the tractability in big data computing, ICE-based refinement type discovery for higher-order functional programs, On Functions Computed on Trees, Unnamed Item, Эффективная вычислительная процедура альтернансного метода оптимизации, Unnamed Item, Unnamed Item, Unnamed Item, Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle, A dichotomy result for cyclic-order traversing games, Circuit lower bounds from NP-hardness of MCSP under turing reductions, Unnamed Item, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, Complexity of Restricted Variants of Skolem and Related Problems, Characterizations of periods of multi-dimensional shifts, Semigroups and one-way functions, Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses, Logic and Complexity in Cognitive Science, Efficient algorithms for approximating quantum partition functions, Unnamed Item, An algebraic characterization of 𝑘–colorability, The Connes embedding problem: A guided tour, Statistical mechanics analysis of generalized multi-dimensional knapsack problems, Implicit computation complexity in higher-order programming languages, Continuous One-counter Automata, MaxSAT Resolution and Subcube Sums, Quantum de Finetti theorems under local measurements with applications, On the linear classification of even and odd permutation matrices and the complexity of computing the permanent, Quantum alternation, Complete Problem for Perfect Zero-Knowledge Quantum Proof, Grothendieck-Type Inequalities in Combinatorial Optimization, \(\mathcal{IV}\)-matching is strongly \textsf{NP}-hard, On a class of optimization problems with no ``efficiently computable solution, Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries, Tractability of batch to sequential conversion, Circuit lower bounds from learning-theoretic approaches, Monomials, multilinearity and identity testing in simple read-restricted circuits, Memory-constrained algorithms for simple polygons, An algebraic proof of the real number PCP theorem, Parameterized complexity classes beyond para-NP, Constructing small tree grammars and small circuits for formulas, The unbearable hardness of unknotting, High-resolution schemes for stochastic nonlinear conservation laws, Uniform proofs of ACC representations, Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits, Fixed-parameter tractability of crossover: steady-state GAs on the closest string problem, Zero knowledge and circuit minimization, Localising iceberg inconsistencies, Four Soviets walk the dog: improved bounds for computing the Fréchet distance, The effect of combination functions on the complexity of relational Bayesian networks, Exact solutions in low-rank approximation with zeros, On path ranking in time-dependent graphs, Feature selection and disambiguation in learning from fuzzy labels using rough sets, Circuit complexity for free fermions, The complexity of comparing optimal solutions, Isomorphism testing of read-once functions and polynomials, Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science, Machines that perform measurements, A computation model with automatic functions and relations as primitive operations, Long-distance Q-resolution with dependency schemes, Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS, Time evolution of complexity: a critique of three methods, Invited talks, A fresh look at research strategies in computational cognitive science: the case of enculturated mathematical problem solving, Naturalism, tractability and the adaptive toolbox, Complexity of manipulative interference in participatory budgeting, Extension-based semantics for incomplete argumentation frameworks, Some \(0/1\) polytopes need exponential size extended formulations, Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms, An automaton group with \textsf{PSPACE}-complete word problem, Mixed state information theoretic measures in boosted black brane, Decision-theoretic troubleshooting: hardness of approximation, Contracting graphs to paths and trees, Computation of the random arrival rule for bankruptcy problems, The price of query rewriting in ontology-based data access, Hardness results for approximate pure Horn CNF formulae minimization, Easy solutions for a hard problem? The computational complexity of reciprocals with quantificational antecedents, Computational power of one-way Turing machines with sublogarithmic memory restrictions, On expressive power of regular realizability problems, A complexity theory for hard enumeration problems, More on complexity in finite cut off geometry, THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA, Approximate Moore graphs are good expanders, Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs, Design and results of the second international competition on computational models of argumentation, Quantum computing with octonions, Natural Proofs versus Derandomization, The computational complexity of Angry Birds, Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits, Three-Player Entangled XOR Games are NP-Hard to Approximate, Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields, Improved Space Efficient Algorithms for BFS, DFS and Applications, On Hard Instances of Non-Commutative Permanent, Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs, Long Distance Q-Resolution with Dependency Schemes, The expressiveness of looping terms in the semantic programming, On hard instances of non-commutative permanent, Exact recovery in the hypergraph stochastic block model: a spectral algorithm, Geometric complexity theory V: Efficient algorithms for Noether normalization, Random resolution refutations, Verification of quantum computation: an overview of existing approaches, Polynomial size linear programs for problems in \textsc{P}, Logical language of description of polynomial computing, Space complexity of reachability testing in labelled graphs, A certain family of subgroups of \(\mathbb{Z}_{n}^{\star}\) is weakly pseudo-free under the general integer factoring intractability assumption, A multiparametric view on answer set programming, Explicit two-source extractors and resilient functions, Estimating the probability of meeting a deadline in schedules and plans, Space efficient linear time algorithms for BFS, DFS and applications, Interactive proofs and a Shamir-like result for real number computations, Book Review: Inevitable randomness in discrete mathematics, A survey on the problems and algorithms for covering arrays via set covers, Function simulation, graph grammars and colourings, Fixed-parameter complexity and approximability of norm maximization, Ultra-weak solutions and consistency enforcement in minimax weighted constraint satisfaction, On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy, A higher-order characterization of probabilistic polynomial time, Constructing NP-intermediate problems by blowing holes with parameters of various properties, On the Computable Theory of Bounded Analytic Functions, Fooling-sets and rank, Mining circuit lower bound proofs for meta-algorithms, Computational barriers in minimax submatrix detection, Monomials in arithmetic circuits: complete problems in the counting hierarchy, Complexity of tropical and MIN-plus linear prevarieties, On optimal language compression for sets in PSPACE/poly, The PCP theorem for NP over the reals, Low-Rank Tucker Approximation of a Tensor from Streaming Data, Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata, The Untold Story of $$\mathsf {SBP}$$, A Short Introduction to Implicit Computational Complexity, Uniqueness of optimal randomized algorithms for balanced AND-OR trees, The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems, Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas, Fast Heuristics and Approximation Algorithms, Quantum Locally Testable Codes, New Limits to Classical and Quantum Instance Compression, The Journey from NP to TFNP Hardness, The stochastic thermodynamics of computation, On the Equivalence among Problems of Bounded Width, Combining Model Checking and Deduction, Geometry and Combinatorics via Right-Angled Artin Groups, Timed Sets, Functional Complexity, and Computability, Studies in Computational Aspects of Voting, Boolean Game with Prioritized Norms, On the Complexity of Input/Output Logic, Quantified Derandomization: How to Find Water in the Ocean, Multi-Valued Reasoning about Reactive Systems, A Survey of Compressed Sensing, On computational complexity of construction of c -optimal linear regression models over finite experimental domains, State complexity and quantum computation, Wasserstein Barycenters Are NP-Hard to Compute, Interval Linear Algebra and Computational Complexity, Squeezing Feasibility, Nonuniform ACC Circuit Lower Bounds, Quantum machine learning: a classical perspective, Computational tameness of classical non-causal models, Computational Complexity of Biased Diffusion-Limited Aggregation, Complexity of Equivalence and Learning for Multiplicity Tree Automata, Short Presburger Arithmetic Is Hard, Exact and Heuristic Algorithms for Semi-Nonnegative Matrix Factorization, Some Results on Interactive Proofs for Real Computations, Lower Bounds for the Size of Nondeterministic Circuits, Unnamed Item, The Fewest Clues Problem of Picross 3D, STRICT FINITISM, FEASIBILITY, AND THE SORITES, Collapsing modular counting in bounded arithmetic and constant depth propositional proofs, Restricted Power - Computational Complexity Results for Strategic Defense Games, Strong Inapproximability of the Shortest Reset Word, On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape, The Ehrenfeucht-Fraïssé Method and the Planted Clique Conjecture, On the Structure of Solution-Graphs for Boolean Formulas, Minimisation of Multiplicity Tree Automata, Unnamed Item, On the Variable Hierarchy of First-Order Spectra, Smallest Formulas for Parity of 2 k Variables Are Essentially Unique, Unnamed Item, Families of graphs with twin pendent paths and the Braess edge, Unnamed Item, Unnamed Item, Quantum circuits and low-degree polynomials over ${{\mathbb{F}}_\mathsf{2}}$, Ontology-Mediated Query Answering with Data-Tractable Description Logics, On quantum lambda calculi: a foundational perspective, The Complexity of Complexity, Unnamed Item, On the locality of arb-invariant first-order formulas with modulo counting quantifiers, Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups, Unnamed Item, Unnamed Item, A Complete Characterization of Unitary Quantum Space, Location of zeros for the partition function of the Ising model on bounded degree graphs, AI-Completeness: Using Deep Learning to Eliminate the Human Factor, Distributed Multi-authority Attribute-Based Encryption Using Cellular Automata, Depth Reduction for Composites, Rényi entropies as a measure of the complexity of counting problems, On Pseudodeterministic Approximation Algorithms., A Framework for In-place Graph Algorithms, NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth, Planarity Testing Revisited, An Introduction to Randomness Extractors, POWER CIRCUITS, EXPONENTIAL ALGEBRA, AND TIME COMPLEXITY, Feasibility and Infeasibility of Adaptively Secure Fully Homomorphic Encryption, Cryptography Using Captcha Puzzles, Unnamed Item, Unnamed Item, Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems, Parallel identity testing for skew circuits with big powers and applications, A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem], Anderson localization makes adiabatic quantum optimization fail, Algebraic cryptography: new constructions and their security against provable break, Definable Inapproximability: New Challenges for Duplicator, Universality, Invariance, and the Foundations of Computational Complexity in the Light of the Quantum Computer, Succinct Algebraic Branching Programs Characterizing Non-uniform Complexity Classes, Quantum control with noisy fields: computational complexity versus sensitivity to noise, Unnamed Item, ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION, Coded Circuit for Trusted Computing: Towards Dynamic Integrity Measurement, Unnamed Item, On Khot’s unique games conjecture, Bayesian Decision Making in Groups is Hard, COMPLEXITY OF SHORT GENERATING FUNCTIONS, Localizing differentially evolving covariance structures via scan statistics, Primitive Sets of Nonnegative Matrices and Synchronizing Automata, On the Complexity of Inverse Mixed Integer Linear Optimization, Unnamed Item, Introduction to local certification, The Inverse of Ackermann Function is Computable in Linear Time, 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, Streaming graph computations with a helpful advisor, Strong continuous non-malleable encoding schemes with tamper-detection, On NP-hard graph properties characterized by the spectrum, How strong is Nisan's pseudo-random generator?, On one-step worst-case optimal trisection in univariate bi-objective Lipschitz optimization, Towards implementation of a generalized architecture for high-level quantum programming language, Parameterized random complexity, Small space analogues of Valiant's classes and the limitations of skew formulas, Catalytic space: non-determinism and hierarchy, Knapsack in graph groups, Robust classification via MOM minimization, 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, Narrow big data in a stream: computational limitations and regression, A structured view on weighted counting with relations to counting, quantum computation and applications, A hierarchy of local decision, Approximate inference in Bayesian networks: parameterized complexity results, On the number of integer points in translated and expanded polyhedra, A parameterized algorithmics framework for degree sequence completion problems in directed graphs, On the complexity of the Leibniz hierarchy, On the computational complexity of data flow analysis over finite bounded meet semilattices, Frameworks for designing in-place graph algorithms, Coloring invariants of knots and links are often intractable, First-order rewritability of ontology-mediated queries in linear temporal logic, Committing to correlated strategies with multiple leaders, Hamiltonicity via cohomology of right-angled Artin groups, The complexities of nonperturbative computations, 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, The complexity of computing a (quasi-)perfect equilibrium for an \(n\)-player extensive form game, Lee-Yang theorems and the complexity of computing averages, On the approximability of robust network design, Better complexity bounds for cost register automata, Recovering nonuniform planted partitions via iterated projection, Quantum computation with write-only memory, 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, 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, On the hardness of covering-interdiction problems, Weighted automata are compact and actively learnable, Complexity of deciding detectability in discrete event systems, On \textsf{NC} algorithms for problems on bounded rank-width graphs, 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 \((\max,+)\) 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
