Questions tagged [soft-question]

A soft question is a question (possibly subjective) about the field of theoretical computer science as opposed to being a question in theoretical computer science.

Filter by
Sorted by
Tagged with
3
votes
5answers
1k views

Quality of a conference

I am a physicist working in TCS in a new group. I would like to know, given a conference (imagine your favorite ones), how can I know the quality of this conference and also the quality of the ...
3
votes
1answer
512 views

New theories and publications on computer science

When someone develops a new theory on computer science, specifically in artificial intelligence domain, which is barely on schetch (so there are no measurements, nor simulations, nor finished code or ...
3
votes
2answers
2k views

Required mathematics for computational geometry research career

I have a computer engineering degree and i am very interested in theoretical and combinatorial aspects of computational geometry . I want to build the mathematical foundation for this area so i can ...
3
votes
3answers
541 views

Why do theoreticians in CS use multiple-letter variables?

This is a "dual" question of a popular post on math.se. Some mathematical objects in computational complexity theory have multiple-letter names. Complexity classes such as $\mathbf{BPP}$ have an ...
3
votes
1answer
430 views

What is “distributed computing” as a field of computer science?

I think it's field that studies distributed systems as described at http://en.wikipedia.org/wiki/Distributed_computing. There are distributed systems such as clusters and grids on top of this field. ...
3
votes
3answers
562 views

Why is lambda calculus so “function” oriented?

I've always had this question nagging at me subconsciously but have never been able to intuitively grasp it. Why does $\lambda$-calculus have a functional notation? Why is everything a function? It ...
3
votes
2answers
129 views

Looking for some lecture videos on logic, models of computation and computational complexity/tcs fundamentals [closed]

Looking for some lecture videos (introductory level) on logic, models of computation as well as computational complexity/ other theoretical computer science fundamentals
3
votes
1answer
172 views

In what fields does a knowledge of formal semantics prove useful?

(If this is better for programmers SE, let me know, but I imagined you guys would have more thorough answers) I'm a mathematics major, but I have a pretty deep interest in CS (especially in compiler ...
3
votes
1answer
255 views

Which are the best universities for a DPhil/PhD in proof theory and automated reasoning?

I'm an undergraduate student studying computer science and I'm interested in doing a PhD after I graduate. I would like to do research in proof theory and automated reasoning, specifically in ...
3
votes
1answer
151 views

Formal theory about explaining algorithms

There is a lot of algorithms written in formal languages, but I have never seen any formal system which target is to explain or give a rationale behind an algorithm. It seems that when constructing ...
3
votes
1answer
83 views

What is 'circuit problem' mentioned in Kempe-Kitaev-Regev's local hamiltonian problem paper

I have been going through Kempe-Kitaev-Regev's paper The Complexity of the Local Hamiltonian Problem. In the first paragraph of page 3, the authors point out that: To the best of our knowledge, ...
3
votes
2answers
890 views

What are some applications of computational geometry towards computer vision?

I'm interested in both of these topics independently, and wondering some good applications of comp geom within the domain of vision. What are some nice applications and potential projects of comp ...
3
votes
0answers
111 views

Metrics for modelling convergence in the lambda-calculus

I wonder if there have been efforts to reconcile the measure approach to termination and Scott's domain theory or other topological models of computation. In other words, can we translate this measure ...
3
votes
0answers
161 views

How to write algorithms?

Reading research articles in theoretical computer science, I noticed that people often describe their algorithms in an enumerative way (i.e., they enumerate the steps of their algorithm and use "go to"...
3
votes
0answers
508 views

Book Recommendations for a General Introduction to (Theoretical) Computer Science

After perusing the web and cstheory.stackexchange in particular, I've come across many different wonderful resources in Computer Science - from Sipser's "Introduction to the Theory of Computation" to ...
3
votes
0answers
100 views

Notion of “total work” of a problem?

I apologize in advance if this question is outside the scope of this Exchange community; if so, perhaps someone can point me in the right direction. I am curious if there is a theoretical notion of "...
3
votes
0answers
219 views

Formal definition of Turing Completeness [closed]

Wikipedia states: In computability theory, a system of data-manipulation rules […] is said to be Turing complete or computationally universal if it can be used to simulate any single-taped Turing ...
2
votes
2answers
246 views

If only pathological cases of NP-hard problems are difficult to solve, then why isn't NP-hard defined to only include those pathological cases?

NP-hard problems are not used in cryptography, because they are believed to be computationally-intractable in the worst case but are not computationally-intractable in the average case. Is there a ...
2
votes
3answers
286 views

Explaining input-size of integral arguments to undergraduate CS students

When I teach undergraduate algorithms, the students have no problem accepting that two n-bit numbers can be added in $O(n)$ time, or that modular exponentiation takes $O(n^3)$ time. But when we get ...
2
votes
2answers
135 views

Collection of failed attempts to solve X

I've been half-jokingly entertaining the idea of trying to blog about "n ways not to solve P vs NP" in the indefinite future, and in my search came across the How not to solve P=NP? question on cs....
2
votes
1answer
775 views

How to become a Theoretical Computer Scientist [closed]

I am a computer science graduate from India. I have worked in a reputed software company for 10 months only to discover that my area of interest is something else. So I resigned from there and I am ...
2
votes
3answers
793 views

Does anyone know of online video courses (in english) on randomness in theoretical computer science?

I have found some video courses like this one but they are all in russian or other languages I don't understand. I'll like to know if anyone has come across lectures (courses) of this kind which are ...
2
votes
1answer
559 views

Computability Theory prerequisites

What are the prerequisite disciplines for Computability theory? How much is Theory of Computation, Automata Theory, etc and how hard would it be studying it without those prerequisites?
2
votes
1answer
291 views

Is Isomorphism of bounded degree hyper-graphs in P?

Informally, hypergraph is a generalization of a graph in which an edge can join any number of vertices. A hyper graph G=(V,E) is a two tuple, where $V$ is the set of vertices and $E$ is a set contain ...
2
votes
1answer
3k views

What are some good references for mathematical optimization for the layman?

I've been getting myself involved with this topic and would like to read more to gain a conceptual understanding of the various techniques and what each one is trying to achieve and their 'idea' ...
2
votes
2answers
194 views

Reference on cryptography methods

I'm looking for a good reference, possibly a survey, on the different types of cryptography methods. As far as I understand, the security of a cryptographic method depends on some hardness assumptions,...
2
votes
1answer
233 views

Recent fundamental results in algorithms? [closed]

I dont know if this question belong to this forum, but I will ask it anyway To your opinions, what are the most recent fundamental results in the field of algorithms ? [Results that can be taught in ...
2
votes
1answer
209 views

Faithful functors vs forgetful functors: exact category-theoretic defs?

In category theory, a functor between two categories $C,D$ is a map $F$ that assigns to each object (resp. morphism) $x$ of $C$ a corresponding object (resp. morphism) $F(x)$ of $D$ by respecting the ...
2
votes
2answers
2k views

Book recommendations for CompSci related math

Searching for good textbooks on math related to Computer Science I bought two german books yet, but found them not to be easily understandable and not suitable for self-study . German textbooks are ...
2
votes
1answer
249 views

How far has computer science moved past Knuth's TAoCP, if at all? [closed]

The seminal book The Art of Computer Programming got its start in 1968. I have been finding references to it in many literature reviews, apparently there are many problems for which a review by Knuth ...
2
votes
1answer
246 views

What are CS blogs for puzzles/games?

I am looking for blogs which contains recent progress on puzzles/games (Algebraic and Combinatorial) etc. like Soduko, latin square etc. I come across a list on TCS What CS blogs should everyone read?,...
2
votes
2answers
181 views

Suggested approach to cover data structure literature

I am not sure if this question is odd topic or too broad, but I have been wondering about this for a long time, and I would very much appreciate any valuable inputs. As a new grad student working on ...
2
votes
0answers
149 views

Quantum advantage beyond the black-box model

Question Aaronson wrote in his thesis that “essentially all quantum algorithms that we know today—from Shor’s algorithm, as discussed previously, to Grover’s algorithm, to the quantum adiabatic ...
2
votes
0answers
148 views

Book recommendation treewidth

I am searching for a good book (or survey paper) on treewidth. I would be delighted if the book/paper surveys multiple approaches to treewidth (eg: structural, algorithmic, `language-theoretic') and ...
2
votes
0answers
248 views

Is Combinatory Logic (CL) still relevant for programming language theory?

I've been reading up on R. Smullyan's "To Mock a Mockingbird" and Hindley's "Lambda-Calculus and Combinators: An Introduction". I've even read Schonfinkel's 1924 paper introducing the idea of ...
2
votes
0answers
52 views

None-monotone submodular function examples

What are some interesting example of non-monotone submodular functions beside cut, directed cut in graphs?
2
votes
0answers
236 views

Is putting articles on arXiv or alternatives, before peer review, generally acceptable?

How common is it to place articles on arXiv or similar sites before publishing in a peer-reviewed journal? I'm trying to get a feel for what my chances are, of publishing in a journal if I put an ...
2
votes
0answers
209 views

What one bit of computable information would you most like to know? [closed]

If you could ask one computational yes/no question, what would it be? To be precise, you get to specify a Turing machine (in a convenient language) and an oracle will tell you whether or not it halts....
2
votes
1answer
1k views

What are the open ended questions for an CS Undergraduate to think about? [closed]

What can be a possible open ended research topics in Computational Complexity (or something equally fun), for an undergraduate to think about? [I am planning to take up something fun, however my ...
1
vote
1answer
363 views

Statement that inequality of P and NP obstructs finding a proof of their separation

In this set of video lectures, Prof. Mulmuley emphasizes several times that P vs. NP is a very deep philosophical question at the core of Mathematics and that the fact that the two classes are not ...
1
vote
2answers
2k views

Where can I find a copy of Guy Jacobson's thesis “Succinct Static Data Structures”?

I'm looking for a copy of Guy Jacobson's PhD thesis: http://dl.acm.org/citation.cfm?id=915547 but I couldn't find it so far. Does anybody know where can I access it ? I really need it. Thanks in ...
1
vote
2answers
377 views

Method of Algorithm Study

I am a Computer Science student who is greatly intrigued by algorithms. However I am curious whether computer scientists who study algorithms teach themselves to formally analyze algorithms and ...
1
vote
2answers
426 views

How do top researchers keep track new results in datastructures

Is there any twitter or some feed,which constantly sends new results which are being published to your mail.
1
vote
1answer
135 views

When we say a parameter is good for a problem?

I am studying parameterized complexity. I have seen few parameterized algorithm for problems like vertex cover, feedback vertex set etc. I have difficulty in determining when a parameter is said to be ...
1
vote
4answers
347 views

Is Biological Computation a theme covered by the Theoretical Computer Science?

I want to say computation realized by biological systems themselves. I'm not talking about bio-inspired algorithms, or applications in computation using living systems. This question is more about an ...
1
vote
2answers
183 views

Classic parallel clustering algorithms

I'm starting a research about parallel clustering. I see a ton of articles on this topic, so that I don't know where to start. I'd like to get familiar with classic methods of parallelizing clustering....
1
vote
1answer
235 views

Citation style for CS publications

What is the recommended citation style for use with CS (and related) publications? I tried looking at submissions at http://arxiv.org/archive/cs but all of them seem to use different citation styles. ...
1
vote
1answer
130 views

What math courses should I revisit to prepare for a CS Ph.D. (Reinforcement learning and Game Theory)?

I am planning to join a CS Ph.D. program in 6 months. My topics of research will be in the area of Reinforcement Learning and Game Theory. Even though I have a good grasp of these two topics’ ...
1
vote
1answer
140 views

Publishing by showing falsity of existing results [closed]

Is it valid to publish a minor result related to computer science complexity theory and classes that disproves and falsifies an existing result? Would that be a valid and respectable endeavor?
1
vote
1answer
169 views

Analytic Number theory in TCS [closed]

Are there any applications of analytic number theory in TCS?

1
4 5 6
7
8