All Questions

Filter by
Sorted by
Tagged with
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 ...
Tran Khanh's user avatar
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.&...
Ravi Deedwania's user avatar
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 ...
Zazaeil's user avatar
  • 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 ...
p-adict's user avatar
  • 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 ...
Soha's user avatar
  • 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 ...
Ayoubayjx's user avatar
  • 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 ...
Gro-Tsen's user avatar
  • 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 ...
Sathishkumar Thirumalai's user avatar
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 $\...
Jan Reineke's user avatar
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 ...
rivana's user avatar
  • 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. ...
uhbif19's user avatar
  • 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$$...
templatetypedef's user avatar
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 ...
Arash Vaezi's user avatar
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 ...
John's user avatar
  • 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 ...
mich's user avatar
  • 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: ...
Tran Khanh's user avatar
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 ...
Marinovsky's user avatar
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 ...
user avatar
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, ...
Barney's user avatar
  • 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 $...
Nicholas Brandt's user avatar
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 ...
grok's user avatar
  • 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 $...
Samdney's user avatar
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 ...
ijon's user avatar
  • 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, ...
The Pointer's user avatar
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 ...
Soham Chatterjee's user avatar
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$: "...
Jake's user avatar
  • 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 ...
Nicola Gigante's user avatar
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,...
Hanchun Yuan's user avatar
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 ...
Derek's user avatar
  • 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 ...
A. G's user avatar
  • 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 ...
Siddharth's user avatar
  • 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 ...
femeve3881's user avatar
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 ...
Coziyu's user avatar
  • 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 $\...
David Carral's user avatar
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 ...
rivana's user avatar
  • 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 ...
polcott's user avatar
  • 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,...
Clay Thomas's user avatar
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 \...
Gro-Tsen's user avatar
  • 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-...
agemO's user avatar
  • 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 ...
user1868607's user avatar
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 $\...
David Carral's user avatar
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.~~~~~~~~~~~~~~~~~~~~~~~~~~~~...
John's user avatar
  • 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 ...
Jingle's user avatar
  • 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 ...
J.Doe's user avatar
  • 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)$....
Edee's user avatar
  • 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 ...
Vetrivel's user avatar
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, ...
roignoirewg's user avatar
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. ...
umityigitbsrn's user avatar
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, ...
Dotman's user avatar
  • 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 ...
Samyak Jha's user avatar

15 30 50 per page