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 cv.computer-vision 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 ds.data-structures 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 gr.group-theory grammars graph-algorithms graph-classes graph-colouring graph-drawing graph-isomorphism graph-minor graph-theory gt.game-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-knowledgeRecent Articles
Dependent type theory and definitions of cumulativity | |
Expected number of random comparisons needed to sort a list | |
Defining normalization with respect to judgmental equality instead of reduction | |
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)$? | |