# All Questions

12,970 questions
Filter by
Sorted by
Tagged with
4k views

### Why isn't TheoretiCS very popular yet?

(My question is probably badly formulated, sorry for this.) TheoretiCS is an overlay journal in Theoretical CS (hence charge-free and in full open access), launched two years ago. From my point of ...
• 509
102 views

### Maximum cardinality disjoint cycle cover in undirected graphs

I call a maximum cardinality disjoint cycle cover of a graph a vertex-disjoint cycle cover containing the maximum possible number of cycles in the graph. What is known about the complexity of this ...
• 828
78 views

### State machine classes with sub-exponentially growing model spaces

State machines are useful tools for system modelling. They allow for a compact visual notation of discrete systems and provide a formal model of them. However, reasoning about the correctness of an ...
919 views

### Status of András Faragó’s (second) claimed proof that NP=RP

In 2020, András Faragó claimed to have proved that NP = RP (discussion; v1 of the paper); the paper was later retracted due to a counterexample to theorem 1. A few days ago, Faragó posted another ...
• 133
486 views

### Trade-off for Barrington's theorem

Barrington's theorem states that any Boolean circuit made up of gates of fan-in $2$ and with depth $d$ can be transformed into an equivalent Branching Program of constant width (in particular, of ...
• 3,712
90 views

### What's the complexity of the "decision version" of counting the paths in a graph?

I learned that "counting the simple paths in a graph(whether directed or not)" is #P-Complete. I'm wondering what the complexity is for its decision version. Here are two types I'm ...
61 views

### Is there an algorithm that finds a minimum vertex cover with an approximation factor of 3/2 for a planar graph?

Is there an algorithm that finds a minimum vertex cover with an approximation factor of 3/2 for a planar graph?
1 vote
108 views

### A variant of the generalised assignment problem

I am trying to solve this problem: There are $N$ workers and $T$ tasks. Each task can be assigned to at most one worker. Each worker can be assigned any number of tasks. The profit obtained by ...
77 views

### Is there a text that contains all 4 Büchi-Elgot-Trakhtenbrot-style theorems?

There are several natural Büchi-Elgot-Trakhtenbrot-style theorems: The equivalence of various finite automata on finite words and the weak monadic second order theory of 1 successor The equivalence ...
• 489
46 views

### Is it possible to estimate the positive outcomes of a boolean function using an optimized version of Goldreich-Levin?

Let $\mathcal{X} = \{-1,1\}^n$ and $h: \mathcal{X} \to \{-1,1\}$, h can be expanded in the basis of monomials for the uniform distribution, or also can have a distribution free expansion (Gram-Schmidt ...
• 65
88 views

### On mod $2^i$ $+$-reducibility of permanent

Suppose we have two bipartite graphs $G_1$ and $G_2$ with perfect matching count $P_1$ and $P_2$ respectively then their disjoint union gives a bipartite graph with perfect matching $P_1P_2$. Is ...
• 13k
103 views

### Maximum theoretical compression ratio for real-valued data

Given a sequence of $N$ real-valued vectors $\mathbf{v_1}, \mathbf{v_2}, ..., \mathbf{v_N}$, each of dimension $d$, do any of the below bounds exist? The minimum number of real-valued vectors of ...
1 vote
72 views

### Properties of #P functions that a GapP function may violate

I want to show a specific GapP problem is likely not in #P, actually very closely related to this question in terms of the area of mathematics it is from: How can I show a Gap-P problem is outside #P ...
• 111
59 views

### How to prove that all pairwise independent hashing circuits are superconcentrators?

It is mentioned in Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates, A. Gal et al. that "it is also not hard to show that (pairwise-independent) ...
235 views

### Richard Feynman says that all quantum procedures are able to be simulated by quantum computation

Richard Feynman says that all quantum procedures are able to be simulated by quantum computation，but his argument is not rigid, it seems to be a conjecture. Is there any physics/math argument ...
• 1,079
658 views

### Example of a term in system F which is not typable in the simply typed lambda calculus

What is the simplest possible example of a (correctly typed) term in system F that does not correspond to any correctly typed term in the simply typed λ-calculus? More precisely, I am looking for a ...
• 841
119 views

### Is beta normalization used for program optimization?

Beta normalization reduces a lambda term to its beta normal form, if it exists. The beta normal form is a computationally equivalent term with no "redundant" computation, in a sense; for ...
• 105
180 views

### Is there a lower bound for the problem of finding the best straight line partition

I recently asked the following algorithms question on another site. The best answer so far is $O(n^4)$ time. The input is of size $O(n^2)$ and the output is just a number so I was wondering if there ...
• 3,902
76 views

### What is $\mathrm{NC}^0$-uniform reduction

I am interesting in strict and right'' formulations of results about $\mathrm{NC}^1$-completeness of some languages. Consider for example Barrington's theorem about $\mathrm{NC}^1$-completeness of ...
• 2,013
157 views

### Is there a high level (functional) language compiling to Mixed Integer Linear Programming problems?

Many different kinds of optimization problems can be expressed as Mixed Integer Linear Programming (MILP). The translation is usually very direct, and one has to encode invariants as constraints in a ...
• 626
113 views

### Why does there not exist an oracle $A$ such that $EXP^{A} = P^{A}$?

I have been trying to find an argument, but with no success so far. My understanding is that if I can choose $A$ to be an $EXP-complete$ language, then I can simply reduce any other problem to that ...
149 views

• 158
898 views

### Intuitive explanation of the fact that the Calculus of Constructions is not conservative over Higher-Order Logic

Reading Barendregt's chapter “Lambda Calculi with Types” in the Handbook of Logic in Computer Science (vol. 2: Computational Structures) (Abramsky, Gabbay & Maibaum eds., 1992) I learned (op. cit. ...
• 841
253 views

• 1,337
89 views

### Application of PCP and error correcting codes to LLMs?

Are there any interesting results in applying error correcting codes and ideas from PCP (Probabilistically Checkable Proofs) to improve the quality of large language models (LLM), or connecting them ...
• 21.7k
37 views

### definition of P-samplable distribution that allows non-binary fractions

Arora and Barak (in chapter 18, on average-case complexity) define a polynomial-time samplable (or P-samplable) distribution $D$ (actually a family $\{D_n\}$, for each output length $n$) as having an ...
508 views

### Deciding whether a convex region is empty

Let $S\subseteq \mathbb{R}^n$ be a convex region defined by $$g_i(x)\leq 0, ~~i\in 1,\ldots,m,$$ where $g_i$ are convex functions. The goal is to decide whether $S$ is empty, and if not - find a point ...
• 2,262
82 views

### Description of the CPS transformation for the typed lambda-calculus

Is there somewhere a precise but hopefully readable account of how the CPS (=continuation-passing-style) transformation applies to the typed lambda-calculus? (Say, simply-typed with product and sum ...
• 841
141 views

### Complexity of simplex method

What is the complexity of the simplex method in terms of Big O in the general case? I saw two variants: O(2^n) and O(2^(n+m)), where n is the number of variables and m is the number of constraints
95 views

### Complexity of Identifying SAT Problems with a Unique Solution from Satisfiable Instances

I am curious about the computational complexity involved in identifying SAT problems that have only one solution from a set of satisfiable SAT instances. input and output: input: A satisfiable cnf ...
• 316
264 views

### What's wrong with this $P \neq BPP$ proof?

I developed this simple argument while learning about the $BP$ operator and McCreight and Meyer's Union Theorem, however I cannot pinpoint where my error is. By the Union Theorem, there exists a total ...
75 views

### Categorical consequences in practical algorithms outside type theory

Most of my exposure to using categorical results to design algorithms, is through modularity in functional programming. I am wondering whether there are examples where the proof of existence of ...
• 920
46 views

### Resources for informatics olympiads and acm icpc competitions?

Recently I am learning c++ programming language. I wanted to know some resources where I can get problems and theories related to acm icpc competition and informatics olympiads . Also can anyone tell ...
• 101
158 views

### If I want to end math, where should I start?

I'm a PhD in math, but I'm not good. I'm familiar with Riemannian geometry, a little partial differential equations, and a little algebraic topology. And the other undergraduate courses of math (I ...
83 views

### Extending Karp Reductions of a Decision Problem to Cook Reductions of the Associated Counting Problem

It seems that most NP-complete decision problems have #P-complete corresponding counting problems, with many examples showing this and no known counterexamples. In Jerrums' lecture notes `Counting, ...
107 views

### How to properly learn when there is random classification noise?

The following problem is motivated by the one here from more than half a decade ago: Let $C$ be a concept class that is efficiently proper PAC-learnable, i.e. there exists a learning algorithm that ...
214 views

### A variation of propositional pigeonhole principle

Let $n$ be the number of pigeons, and $x_{i,j}$ denote the Boolean variable indicating that pigeon #$i$ is mapped to hole #$j$. Then the propositional pigeonhole principle (PHP) is the conjunction of ...
• 187