All Questions

Filter by
Sorted by
Tagged with
1 vote
1 answer
115 views

Is the model in which a protocol is proven secure more important than type of hardness from which the algorithm gains its strength

Question: If I prove a protocol secure in the plain model (i.e., without any prerequisites or setup before running the protocol, setups like a common reference string distributed among all parties) ...
Yasser Sobhdel's user avatar
12 votes
0 answers
375 views

Oracle relative to which MA does not have a complete problem?

Babai introduced a hierarchy of complexity classes based on public-coin randomized interactive proof systems, so called Arthur-Merlin games. The game is played by powerful but untrustworthy wizard ...
Dai Le's user avatar
  • 3,664
12 votes
1 answer
414 views

Can relativization results be used to prove sentences formally independent?

Is it possible to demonstrate that a sentence must be formally independent based on the fact that it is non-relativizing? In other words, are there examples of sentences in computability/complexity ...
user avatar
20 votes
4 answers
1k views

Parity and $AC^0$

Parity and $AC^0$ are like inseparable twins. Or so it has seemed for the last 30 years. In the light of Ryan's result, there will be renewed interest in the small classes. Furst Saxe Sipser to Yao ...
V Vinay's user avatar
  • 3,873
10 votes
1 answer
264 views

A direct sum theorem for Resolution clause space complexity?

Resolution is a scheme to prove unsatisfiability of CNFs. A proof in resolution is a logical deduction of the empty clause for the initial clauses in of the CNF. In particular any initial clause can ...
MassimoLauria's user avatar
4 votes
2 answers
346 views

Nontrivial separation consequences of P!=NP

I am looking for nontrivial examples of complexity class separations that are known to follow from the P!=NP hypothesis. By a "nontrivial example" I mean that it is not just an automatic consequence ...
user avatar
7 votes
1 answer
296 views

Approximating convex sets

In the Haussdorf approximation of a convex object $C$ (and in much core-set work), the standard approach is to take an $\epsilon$-net on the enclosing hyper-sphere, then project it down to $C*(1 + \...
Amir's user avatar
  • 729
6 votes
1 answer
634 views

Books on Mu-Calculus

I need a book on Mu-Calculus with lots of examples that can be used for self-study and preparation for exams.
Shambo's user avatar
  • 163
10 votes
8 answers
893 views

Is there any other algorithm whose worst-case running time is exponential meanwhile it works very well in practice other than Simplex Algorithm?

We generally call an algorithm "good algorithm" if it's runnning time is polynomial in the worst-case. But in some cases (for example Simplex algorithm), eventhough the worst-case of the algorithm is ...
Arman's user avatar
  • 934
11 votes
2 answers
4k views

Complexity of Finding the Eigendecomposition of a *Symmetric* Matrix

This is a specialized version of a previous question: Complexity of Finding the Eigendecomposition of a Matrix . For NxN symmetric matrices, it is known that O(N^3) time suffices to compute the ...
Lihong Li's user avatar
  • 111
85 votes
42 answers
18k views

Funny TCS-related papers etc?

What is the funniest TCS-related published work you know? Please include only those that are intended to be funny. Works which are explicitly crafted to be intelligently humorous (rather than, say, ...
30 votes
0 answers
792 views

The complexity of checking whether two DAG have the same number of topological sorts

This problem is highly related to the CNF one. Here is the problem: given two DAG (directed acyclic graphs), if they have the same counting of topological sorts, answer "Yes", otherwise, answer "No". ...
Mike Chen's user avatar
  • 709
1 vote
3 answers
391 views

Is there a common mathematical symbology for collections?

Preface: So, it was suggested in 'Programmers' that I ask this over here. I am being asked to define several of my algorithms in mathematical terms to describe my work to a customer. I trying to ...
JMike's user avatar
  • 21
9 votes
1 answer
606 views

Is there a relationship between computational complexity theory and complex systems theory?

Computational complexity theory classifies problems according to their inherent difficulty. Complex systems theory addresses systems that exhibit behaviours that do not obviously arise from the ...
rphv's user avatar
  • 583
2 votes
0 answers
431 views

Notation for drawing rooted trees with isomorphic subtrees and recursive parts

I need to specify small rooted trees with a lot of repeated parts and some recursive definitions. To illustrate the need, let's use $s(T_1, T_2, ..., T_k)$ to denote a tree that consists of a degree-$...
Jukka Suomela's user avatar
8 votes
2 answers
482 views

Spectral techniques for genus of a graph

A generic question: are there any spectral techniques to estimate the genus of a graph? I am interested in bipartite graphs.
Turbo's user avatar
  • 12.9k
12 votes
2 answers
2k views

Does the existence of PH-complete problems relativize?

The Baker-Gill-Solovay result showed that the P = NP question does not relativize, in the sense that no relativizing proof (insensitive to the presence of an oracle) can possibly settle the P = NP ...
user avatar
9 votes
2 answers
413 views

Property Testing for Independent Sets

Suppose we're given a graph $G$ and parameters $k,\epsilon$. Are there ranges of values for $k$ (or is it doable for all $k$) for which it is possible to test whether $G$ is $\epsilon$-far from having ...
Suresh Venkat's user avatar
4 votes
2 answers
482 views

Applications of association schemes to complexity theory and other TCS

An association scheme is defined as a pair $(V, R_0,R_1, \ldots,R_{n+1})$ of a set $V$ and relations $R_i$ on $V$ such that $(x,y) \in R_i$ implies $(y,x) \in R_i$ for all $x, y \in V$. $R_0 = \{ (x,...
Aaron Sterling's user avatar
15 votes
4 answers
633 views

Are there known to exist functions with the following direct-sum property?

This question can be asked either in the framework of circuit complexity of Boolean circuits, or in the framework of algebraic complexity theory, or probably in lots of other settings. It is easy to ...
matt hastings's user avatar
9 votes
2 answers
451 views

The complexity of Area-lawed Hamiltonians

I have recently thought about "importing" some physics-related question into quantum CS: The notion of the area-law phenomenon in Hamiltonian systems usually stands for a local Hamiltonian on some ...
user avatar
5 votes
2 answers
699 views

Problems with mixed unary/binary inputs

As a mild follow-up to this question on alphabet sizes, let me ask about the other part of the natural numbers, i.e. $\le 2$. Clearly everyone knows about problems over a binary alphabet. Unary, on ...
Daniel Apon's user avatar
  • 6,001
-1 votes
1 answer
393 views

Locate "N Gram" substrings that are smallest distance away from a target string N character long

I am looking for an algorithm, or code, preferably in Python that would help me locate substrings, N characters long, of exisiting strings that are closest to a target string N character long. ...
PoorLuzer's user avatar
  • 173
28 votes
2 answers
2k views

A category of NP-complete problems?

Does it make sense to consider a category of all NP-complete problems, with morphisms as poly-time reductions between different instances? Has anyone ever published a paper about this, and if so, ...
Paul Allen Grubbs's user avatar
18 votes
5 answers
2k views

Simple and practical deterministic algorithm, complicated running time

Very often, if the running time of an algorithm is a complicated expression, the algorithm itself is also complicated and impractical. Each of the cube roots and $\log \log n$ factors in the ...
Jukka Suomela's user avatar
31 votes
3 answers
4k views

coNP certificate for Graph Isomorphism

It is easy to see that graph isomorphism(GI) is in NP. It is a major open problem whether GI is in coNP. Are there any potential candidates of properties of graphs that can be used as coNP ...
Shiva Kintali's user avatar
47 votes
5 answers
1k views

Are there Conservation Laws in Complexity Theory?

Let me start with some examples. Why is it so trivial to show CVP is in P but so hard to show LP is in P; while both are P-complete problems. Or take primality. It is easier to show composites in NP ...
V Vinay's user avatar
  • 3,873
14 votes
3 answers
856 views

The complexity of checking whether two CNF have the same number of solutions

Given two CNF, if they have the same number of assignments to make them true, answer "Yes", otherwise answer "No". It is easy to see it is in $P^{\#P}$, since if we know the exact numbers of ...
Mike Chen's user avatar
  • 709
10 votes
1 answer
388 views

Computational consequences of Friedman's (unprovable) Upper Shift Fixed Point theorem?

Harvey Friedman showed that there is a neat fixed point result that cannot be proved in ZFC (the usual Zermelo-Frankel set theory with the Axiom of Choice). Many modern logics are built on fixed ...
András Salamon's user avatar
20 votes
2 answers
1k views

Why isn't Montgomery modular exponentiation considered for use in quantum factoring?

It is well known that modular exponentiation (the main part of an RSA operation) is computationally expensive, and as far as I understand things the technique of Montgomery modular exponentiation is ...
S Huntsman's user avatar
0 votes
0 answers
312 views

Sort sorted matrix [duplicate]

Possible Duplicate: What is a good special-case sorting algorithm? Is there any linear-time sorting algorithm for sorting elements of a sorted matrix (a matrix with all rows and columns sorted)?
user avatar
10 votes
0 answers
363 views

Gap hardness of Multi-Dimensional Cover

Given a finite set $X$ and a collection $F$ of subsets of $X$, we define a cover of $X$ in $F$ as a subset of $F$ whose union is equal to $X$. A cover $C$ of $X$ in $F$ is said to be exact if the ...
Tsuyoshi Ito's user avatar
  • 16.5k
9 votes
6 answers
2k views

Where does the information in a fractal come from?

When I view a fractal such as the Mandelbrot, my first thought is, where did this interesting picture come from. For a picture of this complexity, the information that generated this picture must be ...
Phil's user avatar
  • 201
0 votes
0 answers
189 views

P vs. NP via psuedo-random number generators [duplicate]

Possible Duplicate: P vs. NP and Pseudorandom Bit Generators Hello again , and thank you all for making this website a great vehicle for knowledge exchange. So my question is , are you trying to ...
user avatar
0 votes
1 answer
161 views

Languages and their operations: determining equivalence [closed]

I'm currently taking a subject on theoretical computer science. This is not a homework question. I'm having trouble figuring out to show the equivalence or disprove the equivalence. Consider any two ...
oadams's user avatar
  • 103
13 votes
2 answers
590 views

Pairwise independent gaussians

Given $X_1,\ldots,X_k$ (i.i.d. gaussians with mean $0$ and variance $1$), is it possible (how?) to sample (for $m=k^2$) $Y_1, \ldots, Y_m$ such that $Y_i$'s are pairwise independent gaussians with ...
user avatar
3 votes
1 answer
2k views

Tarjan Strongly Connected Components Question [closed]

Below is Tarjan's SCC algorithm as described in wikipedia. Input: Graph G = (V, E) ...
Wesner Moise's user avatar
11 votes
2 answers
356 views

Clustering formalizations other than K-means for separable data

Real world data sometimes has a natural number of clusters (trying to cluster it into a number of cluster lesser than some magic k will cause a dramatic increase the clustering cost). Today I attended ...
Aleksandr Levchuk's user avatar
8 votes
2 answers
2k views

Upper bounds on the length of longest simple path in non-Hamiltonian graph?

Hamiltonian cycle problem is $NP$-complete on cubic planar bipartite graphs. I'm interested in upper bounds on the length of the longest simple path in non-Hamiltonian cubic planar bipartite graphs. ...
Mohammad Al-Turkistany's user avatar
1 vote
2 answers
593 views

When we are using Random Oracle Model

There are protocols which make use of invoking an oracle or submitting queries to an oracle and getting response from that. There are many examples in which oracles are used to define security, like ...
Yasser Sobhdel's user avatar
8 votes
1 answer
492 views

Using game-based proofs in simulation-based proofs

Simulation-based security provides more natural and more powerful definition of security than game-based security. I have seen the simulation based approaches use the game-based proofs in-part to ...
Yasser Sobhdel's user avatar
30 votes
10 answers
2k views

Great algorithms, machine learning and no linear algebra

I teach an advanced algorithms course and would like to include some topics related to machine learning which will be of interest to my students. As a result, I would like to hear people's opinions of ...
Simd's user avatar
  • 3,902
16 votes
7 answers
2k views

Research data organization

This is a question in the spirit of this one where I answered that it is important to keep track of what you have done something, why you have done it and what is not working. I personally use ...
Sylvain Peyronnet's user avatar
3 votes
0 answers
194 views

Simulator Efficiency versus Algorithm Efficiency

I have a question about the simulator efficiency. I am reading a group key exchange protocol which is UC-Secure (the security is proven on universal composability framework of Canetti). The proof uses ...
Yasser Sobhdel's user avatar
20 votes
5 answers
2k views

Deterministic Parallel algorithm for perfect matching in general graphs?

In complexity class $\mathsf{P}$, there are some problems conjectured NOT to be in the class $\mathsf{NC}$, i.e. problems with deterministic parallel algorithms. Maximum Flow problem is one example. ...
Hsien-Chih Chang 張顯之's user avatar
19 votes
4 answers
1k views

Applications of Complexity Theory

Complexity theory seems to capture something fundamental about the structure of the universe, in that it formalizes the intuitive notion that some problems are harder than others. Scott Aaronson ...
rphv's user avatar
  • 583
13 votes
3 answers
2k views

Statistical query model algorithms?

I asked this question in cross validated Q&A but seems that it is related to CS much more than Statistics. Can you give me examples of machine learning algorithms which learn from the statistical ...
Deyaa's user avatar
  • 544
1 vote
2 answers
738 views

Resources on Jablon's Protocol

Are there any good resources (descriptions, explanations, examples) regarding Jablon's protocol for password authentication using multiple servers, aside from this paper?
adrianp's user avatar
  • 107
23 votes
6 answers
817 views

Curriculum: Logical/Formal Methods in Security

At present I teach a small course (Four two hour lectures at the Masters level) on Logical Methods in Security, though the title Formal Methods in Security might be more apt. It covers briefly the ...
Dave Clarke's user avatar
  • 16.7k
11 votes
2 answers
502 views

straight-line simulatability

Does any body know any good reference for meaning of straight-line simulatability? I am currently deep into Universal Composability (UC) framework of Canetti but I can't find any good reference for ...
Yasser Sobhdel's user avatar

15 30 50 per page
1
241 242
243
244 245
258