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
2
votes
2answers
99 views

What podcast should everybody listen to?

This list was inspired by the lists: What are the popular science books that inspire TCS? What Books Should Everyone Read? What papers should everyone read? What videos should everybody watch? I don'...
3
votes
1answer
60 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, ...
1
vote
1answer
120 views

Analytic Number theory in TCS [closed]

Are there any applications of analytic number theory in TCS?
5
votes
0answers
113 views

Program size versus program running time

Short "naive" question: Is it true that faster algorithms require longer programs ? Given a decision problem $A$ and a reasonable model of computation, there can be many ways (algorithms) to ...
5
votes
0answers
132 views

What research is being done in classical complexity theory?

As far as I'm aware, classical complexity theory is being replaced by more recent forms of complexity theory, such as communication complexity and quantum complexity. What happened to results such as ...
-1
votes
0answers
141 views

Timing a career switch from math to TCS [migrated]

Short version: Is it better to switch focus as a postdoc or wait until after tenure? Details: I'm a PhD student in math (combinatorics) graduating next year. Let's suppose that I'm a strong candidate ...
0
votes
1answer
91 views

Diving straight into “research” versus studying broadly as an undergrad (soft question)

I'm nearing the end of my first year as an undergraduate and am very confident that I want to pursue a PhD in TCS. Fortunately because I quickly realized what I'm interested in and have a solid ...
12
votes
0answers
275 views

What percentage of SODA papers are galactic algorithms?

Consider papers published in major theoretical CS conferences during the last 5 year, where the main result is that there exists an algorithm with some time or space complexity to solve some problem. ...
1
vote
0answers
18 views

Sorting using comparisons that are not simple mappings of simple comparisons

The Python language has a sort(x) function that sorts a list based on the intrinsic comparison operator associated with the type of the elements of its input list x. One can also provide a cmp ...
4
votes
0answers
69 views

Status of the Junta Problem (soft question)

Does the learning theory community in general believe that juntas can be learned in polynomial time? The naive algorithm works in quasi-polynomial time. MOS's paper shows how to solve the junta ...
13
votes
1answer
187 views

Dialogue writing style & Yuri Gurevich's imaginary student: Quisani

Recently, while I was looking for more sources of crossing sequence in computational complexity theory, I came across the article "Is Randomness 'Native' to Computer Scientist?" written by M. Ferbus-...
4
votes
1answer
152 views

What are the criteria for inviting conference papers (e.g. SODA) for special issue?

This is mostly for some immigration related document that I am trying to write and want to reference an online link which mentions that only a select few papers are invited for special issue for SODA ...
21
votes
1answer
1k views

Turing award papers

I was wondering if there are individual publications that have led their authors to win the Turing Prize or if the Turing Prize is the result of a lifetime's work and multiple publications and results....
4
votes
0answers
180 views

Advice for new grad student [closed]

I'm a first year PhD student in a CS department at what some would probably consider a mid-tier university. I've been reading from Vershynin's High-Dimensional Probability and been trying to learn ...
1
vote
2answers
143 views

Are patents good sources for academic research?

I'm a freshman Master's student in Computer Science and I need to write a paper for my Operating System class. While looking through research articles using google scholar I found that a lot results ...
2
votes
0answers
126 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 ...
5
votes
1answer
206 views

Site with collection of exercises in TCS?

Is there a website with a large collection of exercises for theoretical computer science, sorted by topics? I know that many exercises can be found in different textbooks, I'm looking for an online ...
7
votes
2answers
349 views

How to efficiently read the theoretical computer science research papers?

I am a computer science graduate student works in theory. The general advice is to go through the paper and then in the second or third round try to understand the detail. Read the abstract, ...
2
votes
0answers
118 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 ...
7
votes
0answers
170 views

Tortoise and hare algorithms

Consider the problem: Given an array $a[0..n]$ where $n\ge 1$ and $a[i]\in [n]$ for all $i=0,\ldots,n$ find two indices $s\neq t$ so that $a[s] = a[t]$. This problem has a stunning solution running ...
2
votes
1answer
221 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 ...
1
vote
0answers
142 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 ...
10
votes
1answer
759 views

What is the “question” that programming language theory is trying to answer?

I've been interested in various topics like Combinatory Logic, Lambda Calculus, Functional Programming for a while and have been studying them. However, unlike the "Theory of Computation" which ...
41
votes
4answers
5k views

Single author papers against my advisor's will?

I am a third year PhD student in an area of theoretical CS that would like advice for a difficult situation with my advisor. My advisor is not involved in my research projects at all. In particular, ...
5
votes
1answer
401 views

What type of mathematical problems interesting for TCS researchers?

I am Ph.D student (about to graduate) in TCS. I have worked on some problems. I have been able to publish few research paper. There are many research problems in mathematics as well in TCS. I am sure ...
2
votes
1answer
215 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?,...
7
votes
1answer
215 views

Where do people publish/submit their work on type theory?

Besides the most common venues (perhaps POPL, ICFP, LICS and FSCD), where else are papers on type theory commonly published? Especially, I'm looking for more "pure mathematical" venues/journals which ...
12
votes
3answers
577 views

Feel dissatisfied after each submission

I am a third year graduate student at a "top-20" university who works on fine-grained complexity (lots of playing with 3-SUM, OV and the usual popular hardness conjectures). I have been fairly ...
4
votes
2answers
1k views

What to do as a Theoretical computer science PhD student in a free time?

I am a mid-stage theoretical computer science student. Although I have a busy schedule, I still have a one or one a half hour in a day which I devote to reading and solving the question given Jeff ...
6
votes
2answers
405 views

Is getting post-doc difficult in theoretical computer science with few published papers? [closed]

I am a Ph.D student ( expected to graduate in few months ) works in computational mathematics. In my PhD, I have published just couple of research papers. I am willing to go for a post-doc( US, Europe,...
-2
votes
1answer
271 views

Graduate school for CS theory?

I am currently studying a bachelor's in (joint honours) Mathematics and Computer Science in the UK. I am intrigued by the sorts of problems present in theoretical computer science and I want to ...
1
vote
1answer
86 views

Cryptography protocols using graph problem instances

I personally am only aware of basic examples of public key cryptography and I haven't studied cryptography yet. I'm curious if there are circumstances in cryptography where using problem instances ...
4
votes
0answers
91 views

Naming an algorithm after a copyrighted object

In machine learning, it is common to give algorithms quirky names. What happens if you think you've found a name that's actually quite fitting for an algorithm (catchy, descriptive, etc) -- but turns ...
17
votes
1answer
859 views

The TOC Blog Aggregator is Offline

I apologise if this is off-topic. It seems that the domain name has expired. I hope some member(s) of the community here (I am not one) may know who was the administrator/owner of that site. It was ...
1
vote
0answers
140 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"...
18
votes
3answers
714 views

How to talk about theory

I realize this might be a contentious question, but this seemed like the right place to ask. Please redirect me if not. The background is that I am a "practitioner" (PhD student, I don't study CS ...
9
votes
0answers
180 views

Relatively low ambitious frontiers

What are some of the current "relatively" low ambitious frontiers for MA/PhD thesis in complexity theory class separations/containment or quantum computing? For example: In the draft version of Arora ...
1
vote
0answers
218 views

Automated theorem proving PhD

I'm looking for a university where I can do doctoral studies in automated theorem proving / computational algebra. Any ideas? Thank you!
4
votes
1answer
154 views

What is the etiquette of naming concepts after people?

There is a concept introduced by other researchers that I use in my work, and IMO it is appropriate to rename it to honor the inventors. Is it considered normal to just go ahead and name it like that ...
8
votes
1answer
335 views

Is it a bad idea to critique someone's paper in my first publication?

I am currently facing a situation that I am not sure how to handle. Basically, there is this problem $A$. Problem $A$ has been a hot topic in the past $5$ years. Last year, a paper was published in ...
1
vote
1answer
74 views

Soft Truth Values in the PSL model

This might sound like a trivial question. But since am starting out with my research in an area that is entirely new to me, I would really appreciate it if someone could kindly elucidate what Soft ...
10
votes
3answers
469 views

Is it beneficial to regularly read papers outside your field?

What do you think about regularly reading papers outside one's own field, even those which are not related to his area? My intuition is that it can give a totally different perspective or technique ...
13
votes
0answers
282 views

Algebraic topology for termination proofs

I'm reading about various ways in which termination proofs of software verifiers are built: ad-hoc methods that detect recursions, term-rewriting, synthesis of lexicographic orderings... From the ad-...
-2
votes
3answers
321 views

Algorithms with run-time $O(n\log \log n)$ [closed]

I am looking for the list of problems with runtime $O(n\log \log n)$, where $n$ is the size of the input. I tried to search on internet but did not able to find any.
1
vote
1answer
123 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 ...
5
votes
3answers
243 views

What are interesting algorithmic questions for groups in table representation?

I am currently reading about research problems in nilpotent groups ( assume table representation ). As we know that solvable group isomorphism is known to be in the (almost ) intersection of $\mathcal{...
1
vote
2answers
226 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 ...
5
votes
1answer
246 views

Are there works on “quantum parametrized complexity”?

I am a research scholar who works in Algorithms and Complexity theory, I use parameterized complexity to some extent. I don't know if researchers in quantum complexity have started using ...
2
votes
0answers
47 views

None-monotone submodular function examples

What are some interesting example of non-monotone submodular functions beside cut, directed cut in graphs?
9
votes
1answer
1k views

Is parameterized complexity going to be the future of complexity theory?

I am a research scholar who works in Algorithms and Complexity theory, I use parameterized complexity to some extent. To me it appears that researchers in parameterized complexity are very active (I ...

1
2 3 4 5
8