User gradstudent

3

votes

1

answer

200

views

What does it mean to “construct a PCP”?

Dec 27 '16 at 8:26 Yuval Filmus 234k

3

votes

1

answer

78

views

A certain submatrix of the correlation polytope

complexity-theory np-complete optimization np-hard np

Mar 8 '16 at 20:03 Yuval Filmus 234k

2

votes

0

answers

48

views

About gradient descent on non-convex functions

machine-learning reference-request gradient-descent

Mar 6 '18 at 23:49 gradstudent 493

2

votes

1

answer

184

views

Lower bounds on regret

optimization online-algorithms

Feb 17 '18 at 23:13 Yuval Filmus 234k

2

votes

0

answers

38

views

From SETH to circuit lowerbounds

complexity-theory computability lower-bounds circuits

Jan 22 '18 at 15:48 gradstudent 493

2

votes

0

answers

85

views

Vandermonde matrix and its binary representation

arithmetic linear-algebra coding-theory error-correcting-codes

Oct 10 '17 at 1:29 gradstudent 493

2

votes

1

answer

55

views

What are the gap functions in the $AC$ hierarchy?

complexity-theory computability time-complexity np-complete circuits

Oct 2 '16 at 16:48 Emil Jeřábek 446

2

votes

0

answers

34

views

A particular type of SOS hardness proof

complexity-theory optimization np-complete np-hard np

Apr 1 '16 at 16:20 D.W.♦ 125k

2

votes

1

answer

105

views

Is a degree-$d$ pseudo distribution always a relaxation?

np-complete optimization np-hard np

Mar 17 '16 at 17:56 Yuval Filmus 234k

2

votes

1

answer

223

views

About the notation of XOR-SAT

np-complete optimization np-hard np

Mar 13 '16 at 23:01 gradstudent 493

2

votes

1

answer

54

views

Is there a degree-2 SOS rewriting of the Goemans-Williamson rounding?

complexity-theory np-complete optimization np-hard

Feb 15 '16 at 16:55 Community♦ 1

2

votes

1

answer

213

views

About the Max-Cut SDP

complexity-theory np-complete optimization np-hard convex-hull

Feb 10 '16 at 7:29 Yuval Filmus 234k

1

vote

0

answers

39

views

About sign-rank of Boolean functions

complexity-theory circuits boolean-algebra

Feb 19 '18 at 17:06 gradstudent 493

1

vote

1

answer

35

views

Two definitions of the Reed-Muller code

complexity-theory combinatorics coding-theory

Jun 16 '17 at 0:02 D.W.♦ 125k

1

vote

0

answers

227

views

About Barron's theorem in neural nets

machine-learning neural-networks

Jan 16 '17 at 17:36 gradstudent 493

1

vote

1

answer

51

views

Is this some kind of hashing?

optimization machine-learning computational-geometry hash hashing

Apr 19 '16 at 1:48 jbapple 3,022

1

vote

1

answer

35

views

About the interpretation of the SOS hardness results of the planted Max-Clique problem

complexity-theory optimization np-complete np-hard np

Apr 12 '16 at 22:46 Community♦ 1

1

vote

0

answers

25

views

About the complexity of learning probabilistic graphical models

complexity-theory reference-request machine-learning graphical-models

Mar 26 '16 at 10:45 Raphael♦ 68.4k

1

vote

0

answers

40

views

A question about SOS duality

complexity-theory np-complete np-hard np

Mar 22 '16 at 0:46 gradstudent 493

1

vote

1

answer

28

views

Is there an example of how SOS can be used to show infeasibility of a set of multivariable equations?

complexity-theory np-complete optimization np-hard np

Feb 29 '16 at 16:46 Yuval Filmus 234k

1

vote

0

answers

33

views

About the SOS degree of a function and optimization algorithms for the function

complexity-theory computability np-complete np-hard computation-models

Feb 24 '16 at 22:13 Community♦ 1

1

vote

1

answer

72

views

About showing algorithmic gap instance for the Goemans-Williamson SDP

complexity-theory time-complexity approximation

Feb 3 '16 at 15:55 Yuval Filmus 234k

0

votes

1

answer

28

views

Taking mod $2$ with LTF gates

complexity-theory circuits boolean-algebra

Oct 19 '17 at 12:36 Yuval Filmus 234k

0

votes

1

answer

64

views

LTF circuits and $AC^0$

complexity-theory circuits boolean-algebra

Oct 19 '17 at 7:09 Yuval Filmus 234k

0

votes

0

answers

54

views

Is there a non-linear version of ICA?

machine-learning approximation learning-theory sparse-matrices

Apr 7 '16 at 16:54 gradstudent 493

-1

votes

1

answer

27

views

Some questions about the depth hierarchy of threshold circuits

complexity-theory complexity-classes circuits

Oct 7 '17 at 16:31 Yuval Filmus 234k

-1

votes

1

answer

91

views

How fast can one compute the power of a number?

time-complexity runtime-analysis polynomial-time arithmetic modular-arithmetic

Apr 27 '16 at 13:08 Community♦ 1

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

27 Questions

What does it mean to “construct a PCP”?

A certain submatrix of the correlation polytope

About gradient descent on non-convex functions

Lower bounds on regret

From SETH to circuit lowerbounds

Vandermonde matrix and its binary representation

What are the gap functions in the $AC$ hierarchy?

A particular type of SOS hardness proof

Is a degree-$d$ pseudo distribution always a relaxation?

About the notation of XOR-SAT

Is there a degree-2 SOS rewriting of the Goemans-Williamson rounding?

About the Max-Cut SDP

About sign-rank of Boolean functions

Two definitions of the Reed-Muller code

About Barron's theorem in neural nets

Is this some kind of hashing?

About the interpretation of the SOS hardness results of the planted Max-Clique problem

About the complexity of learning probabilistic graphical models

A question about SOS duality

Is there an example of how SOS can be used to show infeasibility of a set of multivariable equations?

About the SOS degree of a function and optimization algorithms for the function

About showing algorithmic gap instance for the Goemans-Williamson SDP

Taking mod $2$ with LTF gates

LTF circuits and $AC^0$

Is there a non-linear version of ICA?

Some questions about the depth hierarchy of threshold circuits

How fast can one compute the power of a number?