All Questions
12,687
questions
0
votes
1
answer
30
views
Why is the estimation error smaller in Structural Risk Minimization
On p.87 in this online Understanding Machine Learning book, the authors wrote:
Unlike the ERM paradigm discussed in previous chapters, we no longer just care about the empirical risk, $L_S(h)$, but ...
- 131
1
vote
0
answers
47
views
Relation Between Different Definitions of Information Distance
I'm reading the fourth edition of An Introduction to Kolmogorov Complexity and Its Applications by Li and Vitanyi. In Section 8.3 of the book, it introduces the concept of "information distance.&...
0
votes
0
answers
97
views
Assume `P != NP`, does it imply that one-way functions exist?
I define a function f to be one-way iff for any sufficiently large x computing f(x) bounded ...
- 212
4
votes
1
answer
105
views
High-dimensional expanders through the lens of algebraic topology
High-dimensional expanders are used in a few areas of TCS (coding theory, sampling, probably some others). While I'm not too familiar with their usage, I know that in sampling they can be useful to ...
- 43
4
votes
2
answers
521
views
Do we currently know a polynomial-size Frege proof for Tseitin formulas?
There's a vast literature about super-polynomial lower bounds on proof lengths of Tseitin formulas in bounded-depth Frege systems, but what I'm curious about is: what if we don't restrict the depth of ...
- 145
1
vote
0
answers
39
views
Why the measure of information complexities for passive and active learning are increasing in research communities?
I am a PhD student working on the theory of active learning.
Over the years, accepted papers in COLT and ALT for active learning are focused on approaches that almost all of them define new ...
- 122
10
votes
0
answers
203
views
Is there a text that discusses both the “lambda cube” of pure type theories and Martin-Löf's intuitionistic type theories, and compares them?
I am lost in a maze of twisty little type theories, all different.
There are a number of works (textbooks and papers) that discuss pure type theories, and specifically the ones constituting the ...
- 619
-1
votes
1
answer
61
views
Unable to understand the Sample complexity of PAC learning
I have been studying from the book "Understanding Machine Learning - From Theory to Algorithms" by Shai Shalev-Shwartz and Shai Ben-David
I am struck at corollary 3.2 which states that
Every ...
1
vote
1
answer
70
views
Known Variant of Set Cover?
Consider the following variant of set cover:
Given: Target set $T$ and a collection of sets $\mathcal{C}$, such that $T \subseteq \bigcup_{C \in \mathcal{C}} C$.
Wanted: A subset $\mathcal{C'}$ of $\...
- 11
0
votes
0
answers
31
views
Is there an efficient Goldreich-Levin algorithm that generalizes to agnostic PAC setting?
Goldreich Levin algorithm is an algorithm that based on some assumption (boundness on Fourier coefficients) outputs the indices for most significant Fourier coefficients of a boolean function, however ...
- 53
-3
votes
1
answer
98
views
Can one do descriptive complexity theory using abstract state machines?
I learned about ASM recently and was interested how it could used for descriptive complexity theory.
Such link seems natural to me: you can give construction of algebraic model for formula as an ASM. ...
- 295
4
votes
0
answers
92
views
$\log^\star n$ is somewhat common in runtimes. Does the superroot ever make an appearance?
Many algorithms and data structures have iterated logarithms ($\log^\star n$) in their runtimes. This function is the discrete inverse of tetration, in that
$$\log_a^\star (a \uparrow \uparrow b) = b$$...
- 2,121
2
votes
0
answers
42
views
Geometric Set Cover Problem and Union Complexity
I have encountered an instance of the Geometric Set Cover problem where the complexity of the union of any subset with size, say k, of m objects is linear with respect to m. I am aware of a well-known ...
- 21
4
votes
0
answers
70
views
distinguishments between query complexity of membership oracles and standard time complexity
Many combinatorial optimization problems can be described as follows. We are given a set system $(E,I)$, where $I \subseteq 2^E$ and a weight function $w: E \rightarrow \mathbb{N}$. The goal is to ...
- 173
4
votes
0
answers
72
views
Name for a cyclic path in a graph that visits every vertex while minimizing the maximum number of times a given vertex is revisited?
Me and my colleague are interested in whether anyone has looked into a generalization of Hamiltonian cycles where vertices can be revisited, but we want to minimize the maximum number of times a given ...
- 429
2
votes
0
answers
55
views
Does PAC learnable imply agnostic PAC learnable for binary classification tasks?
The Fundamental Theorem of Statistical Learning from the book "Shai et al., Understanding Machine Learning: From Theory to Algorithms, Cambridge Press University", is written as follows:
...
- 131
3
votes
2
answers
255
views
Where should I apply for MS in CS if I want to get admitted for Phd in TCS
I'm currently finishing my bachelor's degree of Computer Science and I'm really interested in Computational Complexity Theory and Analysis and design of Algorithms. As far as I know, if I do not have ...
- 31
2
votes
1
answer
277
views
Deciding finiteness of regular language is NL-complete?
I've been reading the following Habilitation thesis where the author claims (pg. 29):
... First, deciding whether the language of an NFA is finite is in NL ...
I'm having trouble seeing why this ...
user70406
0
votes
1
answer
112
views
Computational power of probabilistic automata
I am a bit confused about the proper role of probabilistic automata (PA) in the theory of computation.
Informally, I can imagine they can accept more than finite automata (FA) as they, for instance, ...
- 109
5
votes
1
answer
387
views
Relation between ACC^0 and DTIME
In a breakthrough Ryan Williams (STOC13/14) showed that $\mathsf{NEXP} \nsubseteq \text{non-uniform } \mathsf{ACC}^0$.
How far can we potentially push this result?
In other words, what is the largest $...
- 223
1
vote
0
answers
52
views
Find linear combination with small support
Let $v_1,\dots,v_n$ be a basis of a vector subspace of $\Bbbk^N$, say for $\Bbbk$ a finite field. I would like an algorithm to find a linear combination of the $v_i$'s with small support, i.e. with ...
- 191
-1
votes
1
answer
75
views
Representation of binary strings by graphs and hypergraphs
Let $\Sigma$ be the set $\{ 0, 1 \}$, then the set of all finite binary strings of length $n$ is written as $\Sigma^{\star}_{n}$.
Question: Which further ways of representing binary strings of length $...
- 1
1
vote
1
answer
55
views
Many-one degrees of some particular sets
Let $W_0, W_1, W_2,\dotsc$ be an effective numbering of r.e. sets.
Consider sets $\text{Emp}=\{x\mid W_x=\emptyset\}$, $\text{Tot}=\{x\mid W_x=\mathbb{N}\}$ and $S_n=\{x\mid W_x=W_n\}$ (for some fixed ...
- 33
0
votes
2
answers
59
views
Representing/Modelling fields and methods in the context of programming as automata
I am trying to represent/model fields and methods in the context of programming as automata. For instance, let's say that I have field1 with state equal to 2, ...
- 129
1
vote
1
answer
55
views
Coefficients of a determinant of a matrix of univariate polynomials is in $GapL$
Given any matrix of univariate polynomials of degree $\leq n^{O(1)}$ then prove that the coefficent of $x^i$ in the determinant of the matrix is in $GapL$
Hint: Use Mahajan-Vinay's result of ...
- 288
5
votes
0
answers
118
views
"Interesting" problems in $NLogTime \cap coNLogTime$
In terms of machine model, I'm interested in multitape Turing machines with random access to the input via a query tape.
Criteria for "interesting" in this context:
Not in $DLogTime$: "...
- 1,204
1
vote
0
answers
77
views
Conditional lower bounds for reachability
Are there conditional lower bounds for the deterministic time complexity of directed reachability algorithms? Maybe something linked to the Strong Exponential Time Hypothesis (SETH)?
I mean some ...
- 1,588
0
votes
0
answers
29
views
What't the relationship between subexp and polynomial kenrel?
In parameterized algorithms, we know there is a problem that
has a subexponential parameterized algorithm (subexp for short) and a polynomial kernel (e.g., split edge deletion problem);
has no subexp,...
- 19
0
votes
0
answers
28
views
FPTAS for switching deals
The local supermarket offers seasonal deals on their apples and oranges. You want either apples or oranges on any given day, but don't know until you wake up; you want to
minimise your cost. You ...
- 1
0
votes
0
answers
165
views
Decidability of the complexity of decision problems
This might be a question that is related to some of the existent questions on the topic in the title, but I still find some answers either not full, or the topic still slightly different (maybe due to ...
- 101
3
votes
0
answers
69
views
Can a positive elementary inductive definition refer to its own stage comparison relation?
Suppose $\varphi(x,S)$ is a positive elementary formula, i.e., a first-order formula with second-order relation variable $S$, such that the arity of $x$ and $S$ agree. In this setting, $\varphi$ can ...
- 803
0
votes
1
answer
123
views
Finding deepest intersection
There must be a name for this problem, but I can't find it: Given $n$ rectangles in the plane, what is the most number of rectangles that a point in the plane belongs to? In other words, thinking of ...
0
votes
1
answer
58
views
Detecting Erroneous Corrections
A block code $C$, with minimum distance $d$ can be used to:
Detect $d - 1$ errors
Correct $\lfloor\frac{d - 1}{2}\rfloor$ errors
However, the above usually assumes that the number of errors that are ...
- 1
7
votes
2
answers
189
views
How to show that a problem is in $\Pi_1^1$?
I am trying to show that a decision problem is in $\Pi_1^1$.
Because of this, I am looking for:
Papers or books that present a complete and well-explained proof where a problem is shown to be in $\...
- 99
0
votes
0
answers
67
views
The hardness of active learning with fixed budget
I have been looking for theoretical papers studying this question of the hardness of PAC active learning algorithms. I found a few papers studying the problem from a fixed perspective (particular ...
- 53
-7
votes
2
answers
357
views
Self Referential Undecidability Construed as Incorrect Questions
Please see my answer before you read any of this. The answer says the same thing much much more clearly
PhD computer science professor Rick Hehner and I independently derived what we mutually agree ...
- 45
3
votes
0
answers
111
views
Computational complexity of finding the $n$th Dedekind Number
Recently, two independent groups of researchers exactly calculated the $9$th Dedekind Number (see e.g. Quanta). The $n$th Dedekind Number counts the number of antichains consisting of subsets of $\{1,...
- 205
1
vote
1
answer
123
views
Primitive recursion with varying parameters
Suppose $g\colon \mathbb{N}^k \to \mathbb{N}$, $v_1,\ldots,v_r\colon \mathbb{N}^k \to \mathbb{N}^k$ and $h\colon \mathbb{N}^{k+r+1} \to \mathbb{N}$ are all primitive recursive, and define $f\colon \...
- 619
2
votes
0
answers
69
views
Resource bounded Kolmogorov complexity hardness on average over a non uniform distribution of inputs
$K^{poly}$, as well as other related problems such as $MCSP$, is believed to be hard on average [1, 2] when the input is sampled from a uniform distribution (since otherwise one way functions, pseudo-...
- 187
0
votes
0
answers
114
views
Counterexample in Sistla and Clarke's paper
I'm reading Sistla and Clarke's paper "The Complexity of Propositional Linear Temporal Logics". In section 4 they start with the following set up:
Let $S=(s, \xi), T=(t, \pi)$ be structures ...
- 921
2
votes
0
answers
149
views
Deciding Satisfiability of a "Universal" Second-Order Logic Formula
Consider the following decision problem:
Input: a second-order logic formula $\psi$ of the form $\forall X_1 . \ldots . \forall X_n . \phi$ where $X_1, \ldots, X_n$ are a second-order variables and $\...
- 99
0
votes
1
answer
67
views
Solving non-linear programming with large number of variables
Let $n \in \mathbb{N}, [n] = \{1,2,\ldots,n\}$ and consider the following optimization problem:
$$\max \sum_{i \in [n]} \sum_{j \in [n]} x_i \cdot x_j \cdot c_{i,j}$$
$$s.t.~~~~~~~~~~~~~~~~~~~~~~~~~~~~...
- 173
2
votes
0
answers
46
views
Is this variant of Facilities location problem a NP-hard problem?
Given a set of locations $P=\{p_1,p_2,\dots\}$ and a set of facilities $F=\{f_1,f_2,\dots\}，|F|\ge k$ on a plane. We want to partition the facilities into $k$ disjoint subsets (each subset has at ...
- 21
0
votes
0
answers
46
views
Proving the Equivalence of REGEX r^n and r^{..n} when r Is Nullable
Im seeking clarification and a rigorous proof regarding the equivalence of r^n and r^{..n} in the context of formal languages, particularly when r is nullable.
To clarify the terminology:
r denotes ...
- 1
1
vote
0
answers
41
views
How to understand this evolutionary algorithm lower bound calculation?
I have a proof that I understand the most of it except one step
Lemma 10. The expected number of steps the $(1+1)$ EA takes to optimize a linear function with all non-zero weights is $\Omega(n \ln n)$....
- 111
-1
votes
1
answer
71
views
Generating grammar from a string
Given a string generated with a valid grammar, how can I find list of all the valid grammar for that particular string?
Problem statement - I'm trying to build a code base scanner, and I'd like to ...
- 99
1
vote
1
answer
108
views
Complexity of analytic functions and integrals
There exist polynomial - time computable functions, log - space computable functions, and NC - functions. Given this:
To which class do analytic elementary functions, including trigonometric ones, ...
- 13
0
votes
0
answers
30
views
Derivation of influence function in Understanding Black-box Predictions via Influence Functions paper
In Understanding Black-box Predictions via Influence Functions paper Appendix A, the authors provide a standard derivation for influence functions, however, I could not understand one of the steps. ...
2
votes
1
answer
187
views
Additive chernoff bound
From wikipedia,
Additive form (absolute error)
The following theorem is due to Wassily Hoeffding and hence is called the Chernoff-Hoeffding theorem.
Chernoff-Hoeffding theorem.
Suppose $X_1, \ldots, ...
- 109
1
vote
0
answers
40
views
Detailed exposition for proof of Localization Lemma in paper "Random Walks in a Convex Body and an Improved Volume Algorithm"
I've begun reading the paper "Random Walks in a Convex Body and an Improved Volume Algorithm" by Lovász-Simonovits ('93). Although the paper for the most part is pretty self-contained and ...
- 111