Lijie Chen @wjmzbmr1 Twitter profile

Last Seen Profiles

@OnOOra

@ThidaratTanggwa

@blaze64241

@Jll1s

@sin19495293

@spring_twjp

@Noom_burn

@ModasAdri159748

@ChawaSame52803

@eldreamerpunk

@chocotycho

@oporravictorr

@Matsu0_sub

@ITFglobalunion

@MaMa07072022

@Monicafabianam2

@KimigaCilantro

@MichalisRokasEU

@13th_satis

@LeraNickla33796

@JhonierVilladaa

@Jamesdean_1962

@rosecat9_

@bisk_jp

@AirRaidQBcoach

@ITinhouitin

@DoctorMoneyX

@veilleuxmartin

@attck

@jisooswiftie

@Standforfreed11

@bokeplokalmalam

@saudalkhreef

@ReverendEBeaver

@Milkchoco813

@P0KEM0MMA

Lijie Chen

@wjmzbmr1

2 years

A small personal update: I recently graduated from MIT and have now started my new postdoc at Berkeley!

19

14

1K

Lijie Chen

@wjmzbmr1

6 years

WOW, Integer Multiplication in nlogn time!

0

58

215

Lijie Chen

@wjmzbmr1

1 year

I am excited about my recent work () with Hanlin and Shuichi. In 1949, Shannon showed that almost all Boolean functions require exponential circuit complexity. However, the challenge is: how can we identify a specific Boolean function with such hardness?

3

15

216

Lijie Chen

@wjmzbmr1

3 years

Last week my Twitter account was hacked and I just got it back... Luckily it didn't start to claim I can prove P = NP😂

7

1

142

Lijie Chen

@wjmzbmr1

4 years

Happy Birthday! Besides all the listed achievements, Yao also made TCS more popular in China by founding the Yao class at Tsinghua University; that is why I got to know the field of TCS in the first place :)

Association for Computing Machinery

@TheOfficialACM

4 years

Happy birthday to Andrew Chi-Chih Yao! Yao received the 2000 #ACMTuringAward for his fundamental contributions to the theory of computation, including the complexity-based theory of pseudorandom number generation, cryptography and communication complexity.

1

13

94

0

10

142

Lijie Chen

@wjmzbmr1

4 years

Found some very nice online lecture notes about proving information-theoretical lower bounds🥳

1

19

112

Lijie Chen

@wjmzbmr1

2 years

The problem statement is extremely simple: given n d-dimensional points, find two points with maximum Euclidean distance. The best algorithms (3 decades old) run in n^{2-o(1)} time for d=omega(1), Can we show there is no n^{2-eps} algo time for super-constant d, under SETH?

Ryan Williams @[email protected]

@rrwilliams

2 years

Lijie is trying to convince everyone at the CCC rump session to work on furthest pair

3

4

84

3

5

85

Lijie Chen

@wjmzbmr1

4 years

How fast can you derandomize a T(n)-time algorithm? In this work, Roei and I show that under some plausible conjectures, one can achieve an (n T(n))-time derandomization, and this is optimal assuming the Nondeterministic Strong Exponential-Time Hypothesis (NSETH).

TCS blog aggregator

@cstheory

4 years

TR20-148 | Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost | Roei Tell, Lijie Chen

0

26

0

9

81

Lijie Chen

@wjmzbmr1

1 year

Check out our recent work with Zhenjian Lu, @IgorCarboniOliv , Hanlin Ren @dfc7027894e168c , and @rahulsanthanam !

Hanlin Ren

@dfc7027894e168c

1 year

With Lijie @wjmzbmr1 Chen, Zhenjian Lu, Igor @IgorCarboniOliv Oliveira, and Rahul @rahulsanthanam Santhanam, we present a 𝐩𝐨𝐥𝐲𝐧𝐨𝐦𝐢𝐚𝐥-𝐭𝐢𝐦𝐞 pseudodeterministic algorithm for generating primes! (1/10)

1

11

83

1

5

78

Lijie Chen

@wjmzbmr1

4 years

It's great to end 2020 by putting up a new paper by Xin Lyu and me! :) In this work, we proved a new "derandomized" XOR Lemma, which implies super strong correlation bounds against F_2-polynomials, as well as P^NP construction of extremely rigid matrices!

2

3

64

Lijie Chen

@wjmzbmr1

5 years

Wow, a very interesting paper about MCSP! A big open question about MCSP (Given a truth-table, find the smallest circuit computing it) is whether it's NP-complete. This work (among other things) shows that if we consider MCSP for multi-output functions, then it is NP-complete!

TCS blog aggregator

@cstheory

5 years

TR20-021 | NP-Hardness of Circuit Minimization for Multi-Output Functions | Rahul Ilango, Bruno Loff, Igor Carboni Oliveira

0

20

0

11

52

Lijie Chen

@wjmzbmr1

2 years

Heading to CCC 2022, the first in-person conference for me since covid. Really looking forward to it!

2

0

54

Lijie Chen

@wjmzbmr1

4 years

An exciting work by Rahul Ilango which is finally online! It shows the partial version of MCSP (given a truth-table of 0,1 and "don't care", find the minimum circuit consistent with this truth-table) is not in P under ETH, together with many other exciting results.

TCS blog aggregator

@cstheory

4 years

TR20-183 | Constant Depth Formula and Partial Function Versions of MCSP are Hard | Rahul Ilango

0

14

1

6

54

Lijie Chen

@wjmzbmr1

5 years

Finally my lovely paper with Ofer Grossman on distribute computing is out!! It took a whole year to finish this project so I am super happy right now :)

2

1

52

Lijie Chen

@wjmzbmr1

5 months

@pinkfloydie @rrwilliams Congratulations to my Ph.D. advisor from a proud student!!! This was the paper that I read (almost) ten years ago that got me into complexity theory, and it has continued to inspire me ever since😃

0

53

Lijie Chen

@wjmzbmr1

4 years

A pretty interesting work by Zhenjian, Xin, Igor, and me! It was known that PRGs imply average-case hardness under *a certain distribution*, but it's unclear whether PRGs imply average-case hardness under the *uniform distribution*. In this paper, we show they do!

TCS blog aggregator

@cstheory

4 years

TR21-040 | Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC1 | Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Carboni Oliveira

0

1

15

0

2

44

Lijie Chen

@wjmzbmr1

4 years

This a very surprising work, showing that there is a function in AC^0 which requires nearly-cubic size De Morgan formulas to compute. I kind of thought this can't be proved using random restrictions but they did it with random restrictions.

0

2

42

Lijie Chen

@wjmzbmr1

2 years

The upcoming FOCS 2022 will include a workshop titled New Directions in Derandomization. The workshop's format is a self-contained mini-course, focusing on the fast-paced developments from the last few years (the event will be in-person only).

New Directions in Derandomization Workshop

In the last three years there's been fast-paced progress in the area of derandomization: Upending a classical paradigm, opening new directions of study, and discovering exciting connections with...

sites.google.com

1

3

42

Lijie Chen

@wjmzbmr1

4 years

In the summer there will be an online complexity seminar hosted via zoom! The first talk (6/18 noon EST) is by Rahul Ilango about recent results on depth-d Boolean formulas obtained by a form of lifting and applications to MCSP and lower bounds.

0

4

41

Lijie Chen

@wjmzbmr1

4 years

An interesting work I did with my amazing coauthors (Badih, Ravi, and Pasin) on the (non-interactive) local and shuffle model of DP! TL;DR: CountDisticnt is extremely hard for local and 1-message shuffle DP, but surprisingly easy for shuffle DP with 1/2+o(1) expected messages.

TCS blog aggregator

@cstheory

4 years

On Distributed Differential Privacy and Counting Distinct Elements

0

1

5

2

5

39

Lijie Chen

@wjmzbmr1

4 years

wow!

Gautam Kamath

@thegautamkamath

4 years

Rahul Ilango's year in best student papers (all solo): - ITCS 2020 - CCC 2020 - FOCS 2020 All on the challenging MSCP. Did I mention he just finished his first-year as a grad student? @rrwilliams must be a proud advisor!

3

10

218

1

37

Lijie Chen

@wjmzbmr1

6 years

wow, super cool algorithm for subset sum from a high student (!) and a friend of mine. Indeed this paper makes use of some OI (olympiad in informatics) tricks, very impressive to me :-)

A Simple Near-Linear Pseudopolynomial Time Randomized Algorithm...

Given a multiset $S$ of $n$ positive integers and a target integer $t$, the Subset Sum problem asks to determine whether there exists a subset of $S$ that sums up to $t$. The current best...

arxiv.org

2

11

38

Lijie Chen

@wjmzbmr1

5 years

@rrwilliams @firebat03 Thanks so much, Ryan!! This work would certainly be impossible without all your invaluable encouragements and insightful discussions!! (just as my other works) I just realized how much I have grown (as a complexity student) during the last two years with you :)

2

0

38

Lijie Chen

@wjmzbmr1

4 years

@rrwilliams This is certainly not possible at all without your fantastic guidance in the past years!! Now I got some support from IBM to work with you for two more years🥰

0

36

Lijie Chen

@wjmzbmr1

3 years

There is a paper on ECCC that simultaneously claims to break LWE and prove super-polynomial lower bounds against TC^0.

TCS blog aggregator

@cstheory

3 years

TR21-179 | Smoothed Complexity of Learning Disjunctive Normal Forms, Inverting Fourier Transforms, and Verifying Small Circuits | tatsuie tsukiji

0

3

37

Lijie Chen

@wjmzbmr1

4 years

Check the following STOC talk by Ce Jin @jcvbcn on hardness magnification! We showed that for some problems one can (non-trivially) prove an n^{2-eps} lower bound while improving that to n^{2+eps} would imply super-poly lower bounds.

Session 10B - Sharp Threshold Results for Computational Complexity

null

www.youtube.com

1

2

35

Lijie Chen

@wjmzbmr1

6 years

Gonna talk about a new average-case circuit lower bound next Monday at Harvard :-)

1

33

Lijie Chen

@wjmzbmr1

2 years

@rrwilliams Thanks! I am incredibly fortunate to be advised by the best professor on earth!🥰 (Also, sorry for writing such a long thesis😳)

0

1

33

Lijie Chen

@wjmzbmr1

4 years

Just successfully got a PS5!

2

0

31

Lijie Chen

@wjmzbmr1

5 years

Just heard that my friend's F1 visa application has been checked for 3 months and he has to delay enrollment... feeling so bad about it😢

1

28

Lijie Chen

@wjmzbmr1

6 years

A very cute paper by Ruosong and I ("Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols" ) 😀 (to appear in ITCS 2019), about interesting connections between quantum communication protocols and classical fine-grained counting!

Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols

The polynomial method from circuit complexity has been applied to several fundamental problems and obtains the state-of-the-art running times. As observed in [Alman and Williams, STOC 2017],...

arxiv.org

0

5

29

Lijie Chen

@wjmzbmr1

4 months

Yichuan is amazing! :)

Jelani Nelson

@minilek

4 months

Another student makes a significant contribution to streaming! Yichuan Wang, visiting undergrad from Tsinghua, proves a lower bound on approx counting implying optimality of both Misra-Gries (aka "Frequent") from 1982, + the recent quantiles algo. 1/

2

12

123

0

29

Lijie Chen

@wjmzbmr1

2 years

Amazing and beautiful work (both conceptually and technically). They proved (among many things) that the "quantum Merkle tree" by Ramis and me indeed works, and under a condition even weaker than OWFs! (We conjectured the security in a strong model) See Fermi's thread for detail.

Fermi Ma

@fermi_ma

2 years

New paper out today with Sam Gunn, Nathan Ju ( @nathanju34 ), and Mark Zhandry. This project began with a simple question: what does it mean to commit to a quantum state? (1/16)

3

14

85

0

4

26

Lijie Chen

@wjmzbmr1

6 years

WOW, this is an incredible result!

TCS blog aggregator

@cstheory

6 years

TR19-003 | Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0 | Alexander A. Sherstov, Pei Wu

0

7

0

3

25

Lijie Chen

@wjmzbmr1

6 years

Had a wonderful semester at the Simons Institute!

0

1

26

Lijie Chen

@wjmzbmr1

4 years

Wow! This is a big breakthrough in quantum query complexity!

TCS blog aggregator

@cstheory

4 years

TR20-127 | $k$-Forrelation Optimally Separates Quantum and Classical Query Complexity | Nikhil Bansal, Makrand Sinha

0

4

26

0

25

Lijie Chen

@wjmzbmr1

4 years

Very impressive! Resolved the multi-message shuffle complexity of selection/parity-learning without any restriction on the number of messages! (previously even the two-message case is open)

TCS blog aggregator

@cstheory

4 years

The Limits of Pan Privacy and Shuffle Privacy for Learning and Estimation

0

3

6

1

2

23

Lijie Chen

@wjmzbmr1

2 years

Check out the two talks at the recent @DIMACSCenter workshop by Roei Tell and me on some recent developments in derandomization! and

Lijie Chen: Recent Developments in Derandomization I

Lijie Chen presents "Recent Developments in Derandomization I" at the DIMACS Workshop on Meta-Complexity, Barriers, and Derandomization, April 25-27, 2022.

www.youtube.com

3

24

Lijie Chen

@wjmzbmr1

6 years

It is so amazing that Andrew Yao is still proving theorem even recently!

1

0

23

Lijie Chen

@wjmzbmr1

1 year

Diagonalization requires three quantifiers and results in an exponentially hard language in Sigma_3 EXP. In our recent work, we finally made progress by showing that Sigma_2 EXP (and indeed, S_2 EXP) already require a maximum (2^n/n) circuit complexity!

1

22

Lijie Chen

@wjmzbmr1

4 years

Also check out STOC talk by Hanlin Ren @dfc7027894e168c on new average-case circuit lower bounds! We showed non-deterministic quasi-polynomial time is strongly-average case hard for ACC^0, while previously no such result is known even for AC^0[2].

Session 10B - Strong Average-Case Circuit Lower Bounds from Non-tri...

A full version of the talk (given by Lijie) can be found at https://www.youtube.com/watch?v=85XS9H_U4q0.

www.youtube.com

1

3

21

Lijie Chen

@wjmzbmr1

5 years

Nice explanation of the paper (the first hardness magnification part) of Roei and me by Emanuele Viola :)

TCS blog aggregator

@cstheory

5 years

We knew the best threshold-circuit lower bounds long ago

0

1

10

1

0

21

Lijie Chen

@wjmzbmr1

6 years

Just heard that 5 undergrads in Yao class have got some SODA papers...😮

0

19

Lijie Chen

@wjmzbmr1

5 years

A super interesting work!! Maybe one can build a "practical" complexity PRG for derandomization in the real world using this paper?

TCS blog aggregator

@cstheory

5 years

TR19-099 | Nearly Optimal Pseudorandomness From Hardness | Dean Doron, David Zuckerman, Dana Moshkovitz, Justin Oh

0

2

12

0

16

Lijie Chen

@wjmzbmr1

6 years

watched fantastic beast 2, felt like I was in a GCT talk (didn’t understand what’s going on).

0

1

18

Lijie Chen

@wjmzbmr1

6 years

Berkeley's air today reminds me of Beijing, that is a bit nostalgic. #AirQuality

0

2

17

Lijie Chen

@wjmzbmr1

4 years

Wow, looks like a groundbreaking work

TCS blog aggregator

@cstheory

4 years

TR20-126 | Indistinguishability Obfuscation from Well-Founded Assumptions | Aayush Jain, Huijia Lin, Amit Sahai

0

1

17

0

1

18

Lijie Chen

@wjmzbmr1

2 years

@ccanonne_ Probably this will reduce the average life span of TCS ppl by 10 or 20 years...

0

16

Lijie Chen

@wjmzbmr1

1 year

In the language of complexity theory, the goal is to identify the smallest complexity class containing a language with exponential circuit complexity. For the past four decades, the only known method to construct such a hard function has been diagonalization.

1

2

15

Lijie Chen

@wjmzbmr1

2 years

@dfc7027894e168c There is also a student from Tsinghua (who shared the best student paper award) who couldn't go to STOC 2022 and his visa application is rejected multiple times... This is super disappointing😡

1

16

Lijie Chen

@wjmzbmr1

10 months

@nutanlimaye This is a very nice and elegant paper, tree evaluation in almost log space :)

0

16

Lijie Chen

@wjmzbmr1

2 years

The 2018 paper is actually the first paper during my PhD. Since then I have thought about this cute problem a lot but couldn't figure out how to further bring down the dimension to any d = omega(1). I suspect some deep math results from AG codes or number theory could be useful..

1

0

14

Lijie Chen

@wjmzbmr1

6 years

A very nice paper! The reduction in this paper is super cool and kind of unexpected to me. (It builds the reduction by inspecting at the minimum circuit size modulo some prime p, wow)

TCS blog aggregator

@cstheory

6 years

TR19-021 | $AC^0[p]$ Lower Bounds and NP-Hardness for Variants of MCSP | Rahul Ilango

0

7

0

2

14

Lijie Chen

@wjmzbmr1

5 years

looks very cool!

0

11

Lijie Chen

@wjmzbmr1

4 years

@dfc7027894e168c This looks incredible! It seems to involve case analysis for >=100 cases (!!), I wonder if such an argument can be formulated in Coq to check automatically...😄

1

0

13

Lijie Chen

@wjmzbmr1

1 year

@rahulsanthanam @StephenOrnes @IgorCarboniOliv @dfc7027894e168c Hanlin @dfc7027894e168c is truly amazing!

1

0

13

Lijie Chen

@wjmzbmr1

5 years

WOW

TCS blog aggregator

@cstheory

5 years

TR19-179 | Towards Optimal Separations between Quantum and Randomized Query Complexities | Avishay Tal

0

1

15

1

11

Lijie Chen

@wjmzbmr1

5 years

wow

1

2

12

Lijie Chen

@wjmzbmr1

3 years

In particular, it claims that (Lemma 1.31) TC^0 can be simulated by depth-2 quasi-poly-size Symmetric-of-AND circuits. This would be a major breakthrough in circuit complexity if true. I tried to read the proof but it is a bit hard to verify... I wonder how other people think...

0

1

12

Lijie Chen

@wjmzbmr1

7 years

Happy lunar new year!!! :-)

0

11

Lijie Chen

@wjmzbmr1

5 years

@teddy_megumi 感觉我很多work都是喝酒的时候想出来的。。。

2

0

11

Lijie Chen

@wjmzbmr1

4 years

I was working on this model during my summer internship at Google, and was caught by this amazing problem but couldn't figure out how to deal with an unbounded number of messages. Very happy to see this being resolved!

1

0

11

Lijie Chen

@wjmzbmr1

2 years

Topics include non-black-box derand. techniques, which replace classical PRGs; superfast algorithms and free lunch theorems, for algorithms and for proof systems; new connections between derand. and other areas in TCS; and the range avoidance problem for explicit constructions.

0

10

Lijie Chen

@wjmzbmr1

4 years

If this conference version is too short for you, there is another 1-hour long talk for the same paper in IAS :)

Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomi...

Computer Science/Discrete Mathematics Seminar ITopic: Strong Average-Case Circuit Lower Bounds from Non-trivial DerandomizationSpeaker: Lijie ChenAffiliation...

www.youtube.com

1

0

10

Lijie Chen

@wjmzbmr1

2 years

@mahdi_tcs Well, P = L? (L is log-space)

0

10

Lijie Chen

@wjmzbmr1

3 months

@minilek @meghal_bagel @msinghal55 @HongxunWu Congratulations! It's super well-deserved!!

0

10

Lijie Chen

@wjmzbmr1

6 years

WOW

Ainesh Bakshi

@AineshBakshi

6 years

Linear Programming in "almost" matrix multiplication time! Wow!

0

2

8

0

9

Lijie Chen

@wjmzbmr1

6 years

looks super cool!

Clément Canonne

@ccanonne_

6 years

Looking forward to read this new paper by Mingda Qiao and Greg Valiant: This blows my mind. No distributional assumption made, yet non-trivial prediction possible. (I *would* link that to my #fintech friends, but don't have any).

3

10

71

0

8

Lijie Chen

@wjmzbmr1

5 years

@fortnow Bootstrapping Results for Deep Neural Networks? Maybe my paper can then be published in ICML...

0

9

Lijie Chen

@wjmzbmr1

6 years

@hoonoseme Thanks so much!! 😊

1

0

9

Lijie Chen

@wjmzbmr1

3 years

@thegautamkamath Really enjoyed it with @jcvbcn !

1

0

8

Lijie Chen

@wjmzbmr1

2 years

Under SETH, it's straightforward to show there is no n^{2-eps} algo when d = O(log n). In 2017, Ryan Williams improved the dimension to d = O(polyloglog n), and I further improved the dimension to d = 2^{O(log* n)} in 2018. But the progress has then stopped :(

1

0

8

Lijie Chen

@wjmzbmr1

3 years

@cheraghchi @algo_class I thought one reason may be that Karp reduction is important for the NP vs coNP distinction (SAT and UNSAT are equivalent under Cook reduction). I am not sure though... Karp reductions are also required for classes like NP cap coNP.

1

0

8

Lijie Chen

@wjmzbmr1

6 years

@cstheory a super interesting problem I had worked on (like 2 years ago); this application of polynomial-method is something I have never seen before, a truly amazing work!

0

1

8

Lijie Chen

@wjmzbmr1

2 years

@nutanlimaye @vclecomte @rahulsanthanam @dfc7027894e168c Hanlin already explained, but maybe let me echo that this is a FANTASTIC result and I think it's probably the most important development on the hardness of MCSP so far

0

8

Lijie Chen

@wjmzbmr1

6 years

@rrwilliams This paper is awesome!! Expecting to see more cool stuffs in fine-grained complexity coming from AG codes :)

0

7

Lijie Chen

@wjmzbmr1

7 years

First paper as a graduate student! Thanks so much for my omnipotent advisor!!! :-) One cute result is that finding l_2-farthest pair in 2^logstar n dimensions need essentially n^2 time

TCS blog aggregator

@cstheory

7 years

TR18-026 | On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product | Lijie Chen

0

7

Lijie Chen

@wjmzbmr1

2 years

There are also two other great talks on the same topic in the workshop (), by Nicollas Sdroievski and Yanyi Liu. And of course many more other fantastic talks by many great speakers! See for all the videos.

DIMACS CCICADA

Videos of workshops and seminars organized by DIMACS and CCICADA

www.youtube.com

1

7

Lijie Chen

@wjmzbmr1

1 year

Here are the slides of my talk on this work given at Cornell University this month: , which contains a high-level overview of the proof!

0

6

Lijie Chen

@wjmzbmr1

6 years

@ilyaraz2 looks like many ppl think it is correct (), as this is from two leading experts in that direction. But I guess there is no serious verification yet as it only appeared a week ago?

0

1

6

Lijie Chen

@wjmzbmr1

2 years

The following two questions regarding derandomization have attracted some recent interest: 1. what is the fastest derandomization? 2. what is the minimum assumption for derandomization? The aforementioned talks explored these two questions for both algorithms and proof systems.

0

6

Lijie Chen

@wjmzbmr1

4 years

@BooleanAnalysis @rrwilliams Chen-Tell also showed assuming similar assumptions, one can derand BPT[T] in TIME[T n^eps] "on average" instead of worst-case. In that sense "in the practice" one may still derand BPT[T] with almost no overhead...

0

1

6

Lijie Chen

@wjmzbmr1

4 years

@BooleanAnalysis @rrwilliams Based on Wil16 one can also show based on " #SAT cannot be solved by co-NP type 2^{0.99n} circuits", this n factor blow-up of BPT[T] in TIME[T n] is also optimal, for every T.😄 Perhaps this means one can try to refute NSETH by finding faster derandomization!

1

6

Lijie Chen

@wjmzbmr1

4 years

@_shmcg @BooleanAnalysis Sipser's paper is indeed very ahead of its time! In fact, this result can be strengthened to give quadratic overhead running time derandomization, by plugging in a modern extractor that is much stronger than what is known to Sipser in the 80s.

0

2

6

Lijie Chen

@wjmzbmr1

5 years

@teddy_megumi water bureau...作者是水利局的？

0

5

Lijie Chen

@wjmzbmr1

5 years

Looks awesome!

0

1

5

Lijie Chen

@wjmzbmr1

4 years

Complementary to the recent result by Cheu-Ullman, (they proved tight bounds for selection in the robust shuffle model with unbounded messages) We also obtain some better sample lower bounds when the number of messages is not so big and without robustness.

0

6

Lijie Chen

@wjmzbmr1

4 years

The proof of the above result builds on the n/log n lower bound for CountDisticnt in the property testing model (estimating the unseen), generalizing their method to bound the TV distance between mixtures of multi-dimensional Poisson distributions using moment-matching.

1

0

5

Lijie Chen

@wjmzbmr1

6 years

wow, super cool!

John Preskill

@preskill

6 years

In my recent survey of quantum computing applications, I asked whether the Kerenidis-Prakash q. algorithm for recommendation systems is exponentially faster than the best classical algorithm. I didn't expect the answer (no) to come from an 18 year old.

7

60

183

0

5

Lijie Chen

@wjmzbmr1

6 years

@orz_wyh2000 I guess no... but I can make the slides public :-)

0

5

Lijie Chen

@wjmzbmr1

6 years

@rrwilliams 🙂🙃 means one accept and one reject?

1

0

5

Lijie Chen

@wjmzbmr1

4 years

@BooleanAnalysis @rrwilliams In CT21, the assumption is still against normal computation: (1)TIME[2^{kn}] is not in TIME[2^{0.99kn}]/2^{0.99n}) plus (2)OWFs. It's interesting to note that (1) is indeed implied of any PRG-based derand of BPT[T] in TIME[T n]. So (1) is kind of <=> to fast derand (modulo OWF).

1

5

Lijie Chen

@wjmzbmr1

2 years

@pravesh @jfitzsimons @rrwilliams Sorry that I forgot, my bad. Ryan's paper is here , and it also contains lots of discussions on previous work (like the best algorithms). My subsequent work is here

On the Difference Between Closest, Furthest, and Orthogonal Pairs:...

Point location problems for $n$ points in $d$-dimensional Euclidean space (and $\ell_p$ spaces more generally) have typically had two kinds of running-time solutions: * (Nearly-Linear) less than...

arxiv.org

0

4

Lijie Chen

@wjmzbmr1

6 years

@ewintang @ilyaraz2 @hoonoseme That is certain!! Congratulations!!

0

4

Lijie Chen

@wjmzbmr1

2 months