All Questions

Filter by
Sorted by
Tagged with
0 votes
1 answer
49 views

Selecting unique records from a large dataframe with many duplicate records

Suppose we have a dataframe with ~10M rows with ~9M duplicate records. What is the most time efficient way of selecting the unique records from this dataframe? Some sort of sampling algorithm?
user avatar
0 votes
0 answers
33 views

PAC guarantees for linear prediction under the squared loss

I am looking for generalisation bounds under the squared loss, specifically for the class $\mathcal{F}_{\text{lin}} = \{f(x) = \langle w, x \rangle : \|w\| \leq C\}$ of bounded linear predictors. I am ...
user avatar
1 vote
1 answer
151 views

Hardness of a class of quadratics

I have a system of inequalities of the form $x_i^2 \le x_j$ with $x_i = a_i + \sum_j \alpha_j b_{i,j}$, the variables are $x_i,\alpha_i$, the values $a_i, b_{i,j} \ge 0$ are known and all $x_i, a_i, \...
user avatar
1 vote
0 answers
126 views

Can NP-complete language be in $mP/poly$?

Can NP-complete language be in monotone $P/poly$?
user avatar
  • 111
0 votes
0 answers
49 views

Publications on left recursion and PCRE regex engine

Is there any paper (or at least technical report / preprint or even thesis) mentioning that regex engines cannot match expressions that contain "left recursion" (explained below)? I am ...
user avatar
-2 votes
1 answer
101 views

Can a Turing machine quickly move to any position of a large string?

I hope this question is not too basic and I am not missing something dumb. But suppose we simulated a Turing machine on a long string $s$, where $|s| = 10^{100}$ for example. Then if we wanted to ...
user avatar
9 votes
2 answers
356 views

O(n)-space, polylog-time subtree sums in incremental forests?

Consider a forest $G$ of $n$ vertices $v_1, \dots, v_n$ arranged left to right with edges from child to parent always going to the left, i.e. if the parent of vertex $v_i$ is $v_j$, then $j < i$. ...
user avatar
2 votes
2 answers
192 views

What is the computational power of the Calculus of Constructions?

The calculus of constructions (CoC) without fix is clearly not Turing complete, as the program that loops infinitely cannot be expressed in it. What I'm wondering: ...
user avatar
0 votes
0 answers
94 views

How far easier is Boolean matrix multiplication, compared to matrix multiplication?

It is obvious that boolean matrix multiplication can be solved in $O(n^\omega)$, as a simple variant of regular matrix multiplication. I saw a recent paper solving boolean matrix multiplication in $O(...
user avatar
0 votes
1 answer
83 views

Is "choosability of subsets" NP-hard?

Let $n\in\mathbb{N}$ be a positive integer, and let ${\cal A}$ be a collection of subsets of $n=\{0,\ldots,n-1\}$. We say ${\cal A}$ has the choosability property if there is $R\subseteq n$ such that $...
user avatar
0 votes
1 answer
93 views

What is a "Covering Function"?

In Idris2, I will sometimes get an error telling me that a function "is not covering", which is apparently distinct from it not being total (and I do understand what a total function is). I ...
user avatar
6 votes
1 answer
293 views

Lower-bounds under SETH

After reading a bit about SETH (the strong exponential time hypothesis), I see that a lot of lower bounds for problems in P can be proven if we assume SETH. But I notice that most of the ones that are ...
user avatar
  • 161
0 votes
0 answers
56 views

Interesting statistical experiment concerning data compression

I want to present the following statistical experiment concerning data compression, on which I will ask you to predict the result obviously justifying the choice made. The statistical experiment is ...
user avatar
  • 1
5 votes
0 answers
96 views

Data structures to store monotone functions

I am looking for approaches storing strictly increasing natural-valued functions defined on a (subset of) $[0..N]$: $$ \forall x \in X: 0 \le x \le N\\ f: X \to \mathbb N\\ \forall x,y\in X:\quad x<...
user avatar
8 votes
0 answers
119 views

Does NP Completeness always fall on one side or the other of an intermediate computation?

Let $L$ be an NP complete language. My loose intuition for completeness suggests that, at any point in a computation tableau for $L$, either the computation has "already done an NP complete ...
user avatar
  • 2,313
0 votes
0 answers
25 views

Custom data structure for subarray problems

Is it possible to build a data structure for solving subarray related problems efficiently (E.g. counting the number of subarrays of an array satisfying a given condition)?
user avatar
6 votes
1 answer
237 views

An analogue of Scott continuity for infinite-time-Turing-computable functions

$\newcommand{\tb}{2_{\!\bot}}\newcommand{\tbO}{\tb^{\,\omega}}$Let $2 = \{0,1\}$ and $\tb = \{0,\bot,1\}$. Scott continuity is important for defining models of lambda calculus, a formalism for ...
user avatar
1 vote
0 answers
22 views

Can fair ordering of transactions be achieved in permissionless blockchains?

Front running attacks mainly happen because adversaries are able to manipulate the order of the transactions on blockchains. As many research paper address the problem of fair ordering, I don't find ( ...
user avatar
2 votes
1 answer
72 views

Question about "Free-ness" of Free SCWF

In Category with Family by Castellan et al., they introduce the concept of Free SCWF as correspondence of STLC with base type. Seemingly, they define Free B-SCWF as the synonym of initial B-SCWF. My ...
user avatar
  • 133
1 vote
1 answer
49 views

Question in relating STLC and Free CCC

In Lambek's Intro to Higher Order Cat Logic, Chapter 1 Section 4 introduces the free construction (upon graph) My question is, if I want to have STLC + (fake/incomplete) boolean type, how do I have ...
user avatar
  • 133
-1 votes
1 answer
90 views

Showing that a modification of an NP-Complete problem is also NP-Complete

In this question I give a modified version of the knapsack problem, which I call the "extended knapsack problem". I want to show that this "extended" problem is NP-Complete, but I ...
user avatar
0 votes
0 answers
42 views

Capturing a particular regular language with $O(m)$ states

In dx.doi.org/10.1006/inco.2001.3069 the authors defined $NID_m = \{ u\in \{0,1\}^* | \exists i : u_i \neq u_{i + m} \}$ and claimed it could be recognized by a NFA of size $O(m)$. The paper mentions ...
user avatar
4 votes
1 answer
114 views

Characterization of lengths of words accepted by DFAs

Let $M$ be an arbitrary DFA. For each $n \in \mathbb{N}$, let $f_M(n)$ be the number of words of length $n$ accepted by $M$. Then, consider the set of all such $f_M$ for all DFAs $M$. Is there a nice ...
user avatar
  • 732
6 votes
1 answer
191 views

Solving All-Pairs Shortest Paths using a distance matrix in sub-cubic time

I'm working on a project centered around the All-Pairs Shortest Paths (APSP) problem. Common algorithms to APSP (Floyd-Warshall, Bellman-Ford, Johnson's) work with the standard definition of the ...
user avatar
  • 61
0 votes
2 answers
542 views

Best known algorithm for NEXP-complete problem

What is the best (in time) algorithm for NEXP-complete problems? Is there an algorithm that solve a NEXP-complete problem in time $2^{o(2^n)}$?
user avatar
-1 votes
1 answer
120 views

Alternative to binary search trees: A sorted array with empty spaces

There are many data structures that have O(log(n)) insert, delete and find operations: Self balancing binary search trees, skip lists and others. My question is: Why doesn't the following simple thing ...
user avatar
  • 359
0 votes
1 answer
53 views

What set of sequential 2-bit inputs would it take for any system with 2 bits of memory to not be able to no it is not being tested

In a computer game, a player is tasked with making a sequential circuit that takes two one-bit inputs (for a total of four combinations) and outputs a bit depending on both the current input and the ...
user avatar
  • 101
3 votes
1 answer
263 views

Similarities and differences between Pie and popular languages with dependent types

The book The Little Typer explains dependent types using a toy language called Pie (https://github.com/the-little-typer/pie). How similar is Pie to the popular languages with dependent types: Coq, ...
user avatar
  • 133
2 votes
0 answers
66 views

Ignore side effect in monadic code

Is there a standardized notion of something that removes side effects for an element in a monad? In the case of state monad: An element mx : m X is effectively <...
user avatar
  • 151
4 votes
2 answers
151 views

How exactly does a compatible reduction relation change the $\pi$-calculus?

The reduction relation given for the $\pi$-caculus is usually not compatible (i.e., it's not preserved under arbitrary contexts). Quoting Milner's The Polyadic $\pi$-Calculus: A Tutorial: It is ...
user avatar
0 votes
0 answers
133 views

Relation between BSS and Turing models

$P_\mathbb R$ is the set of languages decidable in polynomial time over the real $BSS$ machine defined in https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine. Let $0-1-P_\mathbb R=\{...
user avatar
  • 12.5k
0 votes
1 answer
78 views

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

Shortest Steiner cycle and $(a,b)$-Steiner path problem are generalizations of optimization versions of Hamiltonian cycle and Hamiltonian path problems. The Shortest Steiner cycle problem is defined ...
user avatar
4 votes
1 answer
108 views

"Operations" in category theory that are not defined for arrows

Functors in category theory are defined for both objects and arrows. Depending on how they treat arrows, functors are characterized as either covariant or contravariant. Some "operations" ...
user avatar
  • 41
3 votes
1 answer
99 views

Question about algorithm for enumerating minimal AB-separators

Let $A,B\subseteq V(G)$ be two non-adjacent, disjoint subsets of vertices in $G$. A subset $S\subseteq V(G)\setminus (A\cup B)$ is an $AB$-separator if the graph $G[V\setminus S]$ contains two ...
user avatar
  • 75
1 vote
0 answers
100 views

Can we describe any context-sensitive language by a grammar without left recursion?

The main question: is it possible to avoid left recursion in a context-sensitive grammar (see example below), i.e., if for any context-sensitive language $L$, there exists some context-sensitive ...
user avatar
1 vote
0 answers
94 views

Are there more learnable but undecidable cases except the halting problem

Per request, I cross post the question here which is original from math.stackexchange In the ICML 1996 paper, On the Learnability of the Uncomputables, by Richard Lathrop, he proved that halting ...
user avatar
  • 111
6 votes
0 answers
76 views

Relationship between natural deduction refutation and tableaux for propositional logic

Which kind of relationship is there between natural deduction refutations of a set f propositional logic assumptions, and the corresponding tableaux? For example, consider the unsatisfiable set $\...
user avatar
  • 1,122
0 votes
0 answers
38 views

If two functions are close apart can I prove the difference of their empirical loss is also small?

I am trying to understand the proof of Theorem 3 in the paper "A Universal Law of Robustness via isoperimetry" by Bubeck and Sellke. Basically there exist atleast one $w_{L,e}$ in $\...
user avatar
  • 113
1 vote
0 answers
50 views

Is there an FPT or XP algorithm known for this version of $k$-edge disjoint paths problem?

The shortest $k$-edge disjoint paths problem is defined as follows: Input: An undirected graph $G=(V,E)$ and $k$ pairs of vertices $(s_1,t_1),\ldots,(s_k,t_k)$. Question: Find (if exist) $k$-pairwise ...
user avatar
0 votes
1 answer
131 views

The Complexity of Multi-Objective Optimization

Given a vector set $V=\{v_i\}_{i=1}^n$ with $n$ vectors where $v_i\in \mathbb{R}^d$ is a vector and a transfer matrix $\mathbf{W}\in \mathbb{R}^{d_1\times d}$, the target is to select two subsets $V_1=...
user avatar
  • 57
0 votes
0 answers
47 views

Solving sampling problems with circuits?

If I allow a circuit family (say, poly size, polylog depth) poly($n$) bits of randomized advice, then I can ask if its output samples from certain distributions or not. However I don't know what the ...
user avatar
3 votes
0 answers
72 views

Is there a standard way to "point" at subterms in a lambda expression?

Let's say I have a lambda expression $$ (\lambda x . (\lambda w.ww)x) y $$ There are a bunch of subterms: $(\lambda x . (\lambda w.ww)x) y$ $\lambda x . (\lambda w.ww)x$ $(\lambda w.ww)x$ $\lambda w ....
user avatar
  • 133
1 vote
0 answers
76 views

Cheapest Insertion is $2$-approximation for TSP

Consider the Cheapest Insertion Algorithm on a complete graph with $n$ vertices, where each edge $uv$ has a weight $w(uv)$, and the weights satisfy the triangle inequality $w(xz)\leq w(xy)+w(yz)$ for ...
user avatar
3 votes
1 answer
148 views

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

Say we have a black-box access to a distribution $\mathcal{D}$ with finite support $\{1,2,...,n\}$ with probability mass function $i \mapsto p_i$. How many samples of $\mathcal{D}$ are needed to learn ...
user avatar
  • 33
7 votes
1 answer
187 views

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

During a work I came across the Scott-Topology and I see that Scott-continuous functions show up in the study of models for lambda calculi. What I cannot understand is how this enrich the lambda-...
user avatar
  • 81
-5 votes
1 answer
51 views

I have to make a dfa over the alphabet Σ = { 0, 1, 2 } of strings that end with the same digit twice; e.g., strings that end in 00, 11, 22

hi can you please go over my dfa for this and tell me if its correct??
user avatar
0 votes
0 answers
62 views

Short UNSAT Certificates for X3SAT

Exactly 1 in 3 SAT ($X3SAT$) is a variation of the Boolean Satisfiability problem. Given an instance of clauses where each clause has three literals, is there a set of literals such that each clause ...
user avatar
0 votes
0 answers
88 views

Complexity of the distance between the average vector of two subsets

Given a vector set $V=\{v_i\}_{i=1}^n$ with $n$ vectors, where $v_i\in \mathbb{R}^d$ is a vector, the target is to select two subsets $V_1=\{v_j\}_{j=1}^{|V_1|} \subset V$ and $V_2=\{v_k\}_{k=1}^{|V_2|...
user avatar
  • 57
0 votes
0 answers
72 views

Direct fpt reduction from Weighted 3SAT to Weighted 2SAT

In parameterized complexity, for each fixed $q$, the problem Weighted $q$-CNF SAT is W[1]-complete. In particular, this means that one can turn a 3CNF formula $\varphi$ into a 2CNF formula $\varphi'$ ...
user avatar
9 votes
1 answer
1k views

Are there survey papers in theoretical computer science?

Are there conferences or journals where we can publish surveys/literature review papers related to theoretical computer science problems? If provide a list of such conferences and journals. I know ...
user avatar
  • 113

15 30 50 per page