Network profile

argentpepper

Reputation

2,241

2.3k
2.1k
2k

2018
2019
2020
2021

Top tag

cc.complexity-theory

Next privilege

2,500 Rep.

Create tag synonyms

Badges

13

26

Newest

Yearling

Next badge

68/80

Impact

68 posts edited

5 helpful flags

21 votes cast

Questions (15)

Votes Activity Newest

48	What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?
25	What is $\mathsf{NP}$ restricted to linear size witnesses?
20	Interesting PCP characterization of classes smaller than P?
12	What is the relationship between $\mathsf{PLS}$ and $\mathsf{APX}$?
10	Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?

View more →

Reputation (2,241)

+20	What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?
+10	In what class are randomized algorithms that err with exactly 25% chance?
+10	What is $\mathsf{NP}$ restricted to linear size witnesses?
+10	What is the relationship between $\mathsf{PLS}$ and $\mathsf{APX}$?

View more →

Answers (6)

Votes Activity Newest

27	What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?
4	Finding the sparsest solution to a system of linear equations
4	Hardest problems to approximate
3	Problems in $\text{PSPACE} \cap \text{Co-NP-Hard}$
2	How big is NSC^k?

View more →

Tags (28)

33 cc.complexity-theory × 17	4 clique
31 complexity-classes × 8	4 linear-algebra
27 structural-complexity × 4	4 sparse-matrix
27 conditional-results × 3	4 np-hardness
4 approximation-hardness × 2	4 matrices

View more →

Bookmarks (5)

Votes Activity Newest Views Added

134	Problems Between P and NPC
53	Is there a gap amplification type of result for the Graph Isomorphism Problem?
34	Approximation algorithms for problems in P
11	History and status of the graph matching problem
2	Separation of limited nondeterminism classes?

Accounts (17)

	Stack Overflow	3,336 rep	1 gold badge27 silver badges42 bronze badges
	Theoretical Computer Science	2,241 rep	13 silver badges26 bronze badges
	TeX - LaTeX	492 rep	3 silver badges13 bronze badges
	Mathematics	454 rep	2 silver badges15 bronze badges
	Ask Ubuntu	277 rep	1 gold badge2 silver badges10 bronze badges

Badges (24)

Recent Class Name

Yearling × 9	Nice Answer
Nice Question × 6	Necromancer
Good Question × 2	Self-Learner
Good Answer	Curious
Popular Question	Informed

View more →

Active bounties (0)

Active Offered Earned

This user has no active bounties

Votes cast (21)

all time			by type
11	up		10	question
10	down		11	answer

Theoretical Computer Science Stack Exchange works best with JavaScript enabled