All Questions

Filter by
Sorted by
Tagged with
20 votes
2 answers
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 ...
sparusaurata's user avatar
2 votes
1 answer
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 ...
delete000's user avatar
  • 828
2 votes
2 answers
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 ...
stateMachineOperator's user avatar
12 votes
1 answer
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 ...
Jiak Kantang's user avatar
12 votes
1 answer
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 ...
Michael Lampis's user avatar
3 votes
0 answers
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 ...
Wenhao Wu's user avatar
0 votes
0 answers
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?
John Stuart's user avatar
1 vote
1 answer
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 ...
Michael C.'s user avatar
2 votes
0 answers
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 ...
TomKern's user avatar
  • 489
0 votes
0 answers
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 ...
rivana's user avatar
  • 65
0 votes
0 answers
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 ...
Turbo's user avatar
  • 13k
0 votes
1 answer
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 ...
Susmit Agrawal's user avatar
1 vote
0 answers
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 ...
Matt Samuel's user avatar
5 votes
0 answers
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) ...
Kagura Hitoha's user avatar
-3 votes
1 answer
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 ...
XL _At_Here_There's user avatar
7 votes
3 answers
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 ...
Gro-Tsen's user avatar
  • 841
2 votes
1 answer
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 ...
Hirrolot's user avatar
  • 105
4 votes
1 answer
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 ...
Simd's user avatar
  • 3,902
3 votes
0 answers
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 ...
Alexey Milovanov's user avatar
3 votes
1 answer
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 ...
Turion's user avatar
  • 626
0 votes
1 answer
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 ...
Meki21's user avatar
  • 3
3 votes
2 answers
149 views

An upper bound of pseudo-/VC-dimension

Let $\mathcal{F}\subseteq \left\{f:\mathbb{R}^d\to\mathbb{R}\right\}$ be a family of functions with bounded pseudo-dimension $\text{Pdim}(\mathcal{F})\le N$, i.e., the VC-dimension $\text{VCdim}(\left\...
Recursion's user avatar
0 votes
0 answers
58 views

Implications of NL $\subseteq$ BQL/poly

As far as I could see it's not known whether NL $\subseteq$ BQL/poly. Is it actually not known? If not, what would be the implications of the inclusion?
eunice.goudarzi's user avatar
7 votes
1 answer
218 views

Counting the different subsets of nodes seen when iterating a subset through a directed graph

For a given directed graph $G = (V, E)$ (possibly with loops), and some $S\subseteq V$ define the operation $G(S) = \{ v\mid (u,v)\in E\text{ for some } u\in S \}$. Now consider the infinite sequence $...
alsips-cl's user avatar
  • 158
10 votes
1 answer
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. ...
Gro-Tsen's user avatar
  • 841
7 votes
1 answer
253 views

Are regular expressions polynomially decomposable?

This question is related to my previous question (LINK). I would like to ask whether regular expressions can be polynomially decomposed in the following sense: A regular expression $\mathcal{R}$ is $...
Bartosz Bednarczyk's user avatar
10 votes
1 answer
351 views

The complexity of conversion from a regular expression to a nondeterminsitic automata and back after changing initial and final states

Suppose that a regular expression $\mathcal{R}$ over an alphabet $\Sigma$ is given. It is well-known that one can now construct a non-deterministic finite automaton $\mathcal{A}$ such that $\mathcal{R}...
Bartosz Bednarczyk's user avatar
3 votes
1 answer
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 ...
Kaveh's user avatar
  • 21.7k
2 votes
0 answers
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 ...
Shivaram Lingamneni's user avatar
4 votes
1 answer
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 ...
Erel Segal-Halevi's user avatar
4 votes
0 answers
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 ...
Gro-Tsen's user avatar
  • 841
0 votes
1 answer
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
Kitty's user avatar
  • 1
0 votes
0 answers
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 ...
Jxb's user avatar
  • 316
5 votes
0 answers
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 ...
trillianhaze's user avatar
2 votes
0 answers
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 ...
Ilk's user avatar
  • 920
0 votes
0 answers
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 ...
Sillyasker's user avatar
-4 votes
1 answer
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 ...
Enhao Lan's user avatar
2 votes
0 answers
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, ...
space_kale's user avatar
0 votes
1 answer
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 ...
user avatar
4 votes
1 answer
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 ...
Soha's user avatar
  • 187
0 votes
0 answers
57 views

word2vec: vectors or projective vectors?

In "Efficient Estimation of Word Representations in Vector Space" Mikolov et.al argue that any mapping of words into vectors should satisfy approximate constraints, such as $vector(''Paris'')...
Tegiri Nenashi's user avatar
0 votes
0 answers
33 views

Nonlinear GAP similar to Min-GAP but with minimum quantities and without capacity

I have $m$ items and $n$ bins where each item $i$ and bin $j$ has a value $v_{i,j}$. Each bin $j$ has a value $V_j$. I want to pack the items into the bins such that (1) I minimize the ratio of the ...
Jika's user avatar
  • 115
4 votes
1 answer
157 views

Are there any problems in $\mathsf{BPP}$ that are known to be $\mathsf{RP}$-hard or $\mathsf{coRP}$-hard?

It's suspected that probabilistic complexity classes such as $\mathsf{RP}$ or $\mathsf{BPP}$ don't have complete problems. Of course, their promise counterparts have complete problems, but I am not ...
rus9384's user avatar
  • 355
3 votes
0 answers
155 views

Is it possible to recover the set of derivation trees of a fact from its semiring provenance in Datalog?

Background: In the context of Datalog, Green et. al (2007) introduce the notion of the Datalog provenance semiring, a generalization of why-provenance as well as bag and probabilistic database ...
Justin Lubin's user avatar
6 votes
0 answers
173 views

Variation of (derandomized) Valiant-Vazirani

I am interested in the following "improvement" of the Valiant-Vazirani reduction. As pointed out here, under the right derandomization assumptions one can obtain a deterministic polynomial-...
Noel Arteche's user avatar
1 vote
0 answers
71 views

Hardness for find the clause for statisfiable 3-SAT problems

The 3-SAT problems are known to be NP-complete so the decision problems are believed to be non efficiently solvable unless P=NP. Yet, there are cases where the satisfiability can be answered such as ...
ironmanaudi's user avatar
3 votes
1 answer
188 views

How often can a clause cause a conflict?

This question is about DPLL+CDCL algorithms. How often can a clause cause a conflict? I want to use a specific algorithm. Assume a DPLL+CDCL SAT solver using a fixed variable order. Variables and unit ...
Russell Easterly's user avatar
1 vote
0 answers
45 views

Find the SVM kernel in detecting if a substring in a given string

Consider the task of learning to find a sequence of characters ("signature") in a file that indicates whether it contains a virus or not and let $\mathcal{X}$ be the set of all finite ...
Tran Khanh's user avatar
8 votes
1 answer
486 views

What can we do with a generic oracle (as opposed to a random one)?

Let me first recall a few (lengthy but hopefully mostly standard) facts and definitions in order to motivate my question (feel free to skip down to the actual question): Standard definitions: A ...
Gro-Tsen's user avatar
  • 841
5 votes
2 answers
242 views

Can CDCL Algorithm Derived Conflict Clauses Always Be Obtained Through Resolution from an Unsatisfiable CNF Formula?

I have a question regarding the Conflict-Driven Clause Learning (CDCL) algorithm applied to an unsatisfiable CNF formula $F$. Specifically, can all the conflict clauses learned by the CDCL algorithm ...
Jxb's user avatar
  • 316

15 30 50 per page
1
5 6
7
8 9
260