article

Hardness Amplification Proofs Require Majority

Authors:

Ronen Shaltiel,

Emanuele ViolaAuthors Info & Claims

SIAM Journal on Computing, Volume 39, Issue 7

Pages 3122 - 3154

https://doi.org/10.1137/080735096

Published: 01 July 2010 Publication History

Abstract

Hardness amplification is the fundamental task of converting a $\delta$-hard function $f:\{0,1\}^n\to\{0,1\}$ into a $(1/2-\epsilon)$-hard function $\mathit{Amp}(f)$, where $f$ is $\gamma$-hard if small circuits fail to compute $f$ on at least a $\gamma$ fraction of the inputs. In this paper we study the complexity of black-box proofs of hardness amplification. A class of circuits $\mathcal{D}$ proves a hardness amplification result if for any function $h$ that agrees with $\mathit{Amp}(f)$ on a $1/2+\epsilon$ fraction of the inputs there exists an oracle circuit $D\in\mathcal{D}$ such that $D^h$ agrees with $f$ on a $1-\delta$ fraction of the inputs. We focus on the case where every $D\in\mathcal{D}$ makes nonadaptive queries to $h$. This setting captures most hardness amplification techniques. We prove two main results: (1) The circuits in $\mathcal{D}$ “can be used” to compute the majority function on $1/\epsilon$ bits. In particular, when $\epsilon\leq1/\log^{\omega(1)}n$, $\mathcal{D}$ cannot consist of oracle circuits that have unbounded fan-in, size $\mathrm{poly}(n)$, and depth $O(1)$. (2) The circuits in $\mathcal{D}$ must make $\Omega\left(\log(1/\delta)/\epsilon^2\right)$ oracle queries. Both our bounds on the depth and on the number of queries are tight up to constant factors. Our results explain why hardness amplification techniques have failed to transform known lower bounds against constant-depth circuit classes into strong average-case lower bounds. Our results reveal a contrast between Yao's XOR lemma ($\mathit{Amp}(f):=f(x_1)\oplus\cdots\oplus f(x_t)\in\{0,1\}$) and the direct-product lemma ($\mathit{Amp}(f):=f(x_1)\circ\cdots\circ f(x_t)\in\{0,1\}^t$; here $\mathit{Amp}(f)$ is non-Boolean). Our results (1) and (2) apply to Yao's XOR lemma, whereas known proofs of the direct-product lemma violate both (1) and (2). One of our contributions is a new technique for handling “nonuniform” reductions, i.e., the case when $\mathcal{D}$ contains many circuits.

References

[1]

M. Agrawal, Hard sets and pseudo-random generators for constant depth circuits, in Proceedings of the 21st Annual Conference on the Foundations of Software Technology and Theoretical Computer Science, Springer-Verlag, Berlin, 2001, pp. 58-69.

[2]

M. Ajtai, $\Sigma \sp{1}\sb{1}$-formulae on finite structures, Ann. Pure Appl. Logic, 24 (1983), pp. 1-48.

[3]

M. Ajtai, Approximate counting with uniform constant-depth circuits, in Advances in Computational Complexity Theory (New Brunswick, NJ, 1990), AMS, Providence, RI, 1993, pp. 1-20.

[4]

M. Ajtai and M. Ben-Or, A theorem on probabilistic constant depth computation, in Proceedings of the 16th Annual Symposium on Theory of Computing (STOC), ACM, New York, 1984, pp. 471-474.

[5]

N. Alon and R. Beigel, Lower bounds for approximations by low degree polynomials over ${Z}_m$, in Proceedings of the 16th Annual Conference on Computational Complexity (CCC), IEEE Computer Society Press, Washington, D.C., 2001, pp. 184-187.

[6]

J. Aspnes, R. Beigel, M. Furst, and S. Rudich, The expressive power of voting polynomials, Combinatorica, 14 (1994), pp. 135-148.

[7]

L. Babai, L. Fortnow, and C. Lund, Nondeterministic exponential time has two-prover interactive protocols, Comput. Complexity, 1 (1991), pp. 3-40.

[8]

L. Babai, L. Fortnow, N. Nisan, and A. Wigderson, BPP has subexponential time simulations unless EXPTIME has publishable proofs, Comput. Complexity, 3 (1993), pp. 307-318.

[9]

L. Babai, N. Nisan, and M. Szegedy, Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs, J. Comput. System Sci., 45 (1992), pp. 204-232.

[10]

D. Beaver and J. Feigenbaum, Hiding instances in multioracle queries, in Proceedings of the 7th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Comput. Sci. 415, Springer-Verlag, Berlin, 1990, pp. 37-48.

[11]

R. Beigel, The polynomial method in circuit complexity, in Proceedings of the 8th Annual Structure in Complexity Theory Conference, IEEE Computer Society Press, Washington, D.C., 1993, pp. 82-95.

[12]

R. Beigel, When do extra majority gates help? ${\rm polylog}(N)$ majority gates are equivalent to one, Comput. Complexity, 4 (1994), pp. 314-324.

[13]

A. Bogdanov and L. Trevisan, Average-case complexity, Found. Trends Theor. Comput. Sci., 2 (2006), pp. 1-106.

[14]

A. Bogdanov and L. Trevisan, On worst-case to average-case reductions for NP problems, SIAM J. Comput., 36 (2006), pp. 1119-1159.

[15]

J. Bourgain, Estimation of certain exponential sums arising in complexity theory, C. R. Math. Acad. Sci. Paris, 340 (2005), pp. 627-631.

[16]

J.-Y. Cai, A. Pavan, and D. Sivakumar, On the hardness of the permanent, in Proceedings of the 16th International Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Comput. Sci. 1563, Springer-Verlag, Berlin, 1999, pp. 90-99.

[17]

R. Canetti, G. Even, and O. Goldreich, Lower bounds for sampling algorithms for estimating the average, Inform. Process. Lett., 53 (1995), pp. 17-25.

[18]

T. M. Cover and J. A. Thomas, Elements of Information Theory, Wiley Ser. Telecom., Wiley-Interscience, Hoboken, NJ, 2006.

[19]

I. Csiszar and J. G. Korner, Information Theory: Coding Theorems for Discrete Memoryless Systems, Academic Press, New York, 1982.

[20]

D. P. Dubhashi and A. Panconesi, Concentration of Measure for the Analysis of Randomized Algorithms, Cambridge University Press, Cambridge, UK, 2009.

[21]

J. Edmonds, R. Impagliazzo, S. Rudich, and J. Sgall, Communication complexity towards lower bounds on circuit depth, Comput. Complexity, 10 (2001), pp. 210-246.

[22]

U. Feige and C. Lund, On the hardness of computing the permanent of random matrices, Comput. Complexity, 6 (1996), pp. 101-132.

[23]

M. L. Furst, J. B. Saxe, and M. Sipser, Parity, circuits, and the polynomial-time hierarchy, Math. Systems Theory, 17 (1984), pp. 13-27.

[24]

O. Goldreich, A Sample of Samplers—a Computational Perspective on Sampling (Survey), Technical Report TR97-020, Electronic Colloquium on Computational Complexity (ECCC), 1997; available online at http://eccc.uni-trier.de/report/1997/020/.

[25]

O. Goldreich and L. Levin, A hard-core predicate for all one-way functions, in Proceedings of the 21st Annual Symposium on Theory of Computing (STOC), ACM, New York, 1989, pp. 25-32.

[26]

O. Goldreich, N. Nisan, and A. Wigderson, On Yao's XOR Lemma, Technical Report TR95-050, Electronic Colloquium on Computational Complexity (ECCC), 1995; available online at http://eccc.uni-trier.de/report/1995/050/.

[27]

S. Goldwasser, D. Gutfreund, A. Healy, T. Kaufman, and G. N. Rothblum, Verifying and decoding in constant depth, in Proceedings of the 39th Annual Symposium on Theory of Computing (STOC), ACM, New York, 2007, pp. 440-449.

[28]

P. Gopalan and V. Guruswami, Hardness amplification within NP against deterministic algorithms, in Proceedings of the 23rd Conference on Computational Complexity, IEEE Computer Society Press, Washington, D.C., 2008, pp. 19-30.

[29]

F. Green, A. Roy, and H. Straubing, Bounds on an exponential sum arising in Boolean circuit complexity, C. R. Math. Acad. Sci. Paris, 341 (2005), pp. 279-282.

[30]

V. Guruswami and V. Kabanets, Hardness amplification via space-efficient direct products, in Proceedings of the 7th Latin American Symposium on Theoretical Informatics (LATIN), Lecture Notes in Comput. Sci. 3887, Springer-Verlag, Berlin, 2006, pp. 556-568.

[31]

D. Gutfreund and G. Rothblum, The complexity of local list decoding, in Proceedings of the 12th International Workshop on Randomization and Computation (RANDOM), Lecture Notes in Comput. Sci. 5171, Springer-Verlag, Berlin, 2008, pp. 455-468.

[32]

A. Hajnal, W. Maass, P. Pudlák, M. Szegedy, and G. Turán, Threshold circuits of bounded depth, J. Comput. System Sci., 46 (1993), pp. 129-154.

[33]

K. Arnsfelt Hansen and P. B. Miltersen, Some meet-in-the-middle circuit lower bounds, in Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science (MFCS), Lecture Notes in Comput. Sci. 3153, Springer-Verlag, Berlin, 2004, pp. 334-345.

[34]

J. Håstad, Computational Limitations of Small-Depth Circuits, MIT Press, Cambridge, MA, 1987.

[35]

J. Håstad and M. Goldmann, On the power of small-depth threshold circuits, Comput. Complexity, 1 (1991), pp. 113-129.

[36]

A. Healy, S. Vadhan, and E. Viola, Using nondeterminism to amplify hardness, SIAM J. Comput., 35 (2006), pp. 903-931.

[37]

R. Impagliazzo, Hard-core distributions for somewhat hard problems, in Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society Press, Washington, D.C., 1995, pp. 538-545.

[38]

R. Impagliazzo, R. Jaiswal, and V. Kabanets, Approximately list-decoding direct product codes and uniform hardness amplification, in Proceedings of the 47th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society Press, Washington, D.C., 2006, pp. 187-196.

[39]

R. Impagliazzo, R. Jaiswal, V. Kabanets, and A. Wigderson, Uniform direct product theorems: Simplified, optimized, and derandomized, SIAM J. Comput., 39 (2010), pp. 1637-1665.

[40]

R. Impagliazzo and A. Wigderson, $\mathit{P} = \mathit{BPP}$ if $E$ requires exponential circuits: Derandomizing the XOR lemma, in Proceedings of the 29th Annual Symposium on Theory of Computing (STOC), ACM, New York, 1997, pp. 220-229.

[41]

R. Impagliazzo and A. Wigderson, Randomness vs time: Derandomization under a uniform assumption, J. Comput. System Sci., 63 (2001), pp. 672-688.

[42]

A. Klivans and R. A. Servedio, Boosting and hard-core sets, Machine Learning, 53 (2003), pp. 217-238.

[43]

A. R. Klivans, On the derandomization of constant depth circuits, in Proceedings of the 5th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), Springer-Verlag, Berlin, 2001, pp. 249-260.

[44]

H. Lin, L. Trevisan, and H. Wee, On hardness amplification of one-way functions, in Proceedings of the 2nd Theory of Cryptography Conference (TCC), Lecture Notes in Comput. Sci. 3378, Springer-Verlag, Berlin, 2005, pp. 34-49.

[45]

R. Lipton, New directions in testing, in Proceedings of DIMACS Workshop on Distributed Computing and Cryptography, Vol. 2, AMS, Providence, RI, 1991, pp. 191-202.

[46]

C.-J. Lu, S.-C. Tsai, and H.-L. Wu, On the complexity of hardness amplification, in Proceedings of the 20th Annual Conference on Computational Complexity (CCC), IEEE Computer Society Press, Washington, D.C., 2005, pp. 170-182.

[47]

C.-J. Lu, S.-C. Tsai, and H.-L. Wu, Impossibility results on weakly black-box hardness amplification, in Proceedings of the 16th International Symposium on Fundamentals of Computation Theory (FCT), Lecture Notes in Comput. Sci. 4639, Springer-Verlag, Berlin, 2007, pp. 400-411.

[48]

C.-J. Lu, S.-C. Tsai, and H.-L. Wu, Improved hardness amplification in NP, Theoret. Comput. Sci., 370 (2007), pp. 293-298.

[49]

C.-J. Lu, S.-C. Tsai, and H.-L. Wu, On the complexity of hard-core set constructions, in Proceedings of the 34th International Colloquium on Automata, Languages, and Programming (ICALP), Lecture Notes in Comput. Sci. 4596, Springer-Verlag, Berlin, 2007, pp. 183-194.

[50]

M. Luby, B. Veličković, and A. Wigderson, Deterministic approximate counting of depth-$2$ circuits, in Proceedings of the 2nd Israeli Symposium on Theoretical Computer Science (ISTCS), IEEE Computer Society Press, Washington, D.C., 1993, pp. 18-24.

[51]

M. Naor and O. Reingold, Number-theoretic constructions of efficient pseudo-random functions, J. ACM, 51 (2004), pp. 231-262.

[52]

N. Nisan, Pseudorandom bits for constant depth circuits, Combinatorica, 11 (1991), pp. 63-70.

[53]

N. Nisan and A. Wigderson, Hardness vs randomness, J. Comput. Systems Sci., 49 (1994), pp. 149-167.

[54]

R. O'Donnell, Hardness amplification within $NP$, J. Comput. System Sci., 69 (2004), pp. 68-94.

[55]

M. Pa&caron;traşcu and E. Viola, Cell-probe lower bounds for succinct partial sums, in Proceedings of the 21st Annual Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2010, pp. 117-122.

[56]

R. Raz, A parallel repetition theorem, SIAM J. Comput., 27 (1998), pp. 763-803.

[57]

A. Razborov, Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function, Mat. Zametki, 41 (1987), pp. 598-607 (in Russian); English translation in Math. Notes Acad. Sci. U.S.S.R., 41 (1987), pp. 333-338.

[58]

A. Razborov and S. Rudich, Natural proofs, J. Comput. System Sci., 55 (1997), pp. 24-35.

[59]

A. Razborov and A. Wigderson, $n\sp {\Omega(\log n)}$ lower bounds on the size of depth-$3$ threshold circuits with AND gates at the bottom, Inform. Process. Lett., 45 (1993), pp. 303-307.

[60]

R. Shaltiel and C. Umans, Simple extractors for all min-entropies and a new pseudorandom generator, J. ACM, 52 (2005), pp. 172-216.

[61]

R. Shaltiel and C. Umans, Pseudorandomness for approximate counting and sampling, Comput. Complexity, 15 (2006), pp. 298-341.

[62]

R. Shaltiel and E. Viola, Hardness amplification proofs require majority, in Proceedings of the 40th Annual Symposium on Theory of Computing (STOC), ACM, New York, 2008, pp. 589-598.

[63]

R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, in Proceedings of the 19th Annual Symposium on Theory of Computing (STOC), ACM, New York, 1987, pp. 77-82.

[64]

M. Sudan, L. Trevisan, and S. Vadhan, Pseudorandom generators without the XOR lemma, J. Comput. System Sci., 62 (2001), pp. 236-266.

[65]

L. Trevisan, Extractors and pseudorandom generators, J. ACM, 48 (2001), pp. 860-879.

[66]

L. Trevisan, List decoding using the XOR lemma, in Proceedings of the 44th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society Press, Washington, D.C., 2003, pp. 126-135.

[67]

L. Trevisan, Some applications of coding theory in computational complexity, in Complexity of Computations and Proofs, Quad. Mat. 13, Department of Mathematics, Seconda Univ. Napoli, Caserta, Italy, 2004, pp. 347-424.

[68]

L. Trevisan, On uniform amplification of hardness in NP, in Proceedings of the 37th Annual Symposium on Theory of Computing (STOC), ACM, New York, 2005, pp. 31-38.

[69]

L. Trevisan and S. Vadhan, Pseudorandomness and average-case complexity via uniform reductions, Comput. Complexity, 16 (2007), pp. 331-364.

[70]

E. Viola, The complexity of constructing pseudorandom generators from hard functions, Comput. Complexity, 13 (2004), pp. 147-188.

[71]

E. Viola, On constructing parallel pseudorandom generators from one-way functions, in Proceedings of the 20th Annual Conference on Computational Complexity (CCC), IEEE Computer Society Press, Washington, D.C., 2005, pp. 183-197.

[72]

E. Viola, The Complexity of Hardness Amplification and Derandomization, Ph.D. thesis, Harvard University, 2006; available online at www.eccc.uni-trier.de/.

[73]

E. Viola, New Correlation Bounds for GF($2$) Polynomials Using Gowers Uniformity, Technical Report TR06-097, Electronic Colloquium on Computational Complexity (ECCC), 2006; available online at http://eccc.uni-trier.de/report/2006/097/.

[74]

E. Viola, Pseudorandom bits for constant-depth circuits with few arbitrary symmetric gates, SIAM J. Comput., 36 (2007), pp. 1387-1403.

[75]

E. Viola, Bit-probe lower bounds for succinct data structures, in Proceedings of the 41th Annual Symposium on the Theory of Computing (STOC), ACM, New York, 2009.

[76]

E. Viola, Cell-Probe Lower Bounds for Prefix Sums, preprint, 2009; available online at http://arxiv.org/abs/0906.1370v1.

[77]

E. Viola, On approximate majority and probabilistic time, Comput. Complexity, 18 (2009), pp. 337-375.

[78]

E. Viola, On the power of small-depth computation, Found. Trends Theoret. Comput. Sci., 5 (2009), pp. 1-72.

[79]

E. Viola and A. Wigderson, Norms, XOR lemmas, and lower bounds for GF($2$) polynomials and multiparty protocols, Theory Comput., 4 (2008), pp. 137-168.

[80]

A. Yao, Theory and applications of trapdoor functions, in Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society Press, Washington, D.C., 1982, pp. 80-91.

[81]

A. Yao, Separating the polynomial-time hierarchy by oracles, in Proceedings of the 26th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society Press, Washington, D.C., 1985, pp. 1-10.

Cited By

Srinivasan STripathi USaha BServedio R(2023)Optimal Explicit Small-Depth Formulas for the Coin ProblemProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585238(881-894)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585238
Hatami PHoza WTal ATell RSaha BServedio R(2023)Depth-𝑑 Threshold Circuits vs. Depth-(𝑑+1) AND-OR TreesProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585216(895-904)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585216
Hirahara SShimizu NSaha BServedio R(2023)Hardness Self-Amplification: Simplified, Optimized, and UnifiedProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585189(70-83)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585189
Show More Cited By

Hardness Amplification Proofs Require Majority
1. Theory of computation

Recommendations

Hardness amplification proofs require majority
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computing

Hardness amplification is the fundamental task of converting a δ-hard function f : (0, 1)ⁿ -> (0, 1) into a (1/2-ε)-hard function Amp(f), where f is γ-hard if small circuits fail to compute f on at least a γ fraction of the inputs. Typically, ε,δ are ...
Query complexity in errorless hardness amplification
APPROX'11/RANDOM'11: Proceedings of the 14th international workshop and 15th international conference on Approximation, randomization, and combinatorial optimization: algorithms and techniques

An errorless circuit for a boolean function is one that outputs the correct answer or "don't know" on each input (and never outputs the wrong answer). The goal of errorless hardness amplification is to show that if f has no size s errorless circuit that ...
Using nondeterminism to amplify hardness
STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing

We revisit the problem of hardness amplification in NP, as recently studied by O'Donnell (STOC '02). We prove that if NP has a balanced function f such that any circuit of size s(n) fails to compute f on a 1/poly(n) fraction of inputs, then NP has a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Computing

SIAM Journal on Computing Volume 39, Issue 7

May 2010

757 pages

ISSN:0097-5397

Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 July 2010

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Srinivasan STripathi USaha BServedio R(2023)Optimal Explicit Small-Depth Formulas for the Coin ProblemProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585238(881-894)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585238
Hatami PHoza WTal ATell RSaha BServedio R(2023)Depth-𝑑 Threshold Circuits vs. Depth-(𝑑+1) AND-OR TreesProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585216(895-904)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585216
Hirahara SShimizu NSaha BServedio R(2023)Hardness Self-Amplification: Simplified, Optimized, and UnifiedProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585189(70-83)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585189
Allender EGouwar JHirahara SRobelle C(2023)Cryptographic hardness under projections for time-bounded Kolmogorov complexityTheoretical Computer Science10.1016/j.tcs.2022.10.040940:PB(206-224)Online publication date: 9-Jan-2023
https://dl.acm.org/doi/10.1016/j.tcs.2022.10.040
Gryaznov SPudlák PTalebanfard N(2022)Linear branching programs and directional affine extractorsProceedings of the 37th Computational Complexity Conference10.4230/LIPIcs.CCC.2022.4(1-16)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2022.4
Haitner INukrai DYogev E(2022)Lower Bound on SNARGs in the Random Oracle ModelAdvances in Cryptology – CRYPTO 202210.1007/978-3-031-15982-4_4(97-127)Online publication date: 15-Aug-2022
https://dl.acm.org/doi/10.1007/978-3-031-15982-4_4
Arunachalam SChakraborty SKoucký MSaurabh Nde Wolf R(2021)Improved Bounds on Fourier Entropy and Min-entropyACM Transactions on Computation Theory10.1145/347086013:4(1-40)Online publication date: 1-Sep-2021
https://dl.acm.org/doi/10.1145/3470860
Viola E(2021)AC0 UnpredictabilityACM Transactions on Computation Theory10.1145/344236213:1(1-8)Online publication date: 17-Mar-2021
https://dl.acm.org/doi/10.1145/3442362
Hirahara SAceto L(2020)Non-disjoint promise problems from meta-computational view of pseudorandom generator constructionsProceedings of the 35th Computational Complexity Conference10.4230/LIPIcs.CCC.2020.20(1-47)Online publication date: 28-Jul-2020
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2020.20
Srinivasan SMakarychev KMakarychev YTulsiani MKamath GChuzhoy J(2020)A robust version of Hegedus’s lemma, with applicationsProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3357713.3384328(1349-1362)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1145/3357713.3384328
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents