Topic: Theoretical Computer Science

Recent Tags

ac0 advice-and-nonuniformity advice-request agda algebra algebraic-complexity application-of-theory applicative approximation approximation-algorithms approximation-hardness ar.hardware-architecture arithmetic-circuits asymptotics authorship automata-theory automated-theorem-proving average-case-complexity big-list big-picture binary-decision-diagrams bipartite-graphs black-box board-games boolean-formulas boolean-functions boolean-matrix bounded-depth cache-oblivious calculus-of-constructions cc.complexity-theory cg.comp-geom chernoff-bound circuit-complexity circuit-families clique co.combinatorics coding-theory combinatorics communication-complexity compilers complexity complexity-classes computability computable-analysis computational-geometry concurrency conditional-results conferences constructive-mathematics context-free context-free-languages continuations convex-geometry convex-hull convex-optimization coq counter-automata counting-complexity covering-problems cr.crypto-security cryptojacking ct.category-theory curry-howard data-streams db.databases dc.distributed-comp dc.parallel-comp decidability decision-trees definitions denotational-semantics dependent-type derandomization descriptive-complexity directed-acyclic-graph domain-theory ds.algorithms dynamic-algorithms edit-distance embeddings encoding enumeration epsilon-nets equivalence examples exp-time-algorithms factoring finite-fields fixed-parameter-tractable fl.formal-languages formal-methods formal-modeling fourier-analysis fractals functional-programming grammars graph-algorithms graph-classes graph-colouring graph-drawing graph-isomorphism graph-minor graph-theory halting-problem haskell heuristics hierarchy-theorems high-dimensional-geometry ho.history-overview homotopy-type-theory imperative-programming implementation independence inductive-type integer-programming interaction-nets interactive-proofs it.information-theory iterated-rounding lambda-calculus lattice lg.learning linear-algebra linear-logic linear-programming linear-temporal-logic lo.logic logic-programming logspace lower-bounds machine-learning machine-models markov-chains matching matrices max-flow-min-cut minimization modal-logic model-checking model-theory monad mu-calculus na.numerical-analysis natural-computing near-neighbors nexp ni.networking-internet nondeterminism normalization notation np np-complete np-hardness np-intermediate nt.number-theory object-oriented omega-language operational-semantics optimization oracles p-vs-np pac-learning paper-review parameterized-complexity parametricity parsing pcp permanent permutations petri-nets physics pi-calculus pl.programming-languages polymorphism polynomial-hierarchy polynomial-time polynomials polytope pr.probability primal-dual primes privacy probabilistic-computation process-algebra program-logic program-verification project-topic promise-problems proof-assistants proof-complexity proof-techniques proof-theory proofs property-testing pseudorandom-generators pseudorandomness pspace puzzles qma quantum-computing quantum-information query-complexity random-graphs random-oracles randomized-algorithms randomness recursion reductions reference-request regular-expressions regular-language relativization research-practice sample-complexity sat search-problem security semantics semidefinite-programming separation set-theory shannon-entropy simplex soft-question software sorting sorting-network space-bounded space-time-tradeoff sparse-matrix st.statistics stochastic-process streaming streaming-algorithms structural-complexity submodularity sum-of-squares survey symmetry temporal-logic term-rewriting-systems terminology time-complexity topology tree treewidth turing-machines type-inference type-systems type-theory typed-lambda-calculus unary-languages undecidability unique-solution universal-computation universal-turing-machines upper-bounds vc-dimension writing zero-knowledge

Recent Articles

Randomized communication complexity of or-of-equalities

Quadratic lower bound

Hardness of a class of quadratics

Hardness of a class of quadratics

Best known algorithm for NEXP-complete problem

Similarities and differences between Pie and popular languages with dependent types

Is there FPT or XP algorithms knowm for Shortest Steiner cycle and $(a,b)$-Steiner path problem

Question about algorithm for enumerating minimal AB-separators

Sample complexity lower bound to learn the mode (the value with the highest probability) of a distribution with finite support

What are the application of Scott-Topology in theoretical computer science?

Are there survey papers in theoretical computer science?

Complexity of the Complete (3,2) SAT problem?

Are there 'poision-pill' research questions in TCS?

Can you always throw away the types when evaluating lambda expressions?

Does double majoring with math in undergrad help one grasp TCS topics more easier?

Tensor network contraction "bubbling": why are some approaches more computationally efficient than others (question from a beginner)

How to find the size of an ϵ-net of a vector space?

Complexity of matrix diagonalization

Parameterized complexity of Hitting Set with slightly bigger parameter

$\mathrm{AC}^0$ upper bound for Hamming weight

From CHSH inequality to CHSH game

Upper bound for VCdim of $H$ in terms of subgraph$(F)$, where $H := \{S(f) | f \in F\}$, with $S(f) := \{(x,y) \in X \times \{\pm 1\} | yf(x) \le 1\}$

How to show that the median cannot be maintained in $O(1)$ time?

Maximize a special monotone submodular function - is it easier?

Operations on Sentential Decision Diagrams

Words of the form $(a^n b)^n$ in a context-free language

Efficient transformation into CNF preserving entailment

Restriction of a convex function to {0, 1}^n

Maximal uniquely decodable codes

VC-dimension of the infinite intersection of two spheres

Is Permanent $+$-reducible?

Treewidth relations between Boolean formulas and Tseitin encodings

No free lunch theorem

Extracting coefficients of polynomials given by straight line programs

Proving a property of minimal st-separators that are not minimum st-separators

Word equations with integer parameters

Nontrivial Algorithms for Coloring (Parameterized by Pathwidth)

Maximum flow with parity requirement on certain edges

Another variation of $k$-means problem in the plane

Is the weighted sum of subset prefix product problem NP-hard?

Parameterized algorithm when the parameter is not known in advance?

Is there an approximate version of the strong duality theorem for linear programming?

How do we use directed univalence in directed type theory?

$AC^0$[subexp] vs. NC

Name for words without squared symbols

Binary Trees for Nearest Neighbor Search

Eliminating tautological axioms in tree-like $k$-DNF resolution

Maximum Vertex Cover

"Spurious" Type Equivalences in MLSub/Algebraic Subtyping

Why does it matter how difficult a proof is?

Intuitive way to handle variable binding

Is there a way to define dependent types without explicit substitutions internally within agda?

The complexity of 3SAT

Proof of SPFA's worst-case complexity?

Is there a simplex-like algorithm that can be used with a separation oracle?

Why can't opaque optics form a category?

Is there an Upper Bound on Number of Redundant Clauses in a satisfiable $3-SAT$?

Hardness assumption: an NP-complete problem whose ratio of hard instances do not tend to zero?

Separating 2-SAT from Clique

What's the logical counterpart to jumps with arguments on CPS terms?

How to show that Color Tiles is NP-Complete

2-Center problem with forbidden pairs

Randomized algorithms not based on Schwartz-Zippel

Is every 4-colourful Eulerian Orientation of a planar 4-regular graph good?

Validity problem of intuitionistic two-variable logic

Swapping arguments of variables in higher-order pattern unification

Deterministic communication complexity of refinement

Alternative to LBA for recognising context-sensitive languages

Set cover with rewards

What are the issues with a set-like interpretation of quantifiers in type theory?

3-SAT runtime if an optimal order to eliminate possible solutions is known

Can a normal form term be extensionally equivalent to a term with no WHNF?

Differential privacy definition: subset of range of values vs. equals a value in the range

Reference request for linear algebra over GF(2)

Type theory and fixed points of datatypes

A counter example for the set mean objective

Construction of arbitrary functions with exponential-size $MODp \circ MODq$ circuits

Parameterized complexity of tree/branch decomposition

Can this NP-hardness proof for Super Mario Brothers (and other games) be simplified?

Q: Trusting program output from an untrusted machine

Full names of C. K. Chow and C. N. Liu

Complexity of reachability in directed rooted forests

Effect of HoTT/Univalence Axiom on equality between terms of inductive types?

Hardness of computing the dimension of an integral polytope?

Reference request: An algebraic characterisation of LTL[XF]-definable word languages

Young Diagrams and distinguishing between two distributions

Complexity of NFA to DFA minimization with binary threshold

Does abundance of max cliques make it easy to solve COLORABILITY?

Can we approximate the number of words accepted by an NFA?

Is there an isomorphism between universal domains $\mathcal{P}\omega$ and the interval domain $\mathbf{I}\mathbb{R}$?

How can we compute the VC dimension of a finite class of sets?

What is the general definition of 'extensionality' in type theory and how is extensionality defined for positive types?

Finding a path in a graph hitting a particular vertex

Complete problem in $\Sigma_2^p$ - $\Sigma_{2}SAT$

Lower bound for the OR problem

star height of star-free languages

Are there an algorithm that find Minimum spanning tree in $O(n^2\log\log^*n)$?

exact path cover for undirected graph

Regular Expressions that converts into unambiguous automata

Status of certain problems in knot theory