All Questions
11,964
questions
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?
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 ...
- 123
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, \...
- 749
1
vote
0
answers
126
views
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 ...
- 11
-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 ...
- 99
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$.
...
- 393
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: ...
- 23
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(...
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 $...
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 ...
- 19
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 ...
- 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 ...
- 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<...
- 151
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 ...
- 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)?
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 ...
- 330
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 ( ...
- 11
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 ...
- 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 ...
- 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 ...
- 99
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 ...
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 ...
- 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 ...
- 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)}$?
- 1,655
-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 ...
- 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 ...
- 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, ...
- 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 <...
- 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 ...
- 293
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=\{...
- 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 ...
- 141
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" ...
- 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 ...
- 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 ...
- 11
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 ...
- 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 $\...
- 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 $\...
- 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 ...
- 141
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=...
- 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 ...
- 21
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 ....
- 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 ...
- 11
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 ...
- 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-...
- 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??
- 1
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 ...
- 499
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|...
- 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'$ ...
- 429
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 ...
- 113