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)$? | |